Lab 05 Stacks, Queues, and the Maze
This week we are exploring search algorithms: systematic ways to work through possible choices until we find a solution or determine that none exists. In Sudoku, you used a stack to remember your choices so that you could return to the most recent one when a choice did not work out. We will build on that idea by searching for a path through a maze.
Our search space will be a two-dimensional grid of Cells. Each cell is either open or blocked by an obstacle. From an open cell, we may move up, down, left, or right to another open cell. Starting at one cell, our goal is to find a path to a target cell.
As we search, we will discover possible next steps that we need to remember for later. We will compare two ways of deciding which choice to explore next:
- Depth-first search (DFS) uses a stack to remember pending choices and explore the most recently added choice first. Like your Sudoku solver, it pursues a direction before returning to earlier alternatives.
- Breadth-first search (BFS) keeps a queue of discovered choices waiting to be explored. It explores the oldest waiting choice first, working through nearby cells before cells farther away.
Both approaches must remember choices that are waiting. The difference is which waiting choice comes next: the newest for a stack, or the oldest for a queue.
You already have a singly linked list that implements the Stack interface. To make that same class work efficiently as a Queue, you will add a tail pointer: a reference to the last node in the list. This lets the queue add at the back without walking through every node. Once tail is part of LinkedList, you will also revisit your existing stack methods so that they keep this new reference correct.
- Review: Test the Stack behavior you used for Sudoku.
- Extend: Add tail, update your existing list methods, and implement the Queue interface.
- Prepare: Explore the provided maze classes and trace how a stack and a queue choose different cells.
- Apply in Project 05: Write a shared search algorithm, connect it to each interface, visualize the searches, and compare their results.
DFS and BFS will use separate linked-list objects. We are teaching one LinkedList class to support either role, rather than mixing both behaviors during a search.
Setup
Create Projects/Project05 in your personal Google Drive folder. Copy your own completed LinkedList.java from Project 4. Download the two course interfaces below. The provided Stack.java replaces your Project 4 copy; it has the same four methods. You will download the maze files and the tester in Task 5, after your list implements Queue.
Download now:
Use your own linked list. Do not substitute java.util.LinkedList, java.util.Queue, or a separate queue class. Your list should remain singly linked: each node has only a next link. The provided tests assume your Lab 4 Stack signatures: size, push, pop, and peek, with empty pop and peek returning null.
The most common bug in this lab is hard to see. Once your list has a tail field, a stack can push and pop the right items while tail points to the wrong node, or even to a node that was already removed. The printed output looks fine; the problem only appears later, when offer attaches a new item to that old node and the item is lost. So do not run your code and simply trust what prints. Decide first what should happen, including where head and tail should point, and then check it. The steps below build that habit.
- Read the task and the interface it uses (
Stack.java,Queue.java,Maze.java). Know what each method promises before you change anything. - Draw it. Sketch the nodes with
head,tail, and everynextarrow, before and after the operation. For Tasks 5–6, draw the grid and the frontier. Most pointer bugs show up on paper before they show up in code. - Predict the result. Write down what should print and where
headandtailshould point. The "expected X, got Y" tests only help if you decided X yourself. - Implement. Make the change in the right place. For the stack, that is the helper method that push or pop calls.
- Run the small tests in
main. These can seeheadandtaildirectly, so they catch a stack that returns the right items but leavestailwrong. - Write one test of your own for a case the given tests skip, such as offering after the queue empties or removing the last item by index.
- Run the tester last, as a final check, not as the way to find bugs.
Passing the tester isn't the finish line. At the checkpoint you will show your own tests and traces and explain your reasoning out loud.
Task 1 — Review Stack and programming to an interface REUSE
A stack is last in, first out (LIFO). The top is the head of your list. Push adds at the head; pop removes the head; peek reads the head. Each operation takes O(1) time. Keep your existing Stack behavior. In Task 3 you will revisit its implementation to keep the new tail field accurate.
Stack<Integer> stack = new LinkedList<Integer>();
stack.push(10);
stack.push(20);
System.out.println("peek: expected 20, got " + stack.peek());
System.out.println("pop: expected 20, got " + stack.pop());
System.out.println("size: expected 1, got " + stack.size());
System.out.println("pop: expected 10, got " + stack.pop());
System.out.println("empty pop: expected null, got " + stack.pop());
// TODO: Push 30 and call peek. Then print an expected-versus-got
// check that size is still 1 (peek must not remove anything).
Paste this code into the main method of your LinkedList.java and complete the TODO. Before running it, explain to yourself why each expected value is right; for example, why does the second pop return null? Then compile and run:
javac LinkedList.java Stack.java Queue.java java LinkedList
NullPointerException, your Project 4 remove() does not handle an empty list. Add a check at the top of that method that returns null when head is null. Both Stack and Queue promise null for an empty remove, and Task 3 builds on this same method.Stack<Integer> stack = new LinkedList<Integer>();
new LinkedList<Integer>() creates the object that stores the items. Stack<Integer> stack says that this variable will use that object through the Stack interface. Java allows this because LinkedList implements Stack.
Through stack, our code can call the methods listed in Stack.java: push, pop, peek, and size. The search algorithm can use those operations without knowing how the linked list's nodes are connected.
- Which Stack method adds a choice to remember?
- Which method returns and removes the most recently added choice?
- If LinkedList has a method to insert at a particular index, is that method listed in Stack.java? Why would a stack-based search need only the Stack methods?
Task 2 — Plan a queue before changing code DESIGN
A queue is first in, first out (FIFO), like a line of people waiting. offer adds at the back, poll removes the front, and peek reads the front without removing it. After offering A, B, C, polling must return A, B, C.
Open Queue.java. Its contract is:
public interface Queue<T> {
public int size();
public void offer(T item);
public T poll();
public T peek();
}
In this course interface, offer returns void. Empty poll and peek return null. Use non-null items in your tests so that null clearly signals an empty structure.
Ask Yourself — which end must be the front for O(1) operations?
- Draw four singly linked nodes and label head. Without a tail pointer, how many nodes must you visit to append?
- Add a tail pointer. Can you now append without traversal? Which links change?
- Suppose the tail were the front of the queue. To remove it, which node must become the new tail? Can you reach that predecessor directly from the old tail?
- Now make the head the front and the tail the back. Which pointers change for offer and poll?
- Explain why a tail pointer makes appending O(1), but does not make removing the last node O(1) in a singly linked list.
It is possible to reverse the orientation and still get FIFO behavior, but removal from the tail would cost O(n). For both queue operations to be O(1), use head as front and tail as back.
Task 3 — Add tail and keep head and tail correct MODIFY
Add a private tail field of the same node type as head. Use your actual node class name. Do not add backward links or a second size counter.
After every operation, the following rules must still be true. Computer scientists call rules like these invariants; here, that simply means keeping our references and count consistent with the actual list.
- Empty: size is 0, head is null, and tail is null.
- Nonempty: head points to the first node, tail points to the last, and tail's next is null.
- One item: head and tail point to the same node.
Audit every method that changes the list. Your method names may differ; match each row to your own code. Copy or reconstruction methods, if you have them, need the same audit.
| Method (typical name) | Used by | When does tail change? | The update |
|---|---|---|---|
constructor, clear() | everything | always | tail = null; |
add(T) / addFirst (insert at head) | push | only if the list was empty | if (size == 0) tail = newNode; |
remove() / removeFirst (remove head) | pop, later poll | only if the list is now empty | if (head == null) tail = null; (after removing; the empty-list check from Task 1 stays at the top) |
add(int index, T) | list code | inserting at index == size | tail = newNode; |
remove(int index) | list code | removing at index == size - 1 | tail = previous; (or null if now empty). This removal may still take O(n). |
peek, get, size, iterator | reading only | never | none |
Revisit the stack: a new field creates new responsibilities
DFS will use a Stack, and BFS will use a separate Queue. Neither search mixes stack and queue operations on its frontier. DFS still pushes and pops at the head and does not need tail to choose its next cell.
However, we are changing the LinkedList class, not just adding queue methods. Every object of that class now has a tail field. An invariant is a condition that must remain true after every completed operation. Our new invariant says that tail always identifies the last node, or is null when the list is empty. The existing stack methods must preserve it too.
A stack implementation that only reads head could still return the right items while leaving tail incorrect. Correct stack output alone therefore does not prove that the modified linked list is correct.
Walk through the boundary cases
Draw each row below. Letters name nodes, and the items are listed from the stack's top to its bottom. When head and tail both point to A, there is one node with two references to it, not two copies of A.
| Operation | Items, top to bottom | head | tail | What changes? |
|---|---|---|---|---|
| Start empty | None | null | null | Both references start null. |
| push A | A | A | A | The first node is also the last: set both references. |
| push B | B, A | B | A | Head changes; the last node stays A. |
| push C | C, B, A | C | A | Head changes; tail stays unchanged. |
| pop C | B, A | B | A | Head changes; tail stays unchanged. |
| pop B | A | A | A | Head reaches A; tail already points there. |
| pop A | None | null | null | The last node is gone: clear tail too. |
- push → your head-insertion method: when the list was empty, the new node is also the tail. (Table rows 2–3: push A sets tail; push B and C leave it alone.)
- pop → your head-removal method: when removal leaves head null, set tail to null. (Table row 7: pop A clears tail.)
- peek only reads, so it never changes either reference. Empty pop must leave both references null.
Because push and pop delegate, they inherit the fix. Do not duplicate pointer updates or update size twice. One size method serves both interfaces.
Ask Yourself — correct output or correct structure?
- If push A returns the expected result from peek, but tail is still null, which rule about tail is broken?
- If pop removes the final item but tail still points to that removed node, could a head-only stack test notice? Why is the LinkedList still incorrect?
- Why are these updates needed even though DFS never calls offer or poll?
- Which existing helper methods should you change so that push, pop, and other list operations reuse the correction?
Copy, paste, and complete: Paste the following tests inside your existing public static void main(String[] args) in LinkedList.java. Keep the tests inside the class, where they can read its private fields; do not make the fields public. These tests assume the fields are named head and tail. Adjust the names to match your list. Complete each TODO before checking the results.
// Task 3: Paste INSIDE main in LinkedList.java, after adding tail.
// If your first-node field has another name, replace "head" below.
LinkedList<String> stackList = new LinkedList<String>();
Stack<String> stackView = stackList;
System.out.println("empty pointers: expected true, got "
+ (stackList.head == null && stackList.tail == null));
stackView.push("A");
System.out.println("one node: expected true, got "
+ (stackList.head != null && stackList.head == stackList.tail));
Object originalBottom = stackList.tail; // Save the NODE reference, not its item.
// TODO: Push "B" using stackView.
System.out.println("two items: expected 2, got " + stackView.size());
System.out.println("same bottom: expected true, got "
+ (stackList.tail == originalBottom));
System.out.println("pop: expected B, got " + stackView.pop());
System.out.println("one node again: expected true, got "
+ (stackList.head != null && stackList.head == stackList.tail));
System.out.println("pop: expected A, got " + stackView.pop());
System.out.println("empty size: expected 0, got " + stackView.size());
System.out.println("empty pointers: expected true, got "
+ (stackList.head == null && stackList.tail == null));
// TODO: Push "C" onto the empty stack.
// TODO: Print an expected-versus-got check that head and tail
// point to the same non-null node.
// TODO: Peek, then check that size is still 1.
// TODO: Pop "C", then check that BOTH head and tail are null.
// TODO: Pop once more; expect null and size 0.
The two variables refer to the same object: stackView lets us exercise only Stack methods, while stackList lets this test code inspect its fields. No Queue methods are used. The saved originalBottom reference lets us verify that pushing and popping above A does not change the bottom node.
Run javac LinkedList.java Stack.java Queue.java, then java LinkedList. Compare every expected value with got. A correct pop result with an incorrect pointer check is still a bug. Fix the list before continuing.
Keep existing list method meanings unchanged. These corrections preserve the head-based stack's O(1) operations.
Test it: Draw and run empty → one node → two nodes → one node → empty → one node again. Also exercise your existing list operations: append by index then offer; remove the last item by index then offer; clear then offer. Write expected-versus-got tests using your own method signatures. Lab05Tester also tries add(int, T), remove(int), and clear() if your list has methods with those exact names. If yours are named differently, it skips them, and your own tests are the only check.
Task 4 — Make LinkedList implement Queue
public class LinkedList<T> implements Iterable<T>, Stack<T>, Queue<T>
Keep any other interfaces your class already implements. Compile and read the missing-method errors. Size and peek already satisfy both contracts: the stack's top and queue's front are both the head.
offer(T item): Create a node whose next is null. Handle the empty list; otherwise link the old tail to the new node. Make the new node the tail and increase size. No traversal is needed.poll(): Return null when empty. Otherwise remove and return the head item. Reuse your correct head-removal method if it handles size and tail properly.peek(): Reuse your stack method. It reads the head item without changing any pointers or size.
Paste these tests into LinkedList.main after your stack tests and complete the TODOs. Use your actual field names, as in Task 3.
// Task 4: Paste inside the same LinkedList main method.
// This is a NEW list, separate from the stack tested above.
LinkedList<String> queueList = new LinkedList<String>();
Queue<String> line = queueList;
line.offer("A");
line.offer("B");
System.out.println("peek: expected A, got " + line.peek());
System.out.println("size after peek: expected 2, got " + line.size());
System.out.println("poll: expected A, got " + line.poll());
// TODO: Offer "C" before removing the remaining items.
System.out.println("poll: expected B, got " + line.poll());
System.out.println("poll: expected C, got " + line.poll());
System.out.println("empty poll: expected null, got " + line.poll());
System.out.println("empty size: expected 0, got " + line.size());
System.out.println("empty pointers: expected true, got "
+ (queueList.head == null && queueList.tail == null));
// TODO: Offer "D" to the empty queue.
// TODO: Check that head and tail point to the same non-null node.
// TODO: Check peek returns "D" without changing size.
// TODO: Poll "D" and check BOTH pointers become null again.
Test the queue separately: Add tests of your own for offering after the queue becomes empty. Use a new LinkedList through a Queue variable and use only offer, poll, peek, and size. Check the same rules for head and tail in the empty and one-node cases that you checked for the stack. In the project, DFS will have its own Stack frontier and BFS its own Queue frontier. Both are instances of the same LinkedList implementation, and both must leave that implementation in a valid state.
Task 5 — Meet the maze READ AND EXPERIMENT
Download now: With Queue implemented, javac *.java now works.
getNeighbors. It builds its result with your offer and hands back your LinkedList. If Task 4 is wrong, the maze is wrong: neighbors come back missing, duplicated, or out of order.The provided Maze stores a rectangular Cell[][]. Each Cell stores its row, column, type (FREE or OBSTACLE), and a prev reference. The constructor's density is the independent probability that a cell is an obstacle; it does not guarantee an exact fraction of obstacles. It does not choose start and target cells.
getNeighbors(cell) returns in-bounds FREE neighbors in a fixed order: up, down, right, left. Diagonals are excluded. The cells it returns are the maze's own Cell objects, not copies. For now, think of prev as a field that reset clears. Task 6 uses it to mark discovered cells, and the project uses it to rebuild paths.
Run java Maze, then complete the TODO experiments in MazePractice.java. Use a 3×5 empty maze: predict the neighbors of corner (0,0) and of an interior cell, block one neighbor and predict again, print the maze to find your X (rows go down, columns go across), and verify that reset clears prev without removing obstacles. This is the same array-of-objects idea from earlier projects.
Ask Yourself — references, not copies
If a cell obtained from getNeighbors has its prev changed, does the cell in Maze change too? Why? Why must reset clear every Cell's prev before a second search on the same grid?
Task 6 — Trace the frontier by hand CONNECT
mark start discovered (start.prev = start); add start to frontier
while frontier is not empty:
cur = remove next cell from frontier
if cur is the target: done
for each open neighbor n of cur:
if n is undiscovered (n.prev == null):
mark n (n.prev = cur); add n to frontier
Only one thing changes between the two searches: which cell "remove next" picks.
- DFS (Stack, newest first): keeps following the most recent branch until it's stuck, then backs up to the latest unexplored choice, just like your Sudoku solver backtracking. It finds a path, but not necessarily the shortest one.
- BFS (Queue, oldest first): explores outward in rings: every cell 1 step away, then 2 steps, and so on. Because of that, the first time it reaches the target it has used the fewest possible moves.
We mark a cell when we add it, not when we remove it, so no cell enters the frontier twice. The start points to itself to mark it discovered without inventing an earlier cell.
Trace the loop above by hand, without a target. On a 3×3 all-free grid, start at (1,1). Mark it discovered and add it. Each step removes one frontier cell and adds its undiscovered neighbors in Maze's order. Record the first four removed cells with a stack, then restart and repeat with a queue. Mark cells as discovered when added, not when removed.
| Step | Cell removed | New cells added, in order | Frontier in next-removal order |
|---|---|---|---|
| 1 | (1,1) | Predict | Predict |
| 2–4 | Record each step | Record each step | Record each step |
Why does the last neighbor added become the next one removed by a stack? Why does a queue finish exploring the cells one step from the start before exploring those two steps away? The searcher processes stored Cell references; consecutive removed cells need not be adjacent.
Check your trace with your own list. Only after both hand traces are done, open MazePractice.java. printStackOrder runs the loop above with a Stack<Cell> frontier, prints the order cells are removed, and then draws the grid so you can see where those cells are. Run it and compare with your stack trace. Then complete printQueueOrder by copying printStackOrder and changing only what the frontier needs, and compare with your queue trace. Keep the removedAt and printGrid lines when you copy, so your queue version draws its grid too. If the output disagrees with your trace, find out which one is wrong before moving on.
There is no target yet: these methods only show the order in which cells are explored. The project adds a target, stops when it is found, and draws the path. The grid marks the start with S (it is always removed first), every other removed cell with the step at which it was removed, * if it is discovered and still waiting in the frontier, . if it has not been discovered, and X for an obstacle. Rows go down the page and columns go across, so (1,0) is row 1, column 0: one cell down from (0,0), not across. For example, a stack run from (0,0) on a 2×4 grid ends like this:
c0 c1 c2 c3
r0 S 2 3 4
r1 8 7 6 5
(S = start, number = removal step, * = waiting in frontier, . = undiscovered)
No target: this shows only the order cells are explored.
Compare the two grids: the stack's numbers run off in one direction, while the queue's spread out in rings around the start.
Ask Yourself — what actually changed?
- Which lines differ between
printStackOrderandprintQueueOrder? Everything else is copied. In Project 05 you will write the shared part once. - If you look up DFS online, you will often find a recursive version that marks a cell when it is removed. It visits cells in a different order than our stack version. Why might marking at removal let a cell enter the frontier more than once?
Run the basic checks
javac *.java java Lab05Tester java MazePractice
Lab05Tester runs every check, keeps going after a failure, and ends with a summary. Its sections follow the tasks:
| Section | What it checks |
|---|---|
| Tasks 1 and 3: Stack | LIFO behavior, empty pop and peek, and head, tail, and size after every push and pop |
| Task 4: Queue | FIFO behavior, emptying and refilling, and the same pointer checks after every offer and poll |
| Task 3: other list methods | tail after insert and remove by index and after clear, when those methods exist |
| Task 5: Maze | neighbor order, obstacles, reset, and iteration |
| Task 6: frontier order | your printQueueOrder, on a different grid from your hand trace |
head and tail. If yours have other names, the pointer checks are marked SKIP; rename the fields so they run. Fix the first FAIL first, because one pointer bug often causes several later failures. If a section runs for more than 10 seconds, the tester reports a likely infinite loop and stops. Passing every check does not prove O(1) performance or guarantee full credit; show your own tests and your offer/poll code as well.Lab checkpoint
Complete all six tasks. Show a TA or instructor your passing checks, your own expected-versus-got tests, your frontier traces, and the matching output from printStackOrder and printQueueOrder. Be ready to explain out loud, briefly, (1) why queue removal belongs at the head, (2) why existing stack methods must preserve tail even though DFS does not use it, (3) why Stack and Queue can share peek, and (4) why marking at discovery avoids duplicates. Then begin Project 05.
This is a required graded lab. After your checkpoint you may work on the project until the individual closed-book quiz; remain for the quiz. Nothing needs to be written up for the checkpoint; the Ask Yourself questions are for thinking and discussion. Make sure your code and tests are in Projects/Project05 before the lab ends.