How to implement a queue using two stacks?
Suppose we have two stacks and no other temporary variable.
Is to possible to "construct" a queue data structure using only the two stacks?
Keep 2 stacks, let's call them inbox and outbox .
Enqueue :
inbox Dequeue :
If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
Pop and return the top element from outbox
Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.
Here's an implementation in Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}
A - How To Reverse A Stack
To understand how to construct a queue using two stacks, you should understand how to reverse a stack crystal clear. Remember how stack works, it is very similar to the dish stack on your kitchen. The last washed dish will be on the top of the clean stack, which is called as L ast I n F irst O ut (LIFO) in computer science.
Lets imagine our stack like a bottle as below;
If we push integers 1,2,3 respectively, then 3 will be on the top of the stack. Because 1 will be pushed first, then 2 will be put on the top of 1. Lastly, 3 will be put on the top of the stack and latest state of our stack represented as a bottle will be as below;
Now we have our stack represented as a bottle is populated with values 3,2,1. And we want to reverse the stack so that the top element of the stack will be 1 and bottom element of the stack will be 3. What we can do ? We can take the bottle and hold it upside down so that all the values should reverse in order ?
Yes we can do that, but that's a bottle. To do the same process, we need to have a second stack that which is going to store the first stack elements in reverse order. Let's put our populated stack to the left and our new empty stack to the right. To reverse the order of the elements, we are going to pop each element from left stack, and push them to the right stack. You can see what happens as we do so on the image below;
So we know how to reverse a stack.
B - Using Two Stacks As A Queue
On previous part, I've explained how can we reverse the order of stack elements. This was important, because if we push and pop elements to the stack, the output will be exactly in reverse order of a queue. Thinking on an example, let's push the array of integers {1, 2, 3, 4, 5} to a stack. If we pop the elements and print them until the stack is empty, we will get the array in the reverse order of pushing order, which will be {5, 4, 3, 2, 1} Remember that for the same input, if we dequeue the queue until the queue is empty, the output will be {1, 2, 3, 4, 5} . So it is obvious that for the same input order of elements, output of the queue is exactly reverse of the output of a stack. As we know how to reverse a stack using an extra stack, we can construct a queue using two stacks.
Our queue model will consist of two stacks. One stack will be used for enqueue operation (stack #1 on the left, will be called as Input Stack), another stack will be used for the dequeue operation (stack #2 on the right, will be called as Output Stack). Check out the image below;
Our pseudo-code is as below;
Enqueue Operation
Push every input element to the Input Stack
Dequeue Operation
If ( Output Stack is Empty)
pop every element in the Input Stack
and push them to the Output Stack until Input Stack is Empty
pop from Output Stack
Let's enqueue the integers {1, 2, 3} respectively. Integers will be pushed on the Input Stack ( Stack #1 ) which is located on the left;
Then what will happen if we execute a dequeue operation? Whenever a dequeue operation is executed, queue is going to check if the Output Stack is empty or not(see the pseudo-code above) If the Output Stack is empty, then the Input Stack is going to be extracted on the output so the elements of Input Stack will be reversed. Before returning a value, the state of the queue will be as below;
Check out the order of elements in the Output Stack (Stack #2). It's obvious that we can pop the elements from the Output Stack so that the output will be same as if we dequeued from a queue. Thus, if we execute two dequeue operations, first we will get {1, 2} respectively. Then element 3 will be the only element of the Output Stack, and the Input Stack will be empty. If we enqueue the elements 4 and 5, then the state of the queue will be as follows;
Now the Output Stack is not empty, and if we execute a dequeue operation, only 3 will be popped out from the Output Stack. Then the state will be seen as below;
Again, if we execute two more dequeue operations, on the first dequeue operation, queue will check if the Output Stack is empty, which is true. Then pop out the elements of the Input Stack and push them to the Output Stack unti the Input Stack is empty, then the state of the Queue will be as below;
Easy to see, the output of the two dequeue operations will be {4, 5}
C - Implementation Of Queue Constructed with Two Stacks
Here is an implementation in Java. I'm not going to use the existing implementation of Stack so the example here is going to reinvent the wheel;
C - 1) MyStack class : A Simple Stack Implementation
public class MyStack<T> {
// inner generic Node class
private class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
}
}
private Node<T> head;
private int size;
public void push(T e) {
Node<T> newElem = new Node(e);
if(head == null) {
head = newElem;
} else {
newElem.next = head;
head = newElem; // new elem on the top of the stack
}
size++;
}
public T pop() {
if(head == null)
return null;
T elem = head.data;
head = head.next; // top of the stack is head.next
size--;
return elem;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void printStack() {
System.out.print("Stack: ");
if(size == 0)
System.out.print("Empty !");
else
for(Node<T> temp = head; temp != null; temp = temp.next)
System.out.printf("%s ", temp.data);
System.out.printf("n");
}
}
C - 2) MyQueue class : Queue Implementation Using Two Stacks
public class MyQueue<T> {
private MyStack<T> inputStack; // for enqueue
private MyStack<T> outputStack; // for dequeue
private int size;
public MyQueue() {
inputStack = new MyStack<>();
outputStack = new MyStack<>();
}
public void enqueue(T e) {
inputStack.push(e);
size++;
}
public T dequeue() {
// fill out all the Input if output stack is empty
if(outputStack.isEmpty())
while(!inputStack.isEmpty())
outputStack.push(inputStack.pop());
T temp = null;
if(!outputStack.isEmpty()) {
temp = outputStack.pop();
size--;
}
return temp;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
C - 3) Demo Code
public class TestMyQueue {
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<>();
// enqueue integers 1..3
for(int i = 1; i <= 3; i++)
queue.enqueue(i);
// execute 2 dequeue operations
for(int i = 0; i < 2; i++)
System.out.println("Dequeued: " + queue.dequeue());
// enqueue integers 4..5
for(int i = 4; i <= 5; i++)
queue.enqueue(i);
// dequeue the rest
while(!queue.isEmpty())
System.out.println("Dequeued: " + queue.dequeue());
}
}
C - 4) Sample Output
Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
You can even simulate a queue using only one stack. The second (temporary) stack can be simulated by the call stack of recursive calls to the insert method.
The principle stays the same when inserting a new element into the queue:
A Queue class using only one Stack, would be as follows:
public class SimulatedQueue<E> {
private java.util.Stack<E> stack = new java.util.Stack<E>();
public void insert(E elem) {
if (!stack.empty()) {
E topElem = stack.pop();
insert(elem);
stack.push(topElem);
}
else
stack.push(elem);
}
public E remove() {
return stack.pop();
}
}
上一篇: 你应该听说过哪些复杂的数据结构？
下一篇: 如何使用两个堆栈实现队列？