Watch the full Stack & Queue lab lecture on YouTube:
Stack and Queue are fundamental linear data structures used to organize data based on strict ordering rules.
They are essential for understanding:
- Function calls and recursion (call stack)
- Undo / Redo operations
- Expression evaluation
- Task scheduling and buffering
- Real-world data flow problems
- Elements are added and removed from the same end called top
- Main operations:
push→ insert element at toppop→ remove element from toppeek→ view top elementisEmpty
📌 Real-world analogy:
A stack of plates — the last plate placed is the first removed.
Complexity:
- Time:
O(1)for push/pop - Space: depends on implementation
- Elements are added from the rear and removed from the front, queue processes elements in the same order they arrive.
- Main operations:
enqueue→ insert at reardequeue→ remove from frontpeekisEmpty
📌 Real-world analogy:
People standing in a line.
Complexity:
- Time:
O(1) - Space: depends on implementation
java-ds-lab-stack-queue/
│
├── README.md
│
├── src/
│ ├── examples/
│ │ ├── ArrayStack.java
│ │ ├── LinkedListStack.java
│ │ └── LinkedListQueue.java
│ │
│ ├── activities/
│ │ ├── ReverseSLLUsingStack.java
│ │ ├── SortStack.java
│ │ ├── PalindromeUsingStack.java
│ │ ├── ReverseQueueUsingRecursion.java
│ │ └── ReverseQueueUsingStack.java
│ │
│ └── chapters/
│ └── Lecture 05 - Stack & Queue.pdf
│
├── assignment/
│ └── README.md
│
└── .gitignoreAll files in src/examples/ were fully explained during the lecture, with diagrams, tracing, and dry runs.
Idea:
Implement stack behavior using an array and a top index.
Key points explained:
top = -1→ empty stack- Increment
topbefore insert - Decrement
topafter removal - Dynamic resizing when array is full
Stack Growth Visualization
flowchart TB
%% Stack operations (LIFO)
A["push(10)"] --> B["push(20)"] --> C["push(30)"]
C --> D["top → 30 (Last In)"]
D --> E["pop() → 30 (First Out)"]
%% Styling
classDef push fill:#e3f2fd,stroke:#1e88e5,stroke-width:2px,color:#0d47a1;
classDef top fill:#e8f5e9,stroke:#43a047,stroke-width:2px,color:#1b5e20;
classDef pop fill:#ffebee,stroke:#e53935,stroke-width:2px,color:#b71c1c;
class A,B,C push;
class D top;
class E pop;
📌 Important: This example teaches memory layout, overflow handling, and why arrays need resizing.
Idea: Replace array with nodes to avoid resizing.
Key concepts:
topalways points to head node- Push = insert at head
- Pop = remove head
Push Operation
flowchart LR
%% Stack push linking (LIFO behavior)
A["New Node (Top)"] --> B["Old Top"]
B --> C["Next Node"]
%% Styling
classDef newNode fill:#e3f2fd,stroke:#1e88e5,stroke-width:2px,color:#0d47a1;
classDef oldTop fill:#fff3e0,stroke:#fb8c00,stroke-width:2px,color:#e65100;
classDef next fill:#f3e5f5,stroke:#8e24aa,stroke-width:2px,color:#4a148c;
class A newNode;
class B oldTop;
class C next;
📌 Why linked list stack?
- No overflow
- Dynamic memory
- Clean pointer manipulation
Logic:
- Push each character
- Pop characters to reverse order
flowchart LR
subgraph Original_String
direction LR
A["M"] --> B["a"] --> C["r"] --> D["y"] --> E["a"] --> F["m"]
end
subgraph Reversed_String
direction LR
R1["m"] --> R2["a"] --> R3["y"] --> R4["r"] --> R5["a"] --> R6["M"]
end
%% Invisible edge to force left → right order
F -.-> R1
%% Styling
classDef original fill:#e3f2fd,stroke:#1e88e5,stroke-width:2px,color:#0d47a1;
classDef reversed fill:#ffebee,stroke:#e53935,stroke-width:2px,color:#b71c1c;
class A,B,C,D,E,F original;
class R1,R2,R3,R4,R5,R6 reversed;
Demonstrates pure LIFO behavior.
Goal: Validate expressions using stack.
Rules:
- Push opening brackets
- Pop and match on closing bracket
- Stack must be empty at the end
flowchart LR
%% Input stream
subgraph Input
direction LR
A["{"] --> B["("] --> C[")"] --> D["}"]
end
%% Stack operations
subgraph Stack_Operations
direction TB
P1["push '{'"] --> P2["push '('"]
P2 --> P3["pop '(' ✓ match )"]
P3 --> P4["pop '{' ✓ match }"]
end
%% Flow connection (invisible for ordering)
D -.-> P1
%% Styling
classDef input fill:#e3f2fd,stroke:#1e88e5,stroke-width:2px,color:#0d47a1;
classDef push fill:#e8f5e9,stroke:#43a047,stroke-width:2px,color:#1b5e20;
classDef pop fill:#ffebee,stroke:#e53935,stroke-width:2px,color:#b71c1c;
class A,B,C,D input;
class P1,P2 push;
class P3,P4 pop;
📌 Used in:
- Compilers
- Syntax validation
- Code editors
Structure:
front→ first elementrear→ last element
Enqueue / Dequeue Flow
flowchart LR
%% Queue structure (nodes as front and rear)
F["Front: Node1"] --> N2["Node2"] --> R["Rear: Node3"]
%% Queue operations
subgraph Queue_Operations
direction TB
ENQ["Enqueue Node4 → add at Rear"] --> ENQ2["Queue: Front → Node1 → Node2 → Node3 → Node4 → Rear"]
DEQ["Dequeue Front → remove Node1"] --> DEQ2["Queue: Front → Node2 → Node3 → Rear"]
end
%% Styling
classDef nodes fill:#e3f2fd,stroke:#1e88e5,stroke-width:2px,color:#0d47a1;
classDef enqueue fill:#e8f5e9,stroke:#43a047,stroke-width:2px,color:#1b5e20;
classDef dequeue fill:#ffebee,stroke:#e53935,stroke-width:2px,color:#b71c1c;
class F,N2,R nodes;
class ENQ,ENQ2 enqueue;
class DEQ,DEQ2 dequeue;
Operations:
Enqueue→ attach atrearDequeue→ remove fromfront
Technique:
- Dequeue
- Enqueue back
flowchart LR
%% Queue display operation without losing order
subgraph Queue
direction LR
F["Front: Node1"] --> N2["Node2"] --> N3["Node3"] --> R["Rear: Node4"]
end
%% Display operations
subgraph Display_Queue
direction TB
S1["Dequeue Node1 → Print Node1"] --> S2["Enqueue Node1 back at Rear"]
S2 --> S3["Dequeue Node2 → Print Node2"] --> S4["Enqueue Node2 back at Rear"]
S4 --> S5["Dequeue Node3 → Print Node3"] --> S6["Enqueue Node3 back at Rear"]
S6 --> S7["Dequeue Node4 → Print Node4"] --> S8["Enqueue Node4 back at Rear"]
end
%% Styling
classDef queue fill:#e3f2fd,stroke:#1e88e5,stroke-width:2px,color:#0d47a1;
classDef operation fill:#e8f5e9,stroke:#43a047,stroke-width:2px,color:#1b5e20;
classDef print fill:#fff3e0,stroke:#fb8c00,stroke-width:2px,color:#e65100;
class F,N2,N3,R queue;
class S1,S2,S3,S4,S5,S6,S7,S8 operation;
This reinforces queue rotation and FIFO understanding.
These tasks are intentionally incomplete and must be solved by students.
| Activity | Concept |
|---|---|
| Reverse SLL using Stack | Stack + Linked List |
| Sort Stack | Nested stack logic |
| Palindrome using Stack | String processing |
| Reverse Queue (Recursion) | Queue + recursion |
| Reverse Queue (Stack) | Stack–Queue interaction |
❗ No solutions here. Students must reason, design, and implement.
📌 Assignment questions are NOT written here.
To access the assignment:
- Open the
assignment/folder - Read
README.md - Watch the assignment video
- Follow submission instructions
This ensures fairness and prevents copying.
git clone https://github.com/Maryam-Skaik/java-ds-lab-stack-queue.git
cd java-ds-lab-stack-queue/src/examples
javac *.java
java ArrayStack- Always track top, front, rear
- Draw before coding
- Trace push/pop manually
- Stack problems → think LIFO
- Queue problems → think FIFO
After this lab, students will:
- Implement stack & queue from scratch
- Understand internal data flow
- Apply stack/queue to real problems
- Be ready for recursion internals and trees
This project is provided for educational use in the Java Data Structures Lab.