GATE CS 1997 Q4.7 — Arrays, Stacks and Queues

A stack operates on the Last-In-First-Out (LIFO) principle, meaning the element inserted last must be the first one to be removed.

In the given implementation:

• PUSH(C) is implemented as INSERT(Q, C, K).
• POP() is implemented as DELETEMIN(Q), which retrieves the element with the minimum key value.

To ensure that the most recently pushed element has the minimum key (so it gets popped first), each new element pushed must be assigned a key that is strictly smaller than the keys of all previously pushed elements.

For example, if we push elements $C_1, C_2, C_3$ in sequence, their assigned keys $K_1, K_2, K_3$ must satisfy:

This ensures that $C_3$ (the last pushed element with the minimum key $K_3$) is popped first by DELETEMIN(Q).

Thus, the keys chosen for successive push operations must be in strictly decreasing order.