Unit 3: Stacks and Queues

LIFO and FIFO structures and their uses

Learning Outcomes
  • Describe the LIFO and FIFO principles
  • Implement stacks and queues with arrays and linked lists
  • Apply stacks to expression evaluation
  • Use queues for scheduling and traversal

Stack (LIFO)

A stack allows push, pop and top in O(1) time and follows the last-in first-out order. It underlies function call management, undo features, and balanced parenthesis checking.

int st[100], top = -1; st[++top] = x; // push int y = st[top--]; // pop

Queue (FIFO)

A queue inserts at the rear and removes from the front in first-in first-out order. A circular queue reuses freed slots and avoids wasted space, and queues drive scheduling and breadth-first search.

int q[100], front = 0, rear = 0; q[rear++] = x; // enqueue int y = q[front++]; // dequeue

Applications

Stacks convert infix expressions to postfix and evaluate them, and check balanced brackets, while the C++ STL supplies ready made std stack and std queue containers.

#include <stack> std::stack<int> s; s.push(10); s.pop();

Summary

This unit presented stacks and queues, their array and linked implementations, and key applications such as expression evaluation, scheduling and graph traversal.

Exercises

  • Implement a stack using a linked list.
  • Use a stack to check whether brackets in an expression are balanced.
  • Implement a circular queue with fixed capacity.
  • Explain how a queue is used in breadth-first search.
← PreviousCourse HomeNext →