Data Structures Stacks and Queues 1

Question 1

Which real-world scenario best illustrates LIFO (Last In, First Out) behavior?

Accepted Answer

Undo/redo functionality in a text editor

Answer

Undo/redo works like a stack — the most recently performed action is always the first to be undone, exemplifying LIFO behavior.

Question 2

What is the time complexity of the push and pop operations on a stack?

Accepted Answer

O(1) for both

Answer

Both push and pop operate on the top of the stack only, requiring no traversal, making both O(1) constant time.

Question 3

How can a queue be implemented using two stacks with amortized O(1) enqueue and dequeue?

Accepted Answer

Enqueue to stack1; dequeue pops from stack2, transferring from stack1 when stack2 is empty

Answer

Elements are pushed to stack1 on enqueue; on dequeue, if stack2 is empty, all elements are moved from stack1 to stack2, reversing the order to produce FIFO behavior.

Question 4

What is a monotonic stack used for?

Accepted Answer

Maintaining elements in strictly increasing or decreasing order to solve next-greater-element problems

Answer

A monotonic stack maintains a sorted sequence by popping elements that violate the ordering invariant, enabling O(n) solutions to next-greater and next-smaller problems.

Question 5

Which algorithm uses a stack to evaluate postfix (Reverse Polish Notation) expressions?

Accepted Answer

Push numbers, pop two operands when an operator is found, push result

Answer

Postfix evaluation scans left to right: push operands onto a stack; when an operator is encountered, pop two operands, apply the operator, and push the result.

Data Structures Practice Test

Data Structures Practice Test

Data Structures Stacks and Queues 1