Start learning →

Stacks and queues

Two structures that limit where items go in and come out, and the classic problems they solve: matching brackets, postfix expressions and fair waiting lines.

About 7 hours of study

Learning objectives

Lessons

  1. 1

    Stacks

    Last in, first out: a stack on an array with push, pop, overflow and underflow.

  2. 2

    Using stacks: brackets and postfix

    Check that brackets match, evaluate postfix expressions, and turn infix into postfix.

  3. 3

    Queues

    First in, first out: a circular array queue that wraps around, and a linked queue with front and rear.

Module practice

Module quiz

1. Which structure serves the item that has waited longest?
2. Push 4, push 9, pop, push 2, push 7, pop, pop. What is left on the stack?
3. What is the value of the postfix expression 5 1 2 + 4 * + 3 - ?
4. A circular queue has capacity 5, front = 3 and count = 4. Which indexes hold items?
5. What is the postfix form of a * b + c * d?
6. A bracket checker reads ( [ ) ]. At which character does it report an error?
7. A queue is built from two stacks, and items move across only when the second stack is empty. What do n enqueues and n dequeues cost in total?

‹ Arrays and linked listsTrees and heaps ›