Implement a stack using queue

Problem - Implement a stack using a queue

Solution

Method 1 - Implement a stack using 2 queues
We have already discussed the problems here.

Method 2 - Implement a stack using a single queue
Here are the operations(note that push operation is expensive)

push:

enqueue new element.
If n is the number of elements in the queue, then remove and insert element n-1 times.

pop:

dequeue

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  
+----+----+----+----+----+----+

Code:

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

Thanks.

See also