Scribd
Upload
5 views3 pages

Queue Implementation Using Stack

The document describes a method for implementing a queue using a single stack, outlining operations for ENQUEUE and DEQUEUE that maintain FIFO behavior. It details the process of reversing the stack to access the oldest element for dequeueing. Final examples illustrate the state of the stack after specific operations, showing the results of stack manipulations.

Uploaded by

dheeraj.23gcebcs235
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views3 pages

Queue Implementation Using Stack

The document describes a method for implementing a queue using a single stack, outlining operations for ENQUEUE and DEQUEUE that maintain FIFO behavior. It details the process of reversing the stack to access the oldest element for dequeueing. Final examples illustrate the state of the stack after specific operations, showing the results of stack manipulations.

Uploaded by

dheeraj.23gcebcs235
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Stack

A) Implementing a queue with a single stack (supports PUSH, POP, REVERSE)

Keep the stack so that the top = rear of the queue.


Then:

 ENQUEUE(x) = PUSH(x) (so enqueue is a single operation)

 DEQUEUE() = REVERSE; POP; REVERSE (three operations)

o REVERSE makes the bottom (oldest element, the queue front) become top

o POP removes it
o REVERSE restores original order of remaining elements

This gives FIFO behaviour.

Final answers

i. After 5 2 * 3 4 + → stack = [10, 7] (bottom→top, top = 7)


ii. After 5 2 * 3 4 + 5 2 (i.e., just after processing 5 2 *) → stack = [10, 7, 10] (top = 10)
iii. At end of evaluation → stack = [80]

You might also like