Stack Riddle Answer: Plate Pile, Undo Button and LIFO Explained

The riddle from today's Short:

Main ek dher hu - plate ka dher. Jo sabse upar rakhi, wahi pehle uthegi. Aur tumhara undo button? Wo bhi mere bharose chalta hai. Bata kya hu?

Answer: a stack. A stack follows LIFO: Last In, First Out. The last item placed on top is the first item removed. The clue is the removal order, not the shape of the pile.

Why the plate clue means LIFO

Put plate A down first, B on A, and C on B. C is now on top. If you take plates only from the top, you remove C, then B, then A. You do not take A first merely because it arrived first.

That is the stack rule. Push adds an item to the top. Pop removes and returns the top item. Peek reads the top without removing it. These names describe operations; a stack can be built with an array, a linked list or another suitable structure.

Tiny Python proof: A, B, C comes out C, B, A

Python's list can act as a stack when we add with append() and remove with pop() at the end. Here the rightmost item is the top. This exact code was run before publication:

stack = []
stack.append('A')
stack.append('B')
stack.append('C')
print(stack[-1])
print(stack.pop(), stack.pop(), stack.pop())
print(stack)

Output:

C
C B A
[]

The first C comes from peek, so it is still there for the first pop. After three pops, the list is empty. Peeking did not secretly remove a plate.

Operation	Stack, bottom to top	Removed
push A	A	none
push B	A B	none
push C	A B C	none
pop	A B	C
pop	A	B
pop	empty	A

Calling pop() again on this empty Python list raises IndexError. Check that a stack is nonempty before taking its top item. Removing from an empty stack is called underflow in data-structure terminology.

Why undo is a stack-shaped idea

Imagine three recorded edits: type a word, make it bold, then change its color. Undo reverses the latest edit first: color, then bold, then typing. That is the same last-in, first-out order.

An undo system can keep previous states or commands in a history stack. Undo takes the most recent record and restores or reverses it. Redo can use a second stack. Real editors may group edits, limit history or use a more involved design; the riddle describes the usual LIFO model, not a claim about every app's internal code.

The other clue: who leaves in arrival order?

The answer to the Short's follow-up, "jo pehle aaya, wo pehle jaata hai", is a queue. It follows FIFO: First In, First Out. Enqueue A, B, C and dequeue them in the same order: A, B, C. A line at a counter is a simple queue example.

Do not confuse the two: a stack reverses the arrival order when you remove everything; a queue preserves it. In both examples, the order is set by the operations, not by alphabetic sorting.

Picture the top before you move a plate

After push A, B, C     After one pop
    +-------+             +-------+
top |   C   | -> C out top |   B   |
    +-------+             +-------+
    |   B   |             |   A   |
    +-------+             +-------+
    |   A   |              bottom
    +-------+
     bottom
Peek sees C; it leaves every plate in place.

The picture is a logical stack, not a memory layout. With a Python list, the right end is the top. If you instead remove index 0, you have changed the removal rule and the time cost.

Stack versus queue: choose the removal rule

Question	Stack	Queue
Rule	LIFO: latest arrival first	FIFO: earliest arrival first
Arrivals A, B, C	Pops C, B, A	Dequeues A, B, C
Useful model	Undo the latest edit	Serve the next waiting task
Python choice	list.append() and list.pop()	deque.append() and deque.popleft()

Undo and redo: two stacks, one current state

Before undo:
undo: ["", "A", "AB"] <- top
current: "ABC"
redo: []

UNDO: save current on redo, pop undo into current
undo: ["", "A"] <- top
current: "AB"
redo: ["ABC"] <- top

REDO: save current on undo, pop redo into current
undo: ["", "A", "AB"] <- top
current: "ABC"
redo: []

This example stores the state before each change in the undo stack. Undo does not simply discard the current text: it preserves it on the redo stack first. After a new edit, the old redo branch is cleared so it cannot overwrite the new work. A no-change edit is ignored.

Action	Current text	Undo, bottom to top	Redo, bottom to top
Edit A, AB, ABC	ABC	empty string, A, AB	empty
Undo	AB	empty string, A	ABC
Undo again	A	empty string	ABC, AB
Redo	AB	empty string, A	ABC
Edit ABX	ABX	empty string, A, AB	empty: old branch cleared

Run the complete history model

Run this standalone Python 3 script. The assertions check both stack boundaries, undo/redo transitions and branch clearing. The final sweep covers every binary sequence of length 0 through 6: 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 batches. It is a reproducible check of these cases, not a proof of every editor design.

# Complete-state snapshots for a tiny text editor.
class History:
    def __init__(self):
        self.text = ''
        self.undo_stack = []
        self.redo_stack = []
    def edit(self, text):
        if text == self.text:
            return
        self.undo_stack.append(self.text)
        self.text = text
        self.redo_stack.clear()
    def undo(self):
        if not self.undo_stack:
            return False
        self.redo_stack.append(self.text)
        self.text = self.undo_stack.pop()
        return True
    def redo(self):
        if not self.redo_stack:
            return False
        self.undo_stack.append(self.text)
        self.text = self.redo_stack.pop()
        return True

h = History()
assert not h.undo() and not h.redo()
h.edit('A'); h.edit('AB'); h.edit('ABC')
print('After edits:', h.text)
assert h.undo() and h.text == 'AB'
assert h.undo() and h.text == 'A'
print('After two undos:', h.text)
assert h.redo() and h.text == 'AB'
print('After redo:', h.text)
h.edit('ABX')
assert not h.redo() and h.text == 'ABX'
print('New edit clears redo:', h.text, h.redo_stack)
assert h.undo() and h.text == 'AB'
assert h.undo() and h.text == 'A'
assert h.undo() and h.text == ''
assert not h.undo()
print('All undos:', repr(h.text), '; boundary checks passed')

# Exhaustively verify small push-only batches and peek preservation.
from itertools import product
cases = 0
for length in range(7):
    for values in product('AB', repeat=length):
        s = []
        for value in values:
            s.append(value)
        if s:
            before = s[:]
            assert s[-1] == values[-1] and s == before
        removed = [s.pop() for _ in values]
        assert removed == list(reversed(values)) and not s
        cases += 1
print('LIFO/peek batch checks:', cases, 'passed')

Executed output:

After edits: ABC
After two undos: A
After redo: AB
New edit clears redo: ABX []
All undos: '' ; boundary checks passed
LIFO/peek batch checks: 127 passed

Time, space and common exam traps

Operation or design	Cost or caution
Python list push at end	O(1) amortized: occasional resize can cost O(n)
Python list pop at end; top lookup	O(1), if nonempty
Python list removal at index 0	O(n): remaining elements shift
n items stored in a stack	O(n) references, excluding payload size
Whole-text snapshots for undo	Total memory depends on all retained text lengths, not only the number of edits

The constant-time stack operations do not make a real undo action constant-time. Restoring a large document, copying state, applying a command or redrawing the screen can add work. This tiny model assigns immutable Python strings and keeps references to earlier values; it is not a full editor.

What is underflow? Trying to pop an empty stack. The model checks emptiness and returns False; an unguarded empty Python list pop raises IndexError.

What is overflow? Exceeding a stack implementation's capacity. A fixed-size array may reject a push when full. Python lists do not have that fixed capacity, but available memory is still finite.

Why clear redo after an edit? Redo describes the old future. Editing after undo creates a different future; retaining the old branch would not match this linear-history model.

Does every stack reverse all values? Only when those values are pushed and then all popped without other changes. Interleaved pushes and pops still follow LIFO at each pop, but need their own operation trace.

Exam questions and answers

What is a stack?
A linear abstract data type in which insertion and removal take place at the top, following LIFO.

What does LIFO stand for?
Last In, First Out. The newest pushed item is the next popped item.

Push A, B, C. What do three pops return?
C, B, A. The code and the operation table above agree.

How is peek different from pop?
Peek reads the top without removing it. Pop removes and returns it.

Name a stack application.
Undo history is a common model. Function-call tracking, expression evaluation and bracket matching are other stack applications.

How is a queue different?
A queue follows FIFO. With arrivals A, B, C, removals are A, B, C rather than C, B, A.

Want the longer lesson with postfix evaluation and circular queues? Read DSA Episode 4: stacks and queues.

Sources: Python's stack and queue tutorial; Real Python's stack and undo explanation. This is an original worked answer, not an official university answer key.