Wednesday, March 19, 2014

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:
1. enqueue new element.
2. If `n` is the number of elements in the queue, then remove and insert element `n-1` times.
pop:
1. 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.