This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/implement-stack-using-queues/.
Problem - Implement a stack using a queueSolution
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 elementn-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