• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3121
  • Last Modified:

Using queue/stack solution for a palindrome

Hello folks

*disclaimer* this IS homework (gasp!) therefore I am not after complete code just general direction/assistance.  I understand the concepts I need to use (stack, queue, linked list) but it is stitching them together that has got me stumped... Here's the question:

"Read a textfile in to the main method.  Load in into a linked queue (1 char at a time).  Test whether a string is a palindrome using a stack.  Output palindromes only to a new textfile."  For those who don't know a palindrome reads the same forward as backward.  Madam I'm Adam.  Punct is ignored.  A pretty common question in homework, however, the above method is probably the most cumbersome I've EVER seen.  

I am OK with the I/O functions, and I can check whether a string is a pal, but I am not sure about passing it from the queue to the stack.  I have been working on something like this:

for (int x = 1; x <=length; x++)
      {
        int y, z;
             y =q.dequeue();
            if (y % 2 == 0)
                   s.push(y);
            else
                  q.enqueue(y);
                        
            z =s.pop( );
            if (z % 2 == 0)
                  s.push(z);
            else
                  q.enqueue(z);
      }

Is this sort of the right track to load form a queue to a stack?

My stack operations to just to test whether an item is a pal looks like the below.  I'll insert the I/O functions later.

public static boolean palindrome( String originalString ){      
Stack s = new Stack();    
char ch;    

StringBuffer reversedWord = new StringBuffer();    
       for ( int i=0; i < originalString.length(); i++){          
ch =  originalString.charAt(i);          
s.push ( new Character(ch) );    
}    
     
while ( !s.isEmpty() ){        
         
Character stackItem = (Character)s.pop();        
         
       
Char ch = stackItem.charValue();        
reversedWord.append( ch );    
}    
   
if ( originalString.equals ( reversedWord.toString() ) )            
return true;  
     
else            
return false;
}


Thoughts, comments?
0
south_paw
Asked:
south_paw
  • 5
  • 3
  • 3
  • +1
1 Solution
 
aozarovCommented:
Reverse the string and compare sounds ok and your implemention looks ok as well.
Though that can be done via calling reverse funtion of StringBuffer :-) [I know you need to use Stack]
You can also consider running half way and putting it in the stack and then continue the second half and comparing the poped item with the current one.
0
 
CEHJCommented:
I agree with you that it sounds cumbersome ;-) The queue thing sounds a step too far, but don't forget that you need to remove punctuation, so the original String read from the text file needs to be retained. You can enqueue only letter characters and then move them to a stack at the end of the String
0
 
Sys_ProgCommented:
Though this can be done just running a loop,
if u have to use either of the above mentioned data structures, I would use two stacks
A loop running till (length of srting)/2
This loop would populate 2 stacks
1 stack with characters from front of string
The other stack with characters from end of string

Alsom push the punctuation char's

Now, while run a loop for popping,
Pop from both stacks and compare, if you pop a punctuation, ignore that and pop the next item from that particular stack.


Thanks,
Amit
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
aozarovCommented:
>> This loop would populate 2 stacks
Isn't it better to put one in a stack and the other in a list[to simulate queue] (so first of the one is going to be last of the other)?
0
 
Sys_ProgCommented:
Yes, thats also an option, but in that case, u would have to push/add the complete string, and in my case, it would just push half of the string

Amit
0
 
aozarovCommented:
>> Yes, thats also an option, but in that case, u would have to push/add the complete string, and in my case, it would just push half of the string
You can, but you can also travers 0..n/2 and use i and n/2 + i as indexes to traves only half of the string.
0
 
Sys_ProgCommented:
Yep, I think both of our solutions are approximately the same
Only thing is u use two data structures and I use one
Either one would work

Amit
0
 
CEHJCommented:
south_paw, the objective of course is to get you using these abstract datatype classes, so you'd be wise to stick to the spec and do the best with it you can
0
 
south_pawAuthor Commented:
Thanks for the comments so far.  Just to get things back on track, I am wondering if I have the right idea up top about storing the values in a queue and then using a stack to check if the item is a pal.  Specifically, how does one send the values from the queue to the stack to check?

That's the requirement, and I can code the interfaces, pal stack checker, linked queue, blah, blah, it's just getting from the queue to the stack that's got me stranded...

Ta
0
 
CEHJCommented:
Maybe something like:


madam

Queue:
HEAD
m
a
d
a
m


Stack:
TOP
m
a
d
a
m


boolean isPalindrome = true;
while (isPalindrome && !stack.isEmpty()) {
      Character qC = (Character)queue.dequeue();
      Character qS = (Character)stack.pop();
      isPalindrome = qC.equals(qS);
}
0
 
Sys_ProgCommented:
Why do u want to run two loops for populating queue and stack

Run a single loop (length/2) times
Populate stack with chars in 1 to n/2 position
and populate queue with chars in n/2+1 to n posiion

Then run a loop till the stack is empty or the end of queue is reachd
Comapre each item in queue with each item popped frm stack

Amit
0
 
south_pawAuthor Commented:
Amit,

I have lost you there...  items should be in the queue, then test for pal = true using a stack.
0
 
Sys_ProgCommented:
Ok, the first task is to fill up your queue and stack

So, the algo would be

while (loop till length/2) {
    stk.push ( str[i]) ;
    que.add ( str [n/2 + i] ;
}

Now, 2nd step is to check for pall
So, run a loop till
either stk is empty or queue is empty
While (){
     ch1 = stk.pop ();
     ch2 = que.dequeue();
     if ch1 != ch2  
         not a pallindrome
         exit
}

Now, chck for whether either quue or stk is still having values, if yes, then not a pallindrome


Amit

0

Featured Post

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

  • 5
  • 3
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now