The puzzle is to implement basic queue operations with using only basic stack operations. That is, a stack object is given, we need construct a wrapper for the queue functions, insert, remove, which will only use the stack object as its storage, and naturally will have to use the stack operations. I have already posted the opposite task in the post Implement stack using a queue
This can be done using two stack objects. We call these the first stack and the second stack. Although either the insert or the remove complexity will no more be O(1).
I have discussed the process gradually. I added the last solution when it clicked in my mind while reviewing this post.
The Idea
The idea is pretty simple. We start with an empty stack. For the insert operation we simply push the value to be inserted into the stack. The remove operation needs some manipulation. When we need to remove from the queue (simulated with a stack): pop out all the elements one by one and keep them pushing into the second stack. The last element popped from the first stack is not pushed in the second stack, and is returned as the queue front element. Next all the elements in the second stack are all popped back to the first stack one by one (this step can be avoided with a modification mentioned later).
Let the number of elements in the stack is n then we pop (n-1) elements from the stack and push them into the second stack. The last popped element from the first stack is returned. Note that the bottom element in the stack is the one which was inserted first, and we are returning it first, therefore it works like a remove operation (First in First Out). The idea is shown below.
Insert pseudocode
void insert (stack_t s)
{
stack.push (element);
}
Remomve pseudocode
element_type remove (void)
{
while (there is one element in stack1) // Only (n-1) elements 0 to (n-2)
{
stack_top_element = stack1.pop ();
stack2.push (stack_top_element);
}
element = stack1.pop (); // The front element of the queue
while (stack2 is not empty) // Restore the stack1
{
stack_top_element = stack2.pop ();
stack1.push (stack_top_element);
}
return element;
}
A Slightly Better Idea
We can avoid the restoring of the stack1 loop, which requires transfer of stack2 to stack1 for every remove operation. The plan is, instead of transferring the stack2 contents to stack1, we switch roles of the stack, and also remember that when the stack2 has the elements it is in the reverse order of the original. If 1,2,3,4,5 was pushed in stack1, the remove operation will make pop out 5,4,3,2 in that order and into stack2 and return 1. At this moment stack1 is empty and stack2 holds the elements of stack1 in the reverse order (after removing 1). Therefore the next removal should simply return the top element of stack2. But the next insertion in such a case will have to undergo a similar operation like before. Pop off all the elements from stack2 to stack1 and then push the new element to insert into stack1.
To implement this technique we need to know how to detect the cases.
- If stack2 is empty we know that to insert we need to push the element in stack1 and to remove we need to pop all but the last element into stack2 and return the last element of stack1.
- If stack1 is empty we know that to remove we need to pop and return the top element in stack2 and to insert we need to pop all elements from stack2 to stack1 and then push the given element in stack1
- In both stack1 and stack2 are empty then the queue is empty.
The better Insert pseudocode
void insert (stack_t s)
{
if (stack2.isempty())
{
stack1.push (element);
}
else if (stack1.isempty ())
{
while (stack2.isempty () is false)
{
stack_top_element = stack2.pop ();
stack1.push (stack_top_element);
}
stack1.push (element);
}
}
The better Remove pseudocode
element_type remove (void)
{
if (stack2.isempty ()) // We have the stack in stack1 in original order
{
while (stack1 has one element left) // Pop all but one elements from stack1
{
stack_top_element = stack1.pop ();
stack2.push (stack_top_element);
}
element = stack1.pop (); // Get the last element
}
else if (stack1.isempty ()) // We have the stack in stack2 in reverse order
{
element = stack2.pop (); // The top of stack2 is the element we want
}
return element;
}
Depending on which stack is empty the insertion and removal operation is handled. This will avoid the unnecessary operation of taking back the elements to stack1 for every remove. A series inserts or removes will be done immediately. For series of inserts the elements will be pushed in stack1 and for series of removes the elements will be pushed in stack2. Alternating insert and remove will require transferring the elements from one stack to another.
Although there is an even better solution to this. But let me first show this code.
Here is a simple diagram. Assume that the stack representation in the diagram has infinite length. This diagram shows the better Insert and Remove operations.
/** INSERT operation **/ after insert (1), insert (2), insert (3), insert (4) elements are simply pushed into stack1 +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | 4 | <--- top | | +----+ +----+ | 3 | | | +----+ +----+ | 2 | | | +----+ +----+ | 1 | | | +----+ +----+ <--- top stack1 stack2
/**After REMOVE operation **/ +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | | | 2 | <--- top +----+ +----+ | | | 3 | +----+ +----+ | 1 | <--- top | 4 | +----+ +----+ stack1 stack2 Return the stack1 top element as the queue front element +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | | | 2 | <--- top +----+ +----+ | | return stack1 last | 3 | +----+ element (1) +----+ | | | 4 | +----+ <--- top +----+ stack1 stack2
/** Next Remove operation **/ after remove operation +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ | | | | return stack2 top +----+ +----+ element (2) | | | 3 | <--- top +----+ +----+ | | | 4 | +----+ <--- top +----+ stack1 stack2
/** Next INSERT operation **/ after INSERT (5) operation +----+ +----+ | | | | +----+ +----+ | | | | +----+ +----+ elements transferred to | | | | stack1 from stack2 +----+ +----+ inserted element on | 5 | <--- top | | stack1 top. +----+ +----+ | 4 | | | +----+ +----+ | 3 | | | +----+ +----+ <--- top stack1 stack2
Now we go into the implementation, which is pretty simple.
Sourcecode
#include <stdio.h>
#include <stdlib.h>
#define STK_DEFAULT_SIZE 128
#define TYPE int
typedef struct _stack_t
{
TYPE *arr; // the contents
int top; // stack top
int max; // stack capacity
} stack_t;
stack_t *stack_allocate (int size);
void stack_free (stack_t * stk);
void stack_push (stack_t * stk, TYPE e);
TYPE stack_pop (stack_t * stk);
int stack_is_empty (stack_t * stk);
int stack_is_full (stack_t * stk);
void stack_display (stack_t * s);
/* Simulated Queue operations Start */
void
queue_insert (stack_t * s1, stack_t * s2, TYPE v)
{
if (stack_is_empty (s2))
{
stack_push (s1, v);
}
else if (stack_is_empty (s1))
{
while (!stack_is_empty (s2))
{
stack_push (s1, stack_pop (s2));
}
stack_push (s1, v);
}
}
TYPE
queue_remove (stack_t * s1, stack_t * s2)
{
int retval;
if (stack_is_empty (s2))
{
while (!stack_is_empty (s1))
{
stack_push (s2, stack_pop (s1));
}
retval = stack_pop (s2); // Pop off the last one needed
}
else if (stack_is_empty (s1))
{
retval = stack_pop (s2);
}
return retval;
}
int
queue_is_empty (stack_t * s1, stack_t * s2)
{
return (stack_is_empty (s1) && stack_is_empty (s2));
}
/* Simulated Queue operations END */
/* Simulated stack operations END */
/* Stack operations START */
stack_t *
stack_allocate (int size)
{
stack_t *stk;
stk = malloc (sizeof (stack_t));
stk->arr = malloc (sizeof (TYPE) * size);
stk->max = (size <= 0) ? STK_DEFAULT_SIZE : size;
stk->top = -1;
return stk;
}
void
stack_free (stack_t * stk)
{
if (stk == NULL)
{
return;
}
free (stk->arr);
free (stk);
}
void
stack_push (stack_t * stk, TYPE e)
{
if (stk->top != (stk->max - 1))
{
stk->arr[++(stk->top)] = e;
}
}
TYPE
stack_pop (stack_t * stk)
{
if (stk->top == -1)
{
return (TYPE) 0;
}
return stk->arr[(stk->top)--];
}
int
stack_is_empty (stack_t * stk)
{
return (stk->top == -1);
}
int
stack_is_full (stack_t * stk)
{
return (stk->top == (stk->max - 1));
}
/* For demo */
void
stack_display (stack_t * s)
{
int i = 0;
while (i <= s->top)
{
printf ("[%d], ", s->arr[i]);
i++;
}
}
/* Stack operations end */
#define MAX 128
int
main (void)
{
stack_t *s1, *s2;
int x, select;
/* Static allocation */
s1 = stack_allocate (MAX);
s2 = stack_allocate (MAX);
do
{
printf ("\n[1] Insert\n[2] Remove\n[0] Exit");
printf ("\nChoice: ");
scanf (" %d", &select);
switch (select)
{
case 1:
printf ("\nEnter value to Insert:");
scanf (" %d", &x);
/* Pushing */
queue_insert (s1, s2, x);
printf ("\n\n__________________________\nCurrent Stack:\n");
printf ("stack1: ");
stack_display (s1);
printf ("\nstack2: ");
stack_display (s2);
printf ("\n\nInserted Value: %d", x);
printf ("\n__________________________\n");
break;
case 2:
/* Popping */
if (queue_is_empty (s1, s2))
{
printf ("\n\nNo values removed");
}
else
{
x = queue_remove (s1, s2);
printf ("\n\nPopped Value: %d", x);
}
printf ("\n\n__________________________\nCurrent Stack:\n");
printf ("stack1: ");
stack_display (s1);
printf ("\nstack2: ");
stack_display (s2);
printf ("\n__________________________\n");
break;
case 0:
printf ("\nQutting.\n");
return 0;
default:
printf ("\nQutting.\n");
return 0;
}
}
while (1);
return 0;
}
This code is divided in three parts. One is a hand made implementation of a stack of integers. Next the queue operations using the stack, and a demo driver which will demonstrate the code interactively. Run the code to see how the contents of the stack changes. In the code, the queue simulating functions are highlighted. The queue empty function is implemented here with the other stack functions. Note that the queue functions requires the two stacks. To clean this mess of passing two stack objects you can wrap these in a queue type structure and pass an object to the queue type structure. Note that the implementation considers that the stack (queue) size is static defined by the MAX macro, and also the queue will only contain integers. The code is straight forward therefore i am not going to describe it. Although if there is any problem feel free to drop a comment.
Here is a stack wrapper class in CPP using the STL queue class.
#include <iostream>
#include <stack>
using namespace std;
template <class T> class myqueue
{
private:
stack <T> S1, S2;
public:
void mq_insert (T data);
T mq_remove ();
};
template <class T> void myqueue <T>::mq_insert (T data)
{
if (S2.empty ())
{
S1.push (data);
}
else if (S1.empty ())
{
while (!S2.empty ())
{
S1.push (S2.pop ());
}
S1.push (data);
}
}
template <class T> T myqueue <T>::mq_remove ()
{
T temp;
if (S2.empty ())
{
while (!S1.empty ())
{
S2.push (S1.pop ());
}
temp = S2.pop ();
}
else if (S1.empty ())
{
temp = S2.pop ();
}
return temp;
}
An even better solution
While reviewing this post, I got another idea. I realized that we do not need pop off all the content from stack2 back to stack1 when inserting in the last method which I described. Note that, the first stack always holds the latest element on the top, and the stack2 will be initially empty. When we insert an element in the simulated queue, we simply push it into stack1. When we need to remove an element from the simulated queue, we can pop off all the elements from stack1 to stack2 and the return the top element of stack2. Subsequent removals can be done by popping and returning elements from stack2. If at this point, a value is inserted, we can just simply push it in stack1. Therefore at any point of time, stack1 will contain latest element of the simulated queue, and the stack2 will contain the oldest element of the simulated queue on its top. If at some point of time after a sequence of the simulated queue removals, stack2 becomes empty, the next queue operation will require popping off all elements from stack1 to stack2, hence reversing the original arrival order of the elements and prepare them to be delivered out in FIFO order from stack2 with as described.
Hence the improvement is, once stack1 is reversed into stack2 the elements in stack2 are in FIFO order with respect to their original insertion order. So it is unnecessary to put them back into stack1. Therefore this process avoids unnecessary reversals of stack
Therefore here goes the even better insert and remove operations.
The even better Insert pseudocode
void insert (stack_t s)
{
stack1.push ();
}
The even better Remove pseudocode
element_type remove (void)
{
if (stack2.isempty ()) // We have the stack in stack1 in original order
{
while (!stack1.isempty ()) // Pop all elements from stack1 into stack2
{
stack_top_element = stack1.pop ();
stack2.push (stack_top_element);
}
}
return stack2.pop ();
}
Here is the code modification to the presented full code for the last solution.
/* Better Simulated Queue operations Start */
void
queue_insert (stack_t * s1, stack_t * s2, TYPE v)
{
stack_push (s1, v);
}
TYPE
queue_remove (stack_t * s1, stack_t * s2)
{
if (stack_is_empty (s2))
{
while (!stack_is_empty (s1))
{
stack_push (s2, stack_pop (s1));
}
}
return stack_pop (s2); // Pop off the last one needed;
}
The C++ modification is given below for the sake of completeness.
#include <iostream>
#include <stack>
using namespace std;
template <class T> class myqueue
{
private:
stack <T> S1, S2;
public:
void mq_insert (T data);
T mq_remove ();
};
template <class T> void myqueue <T>::mq_insert (T data)
{
S1.push (data);
}
template <class T> T myqueue <T>::mq_remove ()
{
if (S2.empty ())
{
while (!S1.empty ())
{
S2.push (S1.pop ());
}
}
return S2.pop ();
}
Design note
I have passed two stacks explicitly through the insert and remove interface to emphasize that we are implementing one queue with two stacks. I think I should also mention, that to make an object oriented approach, we can put the two stacks in a structure and name it simulated_stack or whatever, and then pass an instance of it. The insert and remove operations will work on an object of the simulated_stack. The C++ implementation shows the process.
Complexity
In the second method, if a series of insert or remove is applied the operations will be O(1). When a remove is made after an insert is made or vice-verca the code requires to transfer the contents from one stack to another, which results in O(n) operation.
In the third method the number of shifting from one stack to another is decreased a lot and it does not depend on if we alternate insert and remove operations. Although, because a remove may require a reversal of an entire stack, therefore the removal operation still becomes O(n) in worst case. I cannot formally present the analysis of the average case runtime complexity for this one.
I don’t know what’s the use, it’s just a puzzle that I came by and promised to post in the previous post.
Updated
18.08.2013: Added the An even better solution section. Some modifications in Complexity section and introduction text.
Phoxis 
NIce one :)
Thanks. I had to post this to complete the series.