5 Stacks and Queues Free Online FlashCards

What access rule does a stack follow?

A stack follows last in, first out (LIFO): the most recently inserted element is removed first.

What access rule does a queue ordinarily follow?

A queue ordinarily follows first in, first out (FIFO): the earliest inserted element is removed first.

How do `push`, `pop`, and `peek` differ in a stack?

`push(x)` inserts `x` at the top, `pop()` removes and returns the top element, and `peek()` returns it without removing it.

How do `enqueue`, `dequeue`, and `front` operate on a queue?

`enqueue(x)` inserts at the rear, `dequeue()` removes and returns the front element, and `front()` or `peek()` inspects the front without removal.

What are underflow and overflow?

Underflow occurs when an element is removed from or examined in an empty structure. Overflow can occur when inserting into a full bounded structure.

Why use a circular buffer for an array-based queue?

A circular buffer lets queue indices wrap around, avoiding shifts of the remaining elements after each dequeue.

Why can dynamic-array insertion be O(1) amortized?

Geometric growth makes a sequence of dynamic-array insertions O(n) total, so each insertion is O(1) amortized despite occasional O(n) resizing.

Why does a linked-list queue maintain front and rear pointers?

A linked-list queue needs both front and rear pointers: front supports constant-time removal, while rear supports constant-time insertion.

What is the main cost of a naive shifting array queue?

A naive array queue can make dequeue O(n) because it shifts every remaining element toward the front after removal.

What is a deque?

A deque supports insertion, removal, and inspection at both ends, so it can function as either a queue or a stack.

How does a call stack manage nested function calls?

A call stack pushes an activation record when a function is called and pops it when the function returns, producing return order in LIFO sequence.

How can a stack check whether `([{}])` has matching delimiters?

Push each opening delimiter; when a closing delimiter appears, it must match the most recently pushed opening delimiter.