**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.

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

## 0 comments:

## Post a Comment