Which data structure is most commonly used to support Last-In-First-Out (LIFO)…

Concept

A stack is a linear abstract data type in which both insertion (push) and removal (pop) happen at a single end called the top. Because the element taken out is always the one added most recently, a stack enforces Last-In-First-Out (LIFO) ordering by definition.

Applying it to undo and redo

A text editor records each action on a stack. Every new edit is pushed on top; an UNDO pops the top element (the most recent action) and reverses it, then pushes that action onto a second redo stack so a later REDO can replay it.

1. Type "A", then type "B": the undo stack holds [insert A, insert B] with "insert B" sitting on top.

2. Press UNDO: pop "insert B" (the most recent action) and remove the B from the document; push "insert B" onto the redo stack.

3. Press UNDO again: pop "insert A" and remove the A, unwinding edits newest-first.

4. Press REDO: pop "insert A" from the redo stack and re-apply it, restoring the most recently undone action first.

Why the other structures do not fit

• A queue inserts at one end and removes from the other (First-In-First-Out), so it would unwind the oldest edit first, which is the wrong order for undo.

• A linked list is a general sequential container that allows insertion or removal at arbitrary positions; on its own it imposes no last-in-first-out discipline.

• A heap removes by priority (the smallest or largest key), not by how recently an element was inserted.

• A hash table locates items by key for fast lookup and keeps no record of the order in which entries were added.