The puzzle is to implement basic stack operations with using only basic queue operations. That is, a queue object is given, we need construct a wrapper for the stack functions, push, pop, which will only use the queue object as its storage, and naturally will have to use the queue operations.

This can be done using only one queue object. Although either the push or the pop complexity will no more be O(1).

### The Idea

The idea is pretty simple. We start with an empty queue. For the `push` operation we simply insert the value to be pushed into the queue. The `pop` operation needs some manipulation. When we need to `pop` from the stack (simulated with a queue), first we get the number of elements in the queue, say `n`, and remove `(n-1)` elements from the queue and keep on inserting in the queue one by one. That is, we remove the front element from the queue, and immediately insert into the queue in the rear, then we remove the front element from the queue and then immediately insert into the rear, thus we continue upto `(n-1)` elements. Then we will perform a remove operation, which will actually remove the `n ^{th}` element of the original state of the queue, and return. Note that the

`n`element in the queue is the one which was inserted last, and we are returning it first, therefore it works like a

^{th}`pop`operation (Last in First Out). The idea is shown below.

#### Push pseudocode

void push (queue_t q) { queue.insert (element); }

#### Pop pseudocode

element_type pop (void) { n = queue.element_count (); for (i from 0 to n - 2) // Only (n-1) elements 0 to (n-2) { queue_element = queue.remove (); queue.insert (queue_element); } element = queue.remove (); return element; }

Note that in the `pop` process, because we are inserting the first `(n-1)` elements in the queue in the same order we are removing, after the `for` loop termination in `pop` the state of the queue would have the last element in the queue at the font, and the remaining elements will maintain the same order which they had before the execution of the `for` loop. At this point we are simply removing the queue’s first element, which happens to be *actually* the last element in the original state of the queue, is removed and sent. After this the queue has the same elements in the same order except the last element. Which is exactly the behaviour we wanted.

Here is a simple diagram. Assume that the queue representation in the diagram has infinite length, and implemented as a linear queue (not circular) for simplicity.

/** PUSH operation **/ front,rear | v +----+----+----+----+----+----+ | 1 | | | | | | push (1) : insert (1) +----+----+----+----+----+----+ front rear | | v V +----+----+----+----+----+----+ | 1 | 2 | | | | | push (2) : insert (2) +----+----+----+----+----+----+ front rear | | v V +----+----+----+----+----+----+ | 1 | 2 | 3 | 4 | | | push (3), push (4) : insert (3), insert (4) +----+----+----+----+----+----+

/** POP operation **/ initial: front rear | | v V +----+----+----+----+----+----+ | 1 | 2 | 3 | 4 | | | +----+----+----+----+----+----+ popping 4 elements present. We will remove first 3 elements and immediately insert them as follows. front rear | | v V +----+----+----+----+----+----+----+----+ | | 2 | 3 | 4 | 1 | | | | queue.insert (queue.remove ()); +----+----+----+----+----+----+----+----+ //first element front rear | | v V +----+----+----+----+----+----+----+----+ | | | 3 | 4 | 1 | 2 | | | queue.insert (queue.remove ()); +----+----+----+----+----+----+----+----+ //second element front rear | | v V +----+----+----+----+----+----+----+----+ | | | | 4 | 1 | 2 | 3 | | queue.insert (queue.remove ()); +----+----+----+----+----+----+----+----+ //third element front rear | | v V +----+----+----+----+----+----+----+----+ | | | | | 1 | 2 | 3 | | return (queue.remove ()); +----+----+----+----+----+----+----+----+ //return required element 4 At this point we have popped the last inserted element, and the queue holds the elements in correct order except the element 4 removed.

Now we go into the implementation, which is pretty simple.

### Sourcecode

#include <stdio.h> #include <stdlib.h> /* Queue structure */ #define QUEUE_EMPTY_MAGIC 0xdeadbeef typedef struct _queue_t { int *arr; int rear, front, count, max; } queue_t; /* Queue operation function prototypes */ queue_t *queue_allocate (int n); void queue_insert (queue_t * q, int v); int queue_remove (queue_t * q); int queue_count (queue_t * q); int queue_is_empty (queue_t * q); /* NOTE: Here is the stuff we are interested in */ /* Simulated stack operations START */ /* NOTE: passing the queue object, on which we will only operate the * queue operations. */ void stack_push (queue_t * q, int v) { queue_insert (q, v); } int stack_pop (queue_t * q) { int i, n = queue_count (q); int removed_element; for (i = 0; i < (n - 1); i++) { removed_element = queue_remove (q); queue_insert (q, removed_element); /* same as below */ //queue_insert (q, queue_remove (q)) } removed_element = queue_remove (q); return removed_element; } int stack_is_empty (queue_t * q) { return queue_is_empty (q); } int stack_count (queue_t * q) { return queue_count (q); } /* Simulated stack operations END */ /* Queue operations START */ int queue_count (queue_t * q) { return q->count; } queue_t * queue_allocate (int n) { queue_t *queue; queue = malloc (sizeof (queue_t)); if (queue == NULL) return NULL; queue->max = n; queue->arr = malloc (sizeof (int) * n); queue->rear = n - 1; queue->front = n - 1; return queue; } void queue_insert (queue_t * q, int v) { if (q->count == q->max) return; q->rear = (q->rear + 1) % q->max; q->arr[q->rear] = v; q->count++; } int queue_remove (queue_t * q) { int retval; /* magic number if queue is empty */ if (q->count == 0) return QUEUE_EMPTY_MAGIC; q->front = (q->front + 1) % q->max; retval = q->arr[q->front]; q->count--; return retval; } int queue_is_empty (queue_t * q) { return (q->count == 0); } /* Queue operations END */ /* For demo */ void queue_display (queue_t * q) { int i = (q->front + 1) % q->max, elements = queue_count (q); while (elements--) { printf ("[%d], ", q->arr[i]); i = (i >= q->max) ? 0 : (i + 1); } } #define MAX 128 int main (void) { queue_t *q; int x, select; /* Static allocation */ q = queue_allocate (MAX); do { printf ("\n[1] Push\n[2] Pop\n[0] Exit"); printf ("\nChoice: "); scanf (" %d", &select); switch (select) { case 1: printf ("\nEnter value to Push:"); scanf (" %d", &x); /* Pushing */ stack_push (q, x); printf ("\n\n__________________________\nCurrent Queue:\n"); queue_display (q); printf ("\n\nPushed Value: %d", x); printf ("\n__________________________\n"); break; case 2: /* Popping */ x = stack_pop (q); printf ("\n\n\n\n__________________________\nCurrent Queue:\n"); queue_display (q); if (x == QUEUE_EMPTY_MAGIC) printf ("\n\nNo values removed"); else printf ("\n\nPopped Value: %d", x); printf ("\n__________________________\n"); break; case 0: printf ("\nQutting.\n"); return 0; default: printf ("\nQutting.\n"); return 0; } } while (1); return 0; }

This code is basically divided in three parts. One is a hand made implementation of a circular queue of integers. Next the stack operations using the queue, and a demo driver which will demonstrate the code interactively. In the code, the stack simulating functions are highlighted. The stack empty and stack element count functions are implemented here with the queue functions. Although it looks a bit messy but i couldn’t stop myself writing the C code and post, although a CPP implementation would have been cleaner. Note that the implementation considers that the queue (stack) 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. Thanks to Subhendu Bera for writing it for me.

#include <iostream> #include <queue> using namespace std; template <class T> class mystack { private: queue <T> Q; public: void ms_push (T data); T ms_pop (); }; template <class T> void mystack <T>::ms_push (T data) { Q.push (data); } template <class T> T mystack <T>::ms_pop () { T n, temp; n = Q.size (); for (int i = 0; i < (n - 1); i++) { temp = Q.front (); Q.pop (); Q.push (temp); /* Same as below */ //Q.push (Q.pop ()); } temp = Q.front (); Q.pop (); return temp; }

### The Other way

The other way is just the opposite. When pushing the element, instead of directly inserting it in the queue we can insert a new element in the queue and then if there are `n` elements in the queue, then we remove and insert `(n-1)`. In this case while popping we simply return the first element. Here is what i am trying to say:

#### Pop pseudocode

int stack_pop (queue_data *q) { return queue_remove (q); }

#### Push pseudocode

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)); } }

Same stuff is in here in my answer: http://stackoverflow.com/questions/688276/implement-stack-using-two-queues

Not posting the code for this one.

### Complexity

Clearly, if we do the dequeue, enqueue operation in the `pop` function, then it will have a execution growth upperbound of `O(n)` where `n` is the length of the queue, and the `push` operation will have `O(1)` time bound. The reverse is valid for the “Other Method”.

What’s the use? I don’t know, it’s just a puzzle that i came by.

What about the reverse, that is implementing a queue with a stack? I will post it soon as i get some time (The ASCII art and making sure things work is *pain*).

Check out the new post which does the opposite: Implement queue using stack

Awesome Work.. Keep it up, The thing I like the most was the way you showed in a pictoral fashion. :)

The ASCII pictures are a bit time consuming to draw, but looks good, and also the purpose is achieved to describe the stuff. Good to know you liked the post. Thanks for stopping by the blog.

same.. liked the ASCII draw of pics

Thanks @vaibhavvatts !

Wow, oh my gosh. Sorry, I didn’t grasp it all but I’m just really impressed by your explanations. This is heavy going stuff to me! But I’ve never seen a blog like it. Excellent stuff!

very nifty solution thanks!!!

Liked this work..I remember we used to solve this problem in B.Sc 1st Yr. Very frequently asked question. And i believe Stack implementation using a queue is frequently required than the other one due to memory problems(Overlapping memory zones). When a queue is allocated,its front and rear when given a limit and we can insert and delete in a circular fashion but memory contraints are also given(without using memory overlapping zones) then this is generally used. Since stack has a problem of colliding with instruction code and deleting that too…the same reason for keeping its index decreasing. This is the use Arjun that i had thought of long back.

Couldn’t understand what the “overlapping memory zones” means, but the design is completely independent of the implementation, as the stack push and pop operations are implemented using queue ADT functions. Whatever implementation be it for the queue, if it conforms with the behaviour then the stack operations, should work.

Yes it is a frequently asked problem in undergraduate CS courses.

Nice implementation in C# , Stack using queues

http://onestopinterviewprep.blogspot.com/2014/05/stacks-using-queues.html

Reblogged this on Vaibhav Vats and commented:

Implementing a stack using only One queue.

i need a source code for python plz can u send me