Stacks & Queues

Stacks and Queues are two of the most fundamental data structures in computer science. They both store collections of elements, but differ in the order elements are added and removed.

Stack — LIFO (Last In, First Out): Think of a stack of plates. You add plates to the top and remove from the top. The last plate placed is the first one taken off.

Queue — FIFO (First In, First Out): Think of a line at a store. The first person in line is the first to be served. New people join at the back.

Key Terms:

• Push — Add an element to the top of a stack
• Pop — Remove the top element from a stack
• Enqueue — Add an element to the rear of a queue
• Dequeue — Remove the element from the front of a queue
• Peek — View the top (stack) or front (queue) element without removing it
• Top — The most recently added element in a stack
• Front / Rear — The first and last elements in a queue

A stack supports three core operations. Try them below with the interactive visualization:

push(item):          pop():               peek():
  top++                item = stack[top]    return stack[top]
  stack[top] = item    top--                // no removal
                       return item

All three operations run in O(1) constant time.

A queue supports three core operations. Items enter from the rear and leave from the front:

enqueue(item):           dequeue():              peek():
  queue[rear] = item       item = queue[front]     return queue[front]
  rear++                   front++                 // no removal
                           return item

All three operations run in O(1) constant time.

Queue State

Bracket matching is a classic application of stacks. Given an expression containing brackets (), [], {}, we verify that every opening bracket has a matching closing bracket in the correct order.

Algorithm: Scan left to right. Push opening brackets onto the stack. When you encounter a closing bracket, pop the stack and check if it matches. If the stack is empty at the end, the expression is valid.

Try these: {[()]} ((())) {[(]) ([)] (((

Add the same items to both a stack and a queue, then remove them to see how the order differs.

Browsers use two stacks: a back stack and a forward stack. Visit pages, then use back/forward to navigate.

1. You push A, B, C onto a stack (in that order), then pop twice. What is left on the stack?

2. You enqueue X, Y, Z into a queue, then dequeue once. What is at the front of the queue now?

3. Which data structure would you use to check if parentheses in an expression are balanced?