Implementing a queue using three stacks

Question

This is just for fun so you will see tons of print statements for trouble shooting. I was hoping on slimming this down some and gain new ideas on what I have. This was a challenge question in a class I'm not in. I know the code i wrote is nightmare-ish anything to slim it down would be nice.

import java.util.*;
public class StackQueue {
 Stack stack1 = new Stack();
 Stack stack2 = new Stack();
 Stack temp = new Stack();
 public void enqueue(String element) {
 stack1.push(element);
 System.out.println(stack1.toString() + "Stack1");
 }
 public void dequeue(){
 System.out.println(stack1.toString() + "\n\nStack1");
 if(!stack1.empty() & stack1.size()> 1 & !stack2.empty()) { // if there are elements in both stacks
 System.out.println("IM IN THE BLOCK");
 while (!stack2.empty()) {
 temp.push(stack2.pop());
 System.out.println(temp.toString() + " TEMPP----");
 System.out.println(stack2.toString() + " STACK 2---");
 }
 while (!temp.empty()) {
 stack1.push(temp.pop());
 System.out.println(stack1.toString() + " STACK1 ----");
 }
 System.out.println(stack1.pop() + " Has been removed");
 System.out.println(stack1.toString() + "STACK 1----");
 System.out.println(stack2.toString()+ "STACK 2----");
 if(stack2.empty()){
 while (!stack1.empty()) {
 temp.push(stack1.pop());
 System.out.println(temp.toString() + " temp ----");
 }
 System.out.println(stack1.addAll(temp));
 System.out.println(stack1.toString()+ "STACK ! ADD");
 temp.removeAllElements();
 System.out.println(temp.toString() + "TEMP _++++_+_+_+_");
 }
 }
 else if(stack1.empty()){
 System.out.println("\n\nstack1 is empty ");
 System.out.println(stack2.pop() + " Has been removed");
 }else {
 System.out.println("\n\n");
 while (!stack1.empty()) {
 System.out.println(stack2.toString() + "Stack2 - second part");
 stack2.push(stack1.pop());
 }
 System.out.println(stack1.toString()+ "stack1");
 System.out.println(stack2.toString()+"stack2");
 System.out.println(stack2.pop() + " Has been removed");
 }
 }
 }
public class Main {
 public static void main(String[] args){
 StackQueue queue = new StackQueue();
 queue.enqueue("hey");
 queue.enqueue("I");
 queue.enqueue("am");
 queue.enqueue("Jeremiah");
 queue.enqueue("now");
 queue.dequeue(); //removes hey
 queue.dequeue(); //removes i
 queue.dequeue();// removes am
 queue.enqueue("one ");
 queue.enqueue("more");
 queue.enqueue("time");
 queue.dequeue(); // removes jeremiah
 // i had to reverse the stack1 order here 
 queue.dequeue(); // removes now
 //queue.dequeue(); // removes one
 queue.enqueue("FIRST");
 queue.dequeue();//removes FIRST
 System.out.println(queue.stack1.toString() + " END S1");
 System.out.println( queue.stack2.toString() + " END S2");
 System.out.println(queue.temp.toString() + " END temp");
 }
}

Answer 1

import java.util.Stack;
public class StackQueue<T> {
 private Stack<T> writeStack = new Stack<T>();
 private Stack<T> readStack = new Stack<T>();
 public void enqueue(T element) {
 writeStack.push(element);
 }
 public T dequeue(){
 if (readStack.empty()) {
 while (!writeStack.empty()) {
 readStack.push(writeStack.pop());
 }
 }
 return readStack.pop();
 }
}

Algorithm

You only need two stacks. Always write to the writeStack, read from the readStack. If the latter is empty, copy everything over.

Naming

Use meaningful names, such as writeStack and readStack instead of stack1 and stack2. Declare them private. A queue's user doesn't care about the internals. Import only what you need, in this case java.util.Stack.

Generics

The Stack<T> is a generic datatype, make use of it. Make your StackQueue generic as well. Instanciate it using

StackQueue<String> queue = new StackQueue<String>();

Return value

dequeue() should return a value. Print it with

System.out.println(queue.dequeue());

• jermiah: Yes, but the problem I found said to use three stacks. This was a challenge problem. However, your solution is great and advice thank you.
• jermiah: Also, why should dequeue return a value ?
• Rainer P.: If you insist on using a third stack, just add a uselessStack and don't use it. Also, a two-stack automaton is equivalent in power to a Turing machine. You never need more than two stacks.
• Rainer P.: From the most abstract point of view, a queue is a datastructure where you can put in values one by one, which are then stored internally and can later be retrieved in the same order. Hence, it must a least implement the methods enqueue, which takes a value and returns nothing, and dequeue, which does the opposite.
• jermiah: I understand its pointless to use three stacks. However, the problem in the book asked me to do so for a challenge. I think adding uselessStack is cheating ha.

Answer 2

Well, first I'd delete all the print statements and add at least one return, but you know that.

 Stack stack1 = new Stack();
 Stack stack2 = new Stack();

Stack is a generic datatype. You should instantiate it as such.

 Stack<String> stack1 = new Stack<>();
 Stack<String> stack2 = new Stack<>();

This way there's no confusion about what it holds.

 public void dequeue(){
 System.out.println(stack1.toString() + "\n\nStack1");
 if(!stack1.empty() & stack1.size()> 1 & !stack2.empty()) { // if there are elements in both stacks
 System.out.println("IM IN THE BLOCK");
 while (!stack2.empty()) {
 temp.push(stack2.pop());
 System.out.println(temp.toString() + " TEMPP----");
 System.out.println(stack2.toString() + " STACK 2---");
 }
 while (!temp.empty()) {
 stack1.push(temp.pop());
 System.out.println(stack1.toString() + " STACK1 ----");
 }
 System.out.println(stack1.pop() + " Has been removed");
 System.out.println(stack1.toString() + "STACK 1----");
 System.out.println(stack2.toString()+ "STACK 2----");
 if(stack2.empty()){
 while (!stack1.empty()) {
 temp.push(stack1.pop());
 System.out.println(temp.toString() + " temp ----");
 }
 System.out.println(stack1.addAll(temp));
 System.out.println(stack1.toString()+ "STACK ! ADD");
 temp.removeAllElements();
 System.out.println(temp.toString() + "TEMP _++++_+_+_+_");
 }
 }
 else if(stack1.empty()){
 System.out.println("\n\nstack1 is empty ");
 System.out.println(stack2.pop() + " Has been removed");
 }else {
 System.out.println("\n\n");
 while (!stack1.empty()) {
 System.out.println(stack2.toString() + "Stack2 - second part");
 stack2.push(stack1.pop());
 }
 System.out.println(stack1.toString()+ "stack1");
 System.out.println(stack2.toString()+"stack2");
 System.out.println(stack2.pop() + " Has been removed");
 }
 }

I'm not following what temp does for you. Consider

 public void dequeue() {
 if (stack2.empty()) {
 while (!stack1.empty()) {
 String current = stack1.pop();
 stack2.push(current);
 System.out.println(current + " moved from stack1 to stack2.")
 }
 }
 System.out.println(stack2.pop() + " Has been removed");
 }

In this system, stack1 is backwards, so we transfer it to stack2. We do so only when stack2 is empty, because otherwise it would get out of order.

If both stacks are empty, it will throw an exception on the last pop. It's up to you if you catch it or allow it to propagate. You could also check for empty() again.

Consider renaming stack1 and stack2 to have more meaningful names. Something like backward and forward to keep track of the remove order. So you reverse the backward stack onto the forward stack and remove from the forward stack. I'd find that a lot more readable.

Note: I didn't try to check correctness on your original algorithm, but I'm confident that this will work.

• jermiah: The problem required me to use three stacks which is why I used another stack called temp.