Project 6: Stack and Queue Applications

Build practical stack and queue utilities including expression parsing and BFS.

Quick Reference

Attribute Value
Difficulty Level 2: Intermediate
Time Estimate 1-2 weeks
Language C (Alternatives: Python, Java, Rust)
Prerequisites Project 5, LIFO/FIFO basics
Key Topics Stacks, queues, parsing, BFS

1. Learning Objectives

By completing this project, you will:

  1. Implement stack and queue data structures.
  2. Use stacks for expression parsing and evaluation.
  3. Use queues for breadth-first traversal.
  4. Compare array-based vs linked implementations.

2. Theoretical Foundation

2.1 Core Concepts

  • Stack (LIFO): Push/pop at one end, used for parsing and DFS.
  • Queue (FIFO): Enqueue/dequeue at opposite ends, used for BFS.
  • Shunting-yard algorithm: Convert infix to postfix using stacks.
  • Circular buffer: Efficient array-based queue implementation.

2.2 Why This Matters

Stacks and queues appear everywhere: parsing, scheduling, graph traversal, and systems programming. They are foundational for many algorithms.

2.3 Historical Context / Background

Dijkstra introduced the shunting-yard algorithm for expression parsing, a classic example of stack power.

2.4 Common Misconceptions

  • Misconception: Stacks are only for recursion. Reality: Parsing and undo are stack-heavy tasks.
  • Misconception: Queues are always linked lists. Reality: Circular buffers are common and fast.

3. Project Specification

3.1 What You Will Build

A small toolkit that includes:

  • A stack implementation
  • A queue implementation (array and linked)
  • An infix-to-postfix converter with evaluation
  • A BFS demo on a small graph

3.2 Functional Requirements

  1. Stack operations: push, pop, peek, is_empty.
  2. Queue operations: enqueue, dequeue, is_empty.
  3. Expression parsing: infix to postfix conversion.
  4. Expression evaluation: evaluate postfix expressions.
  5. BFS demo: traverse a graph using a queue.

3.3 Non-Functional Requirements

  • Reliability: Graceful handling of overflow/underflow.
  • Performance: O(1) amortized operations.
  • Usability: CLI to run parsing and BFS demos.

3.4 Example Usage / Output

$ ./stack-queue --expr "3 + 4 * 2"
postfix: 3 4 2 * +
result: 11

$ ./stack-queue --bfs --start A
BFS order: A B C D E

3.5 Real World Outcome

You will be able to parse arithmetic expressions and traverse graphs with BFS. The CLI will show postfix conversion and BFS order, confirming correct stack/queue usage.

4. Solution Architecture

4.1 High-Level Design

┌───────────┐     ┌──────────────┐     ┌─────────────┐
│ CLI Input │────▶│ Data Structs │────▶│ Demos       │
└───────────┘     └──────────────┘     └─────────────┘

4.2 Key Components

Component Responsibility Key Decisions
stack.c Stack operations Array vs linked
queue.c Queue operations Circular buffer
parser.c Shunting-yard + eval Operator precedence table
bfs.c Graph traversal demo Adjacency list

4.3 Data Structures

typedef struct {
    int items[STACK_MAX];
    int top;
} Stack;

4.4 Algorithm Overview

Key Algorithm: Shunting Yard

  1. Read tokens left to right.
  2. Use stack to manage operators by precedence.
  3. Output postfix expression.

Complexity Analysis:

  • Time: O(n)
  • Space: O(n)

5. Implementation Guide

5.1 Development Environment Setup

cc -Wall -Wextra -o stack-queue src/*.c

5.2 Project Structure

stack-queue/
├── src/
│   ├── stack.c
│   ├── queue.c
│   ├── parser.c
│   ├── bfs.c
│   └── main.c
├── tests/
└── README.md

5.3 The Core Question You’re Answering

“How do stacks and queues power real algorithms like parsing and BFS?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Operator precedence and associativity
  2. Circular buffer indexing
  3. Graph adjacency lists

5.5 Questions to Guide Your Design

  1. Will your stack and queue be generic or int-only?
  2. How will you tokenize expressions safely?
  3. How will you represent graphs for BFS?

5.6 Thinking Exercise

Convert 3 + 4 * 2 / ( 1 - 5 ) to postfix by hand.

5.7 The Interview Questions They’ll Ask

  1. Implement a stack with constant-time min.
  2. Use a queue to perform level-order traversal.
  3. Explain why BFS finds shortest paths in unweighted graphs.

5.8 Hints in Layers

Hint 1: Tokenizer first Parsing is easier once tokens are clean.

Hint 2: Operator precedence table Use a small array or switch statement.

Hint 3: Queue as circular buffer Maintain head and tail indices and wrap with modulo.

5.9 Books That Will Help

Topic Book Chapter
Stacks and queues “Data Structures the Fun Way” Ch. 4
Expression evaluation “The Art of Computer Programming” Vol. 1, 2.2.1

5.10 Implementation Phases

Phase 1: Data Structures (3-4 days)

Goals:

  • Implement stack and queue
  • Add basic tests

Tasks:

  1. Write push/pop and enqueue/dequeue.
  2. Add overflow/underflow checks.

Checkpoint: All data structure tests pass.

Phase 2: Parsing and Eval (3-4 days)

Goals:

  • Implement shunting-yard
  • Evaluate postfix expressions

Tasks:

  1. Build tokenizer.
  2. Add postfix evaluator.

Checkpoint: Correct results for sample expressions.

Phase 3: BFS Demo (2-3 days)

Goals:

  • Build graph representation
  • Run BFS from a start node

Tasks:

  1. Implement adjacency list.
  2. Print BFS order.

Checkpoint: BFS order matches expected.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Queue storage linked, circular array circular array Cache-friendly
Tokenizer manual, regex manual More control in C
Graph format adjacency list, matrix list Sparse-friendly

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Stack/queue ops push/pop/peek
Integration Tests Parsing flow infix -> postfix -> eval
Edge Case Tests Empty structures pop on empty

6.2 Critical Test Cases

  1. Expression with parentheses and mixed operators.
  2. BFS on disconnected graph.
  3. Queue wrap-around in circular buffer.

6.3 Test Data

Expression: 3 + 4 * 2
Graph: A-B, A-C, B-D

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong precedence Incorrect postfix Check operator table
Queue overflow Missing nodes in BFS Increase capacity or resize
Stack underflow Crashes on eval Validate operands

7.2 Debugging Strategies

  • Print tokens before parsing.
  • Log queue head/tail for wrap-around issues.

7.3 Performance Traps

Repeated string scanning in the tokenizer can make parsing O(n^2). Use a single pass.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add support for exponent operator.
  • Add an interactive REPL.

8.2 Intermediate Extensions

  • Add infix to prefix conversion.
  • Add generic stack using void pointers.

8.3 Advanced Extensions

  • Implement BFS shortest-path reconstruction.
  • Add expression variables and assignment.

9. Real-World Connections

9.1 Industry Applications

  • Compilers and interpreters use stacks for parsing.
  • BFS is used in routing, crawling, and shortest path in unweighted graphs.
  • bc: Unix calculator uses expression parsing.
  • Boost Graph Library: BFS implementations.

9.3 Interview Relevance

Stack and queue problems appear in almost every interview set.

10. Resources

10.1 Essential Reading

  • “Data Structures the Fun Way” by Jeremy Kubica - Ch. 4
  • “Algorithms, Fourth Edition” by Sedgewick - Section 1.3

10.2 Video Resources

  • Shunting-yard algorithm tutorials

10.3 Tools and Documentation

  • Compiler tokens and parsing references

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain LIFO vs FIFO with examples.
  • I can describe how shunting-yard works.
  • I can explain why BFS uses a queue.

11.2 Implementation

  • Stack and queue are correct and tested.
  • Expression parsing and evaluation work.

11.3 Growth

  • I can build additional stack/queue applications.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Stack and queue implementations
  • Infix to postfix conversion

Full Completion:

  • Expression evaluator and BFS demo

Excellence (Going Above and Beyond):

  • Shortest-path reconstruction
  • Generic data structure library

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.