Menu
Using 2 queues, we can make a stack, which can perform push operations in O(n) and all other functionalities in O(1) time.
There are two approaches to implement stack using Queue: First, we can make the push operation costly. Second, we can make the pop operation costly.
Implement Stack using Queues in C++ push(x) − Push x onto stack. top() − Return the top element from stack. empty() − Return whether the stack is empty or not.
A simple way to implement k queues is to divide the array in k slots of size n/k each, and fix the slots for different queues, i.e., use arr[0] to arr[n/k-1] for the first queue, and arr[n/k] to arr[2n/k-1] for queue2 where arr[] is the array to be used to implement two queues and size of array be n.
Version A (efficient push):
Version B (efficient pop):
The easiest (and maybe only) way of doing this is by pushing new elements into the empty queue, and then dequeuing the other and enqeuing into the previously empty queue. With this way the latest is always at the front of the queue. This would be version B, for version A you just reverse the process by dequeuing the elements into the second queue except for the last one.
Step 0:
"Stack"
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
Step 1:
"Stack"
+---+---+---+---+---+
| 1 | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 1 | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
Step 2:
"Stack"
+---+---+---+---+---+
| 2 | 1 | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | 2 | 1 | | | |
+---+---+---+---+---+ +---+---+---+---+---+
Step 3:
"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 3 | 2 | 1 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
We can do this with one queue:
push:
n is the number of elements in the queue, then remove and insert element n-1 times.pop:
.
push 1
front
+----+----+----+----+----+----+
| 1 | | | | | | insert 1
+----+----+----+----+----+----+
push2
front
+----+----+----+----+----+----+
| 1 | 2 | | | | | insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | 2 | 1 | | | | remove and insert 1
+----+----+----+----+----+----+
insert 3
front
+----+----+----+----+----+----+
| | 2 | 1 | 3 | | | insert 3
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | 1 | 3 | 2 | | remove and insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | | 3 | 2 | 1 | remove and insert 1
+----+----+----+----+----+----+
Sample implementation:
int stack_pop (queue_data *q)
{
return queue_remove (q);
}
void stack_push (queue_data *q, int val)
{
int old_count = queue_get_element_count (q), i;
queue_insert (q, val);
for (i=0; i<old_count; i++)
{
queue_insert (q, queue_remove (q));
}
}
import java.util.*;
/**
*
* @author Mahmood
*/
public class StackImplUsingQueues {
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
public int pop() {
if (q1.peek() == null) {
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
} else {
int pop = q1.remove();
return pop;
}
}
public void push(int data) {
if (q1.peek() == null) {
q1.add(data);
} else {
for (int i = q1.size(); i > 0; i--) {
q2.add(q1.remove());
}
q1.add(data);
for (int j = q2.size(); j > 0; j--) {
q1.add(q2.remove());
}
}
}
public static void main(String[] args) {
StackImplUsingQueues s1 = new StackImplUsingQueues();
// Stack s1 = new Stack();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
s1.push(8);
s1.push(9);
s1.push(10);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
System.out.println("8th = " + s1.pop());
System.out.println("9th = " + s1.pop());
System.out.println("10th= " + s1.pop());
}
}
Can we just use one queue to implement a stack? I can use two queues, but considering single queue would be more efficient. Here is the code:
public void Push(T val)
{
queLower.Enqueue(val);
}
public T Pop()
{
if (queLower.Count == 0 )
{
Console.Write("Stack is empty!");
return default(T);
}
if (queLower.Count > 0)
{
for (int i = 0; i < queLower.Count - 1;i++ )
{
queLower.Enqueue(queLower.Dequeue ());
}
}
return queLower.Dequeue();
}
queue<int> q1, q2;
int i = 0;
void push(int v) {
if( q1.empty() && q2.empty() ) {
q1.push(v);
i = 0;
}
else {
if( i == 0 ) {
while( !q1.empty() ) q2.push(q1.pop());
q1.push(v);
i = 1-i;
}
else {
while( !q2.empty() ) q1.push(q2.pop());
q2.push(v);
i = 1-i;
}
}
}
int pop() {
if( q1.empty() && q2.empty() ) return -1;
if( i == 1 ) {
if( !q1.empty() )
return q1.pop();
else if( !q2.empty() )
return q2.pop();
}
else {
if( !q2.empty() )
return q2.pop();
else if( !q1.empty() )
return q1.pop();
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With