Abstract data types
A stack uses last-in, first-out (LIFO) ordering: push, pop and peek. A queue uses first-in, first-out (FIFO): enqueue and dequeue.
Real uses
A stack can model undo history and recursive calls. Queues are useful for print jobs and breadth-first graph traversal.
Binary search trees
A binary search tree organises keys so smaller keys occur in the left subtree and larger ones in the right (under a no-duplicate convention). Balanced trees can deliver O(log n) search, while an unbalanced tree may degrade to O(n).
Exam-style questions
1. Trace stack operations PUSH A, PUSH B, POP, PUSH C. Which item is at the top? 2. Explain why a queue is better suited than a stack for fair printer-job order. 3. Describe a circumstance where a BST becomes inefficient.
Suggested answers
1. C. 2. FIFO serves earlier submissions first. 3. Inserting sorted data into a simple unbalanced tree may create a chain, giving O(n) search.