This discussion is archived
7 Replies Latest reply: Jun 14, 2008 12:33 AM by 807601

# Stacks and Dequeue Logic Loop Help - Alphabetizing Strings

Currently Being Moderated
Hi all! First, I apologize ahead of time for the long question, but I want to make sure I explain myself clearly. I am working on a program for school that is supposed to ask the user to input a word. The program then uses a stack and a dequeue to manipulate the individual characters of the string and outputs the string, alphabetized.
The following gives you a better idea of what 's supposed to happen:
A word will be input then processed one letter at a time left to right. In each case, the letter will be inserted at the rear of the deque, but it may be necessary to move some of the other letters first. At the end of each insertion, those letters less than or equal to the inserted letter will be on the deque, and those greater than the inserted letter will be on the stack. Once the last letter in the string has been inserted, the content of the stack is moved to the rear of the deque, and the deque is then emptied from the front.

For example, if the user inputs the word BANDAGE, after manipulation using stack and dequeue, the program outputs: AABDEGN. I have already created the stack and dequeue classes, but I am having trouble formulating the logic to check each individual character and output the string alphabetized. Can someone please show me how to go about, or at least point me in the right direction. Thanks in advance!

Here is my main class:
``````public static void main(String[] args){

//Constructors to create instances of the Dequeue and Stack class.
program1Dequeue myDQ = new program1Dequeue();
program1Stack myStack = new program1Stack();
Scanner userInput = new Scanner(System.in);

//Ask and take in user input
System.out.println("Enter a word: ");
String aString = userInput.next();

//Take 1st character of the string and place in queue
char firstChar = aString.charAt(0);

//further logic using stacks and dequeue to alphabetize input string
char char2 = aString.charAt(1);
if(char2 <firstChar)
{

myStack.push(firstChar); //place element in stack
myStack.pop();

myDQ.addToCurrent(firstChar); //now place element back at end of queue
}

char char3 = aString.charAt(2); ***From here on I get stuck***
if((char3 < char2) && (char3 < firstChar))
{
myDQ.removeTail();
}

//Display Queue and Stack contents.
myDQ.getAllData();
myStack.display();

} ``````
I am sure there's an easier/better way to implement this logic, I am just not seeing it. I eventually will implement some sort of loop for the logic, but in the above code, I am simply trying to figure out the pattern to use in the loop. Thanks again.
• ###### 1. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
Johnny,

That's an interesting theoretical exercise, but it's just basically (in java, at least) nutts! If I where doing this this in the "real world" I'd just stick the characters in an array, sort it with Arrays.sort, and print the result THREE. That's lines of really simple code. If really had to "do it manually" then I'd insert each letter into the appropriate place in a LinkedList. Easy.

Now, having vented my spleen, until you understand HOW your program will work FORGET writing a program... and concentrate on HOW it will work...
``````  for each letter in word
if necessary then
reorder the existing letters in the list
endif
append this letter to the list
then some magic happens which:
(a) moves all letters which are less-than this-letter to the before-list; and
(b) moves those letters which are greater than this-letter to the after-list;
which is (IMHO) just plain nutts!
next letter
append the after-list to the before-list
output the before list``````
What you need to work on is the bit where "some magic happens".

All professors are idiots. It's in there job description.

Cheers. Keith.

Edited by: corlettk on 14/06/2008 06:06
• ###### 2. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
JohnnyBoy08 wrote:
Hi all! First, I apologize ahead of time for the long question, but I want to make sure I explain myself clearly. I am working on a program for school that is supposed to ask the user to input a word. The program then uses a stack and a dequeue to manipulate the individual characters of the string and outputs the string, alphabetized.
The following gives you a better idea of what 's supposed to happen:
A word will be input then processed one letter at a time left to right. In each case, the letter will be inserted at the rear of the deque, but it may be necessary to move some of the other letters first. At the end of each insertion, those letters less than or equal to the inserted letter will be on the deque, and those greater than the inserted letter will be on the stack. Once the last letter in the string has been inserted, the content of the stack is moved to the rear of the deque, and the deque is then emptied from the front.

For example, if the user inputs the word BANDAGE, after manipulation using stack and dequeue, the program outputs: AABDEGN. I have already created the stack and dequeue classes, but I am having trouble formulating the logic to check each individual character and output the string alphabetized.
Hmmm...it doesn't seem possible. Suppose the user enters:

``````process K -> deque: K
stack:

process S -> deque: K S
stack:

process A -> deque: A
stack: K S

process D -> deque: A D
stack: K S

process Z -> deque: A D Z
stack: K S``````
Then if you pop the S off the stack and add it to the end of the deque, things will be out of order. And, if you pop the S off the stack and store it an array and then pop the K off the stack and add it to the end of the deque, things will be out of order too.

Hmmmm...a brain teaser.
• ###### 3. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
corlettk wrote:
All professors are idiots. It's in there job description.
...lol!

Thanks for the quick reply corlettk,

Yeah, I agree with you on the program being too theoretical. It's a good exercise and I ve spent too many hours trying to figure out the "magical aspect" of it. The problem is, the prof doesn't want us to use Arrays.sort or anything that will take the torture out of it :) we are supposed to use the stack and queue to do all the sorting and manipulation manually (yep, mostly stack and queue manipulation with some sorting). Oh, the wonderful pain profs put us through! I think I 'll get some sleep now, maybe that will help to refresh my mind. Thanks for the help.

-Johnny
• ###### 4. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
I was just rereading this bit and the light bulb went on...
but it may be necessary to move some of the other letters first. At the end of each insertion, those letters less than or equal to the inserted letter will be on the deque, and those greater than the inserted letter will be on the stack.
What I think this means is...

before appending the letter to the before-queue
(a) move those letters which are greater than this-letter from the-head-of-the-after-stack to the end-of-the-before-queue; and
(b) move all letters from which are less than this-letter from the end-of-the-before-queue to the the-head-of-the-after-stack.
... effectively placing "the insertion point" at "this-letter"

But my problem with it is efficiency... there's somewhere in the order of O(N^2) tests going on for each character. A simple [insertion sort|http://en.wikipedia.org/wiki/Insertion_sort] is more efficient at O(n+d)... which isn't as bad as it sounds on doubly-linked-lists, where the cost of inversion is O(1).
• ###### 5. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
>
I am sure there's an easier/better way to implement this logic, I am just not seeing it. I eventually will implement some sort of loop for the logic, but in the above code, I am simply trying to figure out the pattern to use in the loop. Thanks again.
For this to work the sequence inserted in the deque and the stack must be sorted all the time. You use the rear of the deque and the top of the stack as the insertion point. I've used a comma sign to show your insertion point. When everything of BANDAGE except for the last E has been inserted it may look like this,

AAB,DGN

AAB is in the deque (with B at the rear) and DGN is on the stack (with D on the top). Or it may look like this,

AABD,GN

or even,

AABDGN,

so the stack is empty. It doesn't matter. The only thing that matters is that AABDGN is in sorted order regardless of which letters are in the deque and which are on the stack.

Now the final E comes in. What to do? Well if you have this situation,

AAB,DGN

you pop the D from the stack and insert it in the rear of the deque to get this

AABD,GN

Now you note that E fits between D and G so you insert E in the deque to get,

AABDE,GN

Note that after this operation both deque and stack are still sorted.

AABDGN,

here you would move first the N and push it on the stack to get,

AABDG,N

The E still cannot be inserted so you remove G and push it to get,

AABD,GN

Now E can be inserted in the deque and you finally get

AABDE,GN

---

So to summarize,

1. The deque and the stack together hold a sorted sequence at all times.
2. View the rear of the deque and the top of the stack as the insertion point.
3. Move the insertion point of the sequence by moving letters between deque and stack.
4. Insert a letter in the deque when the insertion point is positioned right.
• ###### 6. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
7stud,

That's pretty good thinking on trying to crack the system, which reminded me that the test Strings to be entered are given to us. Here are the test data strings and a sample output process of what should be returned from program.

The deque displays front to back, as left to right. The stack displays top to bottom as left to right. The word being input here is BANDAGE.

Step Letter Deque Stack
0------ B--------- -----{}
1------ A ----------{}------ {B}
2----- -------------{A}------{B}
3 ------N-------- {AB}---- {}
4 -----------------{ABN}--- {}
5 ------D ---------{AB}--- {N}
6 -----------------{ABD}-- {N}
7------ A--------- {AB}-- {DN}
8 --------------------{A}-- {BDN}
9 -------------------{AA}- {BDN}
10 -----G-------- {AAB} {DN}
11 ---------------{AABD} {N}
12 --------------{AABDG} {N}
13 -----E------- {AABD} {GN}
14 --------------{AABDE} {GN}
15 --------------{AABDEG} {N}
16 -------------{AABDEGN}

how would I implement the logic behind this? Specifically, I am having trouble creating the loop for testing if the current char is greater than the previous char & knowing when to pop the stack to add the chars back on the dequeu. The generic code for the logic behind this would be more than super, but I ll be equally gratefull for any and all help offered on this problem - just as long as I have something to work with. Thanks.

By the way, thanks a lot for the insight above everyone. It' s helping to look at the problem differently. Here is the list of Strings on which the program will be tested:

BANDAGE
PARTICLE
OBFUSCATE
TRIPLEWORDSCORE
VERISIMILITUDE
POLYSACCHARIDE
SUBBOOKKEEPPER

Another question is if it 's possible to create a general process that will work for all these above words or will I have to manually manipulate each word to get alphabetized just right?

Edited by: JohnnyBoy08 on Jun 14, 2008 12:50 AM
• ###### 7. Re: Stacks and Dequeue Logic Loop Help - Alphabetizing Strings
Currently Being Moderated
This still a nutzoid algorithm, but here goes anyway:
``````package forums;

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Iterator;

import java.util.Scanner;

class SpazmoidLetterSorterator
{

public static void main(String[] args) {

Deque<Character> before = new ArrayDeque<Character>(); // a FIFO queue
Deque<Character> after = new ArrayDeque<Character>();  // a LIFO stack
String word = "BANDAGE"; //getWord();
System.out.println("+"+word.charAt(0)+"\n");
for (int i=1; i<word.length(); i++) {
char letter = word.charAt(i);
System.out.println("+"+letter);
Character l = null;
while ( (l=before.peekLast())!=null && l>letter ) {
System.out.println(">"+l);
}
while ( (l=after.peekFirst())!=null && l<letter ) {
System.out.println("<"+l);
}
System.out.println("before="+join(before)+", after="+join(after));
System.out.println();
}
System.out.println(join(before)+","+join(after));
}

private static String getWord() {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a word: ");
return scanner.next();
}

private static String join(Deque<Character> queue) {
StringBuilder result = new StringBuilder();
Iterator<Character> it = queue.iterator();
while ( it.hasNext() ) {
result.append(it.next());
}
return result.toString();
}

}``````
... ergo