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:

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.

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.

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

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?

  1. Draw four singly linked nodes and label head. Without a tail pointer, how many nodes must you visit to append?
  2. Add a tail pointer. Can you now append without traversal? Which links change?
  3. 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?
  4. Now make the head the front and the tail the back. Which pointers change for offer and poll?
  5. 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 byWhen does tail change?The update
constructor, clear()everythingalwaystail = null;
add(T) / addFirst (insert at head)pushonly if the list was emptyif (size == 0) tail = newNode;
remove() / removeFirst (remove head)pop, later pollonly if the list is now emptyif (head == null) tail = null; (after removing; the empty-list check from Task 1 stays at the top)
add(int index, T)list codeinserting at index == sizetail = newNode;
remove(int index)list coderemoving at index == size - 1tail = previous; (or null if now empty). This removal may still take O(n).
peek, get, size, iteratorreading onlynevernone

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.

OperationItems, top to bottomheadtailWhat changes?
Start emptyNonenullnullBoth references start null.
push AAAAThe first node is also the last: set both references.
push BB, ABAHead changes; the last node stays A.
push CC, B, ACAHead changes; tail stays unchanged.
pop CB, ABAHead changes; tail stays unchanged.
pop BAAAHead reaches A; tail already points there.
pop ANonenullnullThe last node is gone: clear tail too.

Ask Yourself — correct output or correct structure?

  1. If push A returns the expected result from peek, but tail is still null, which rule about tail is broken?
  2. 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?
  3. Why are these updates needed even though DFS never calls offer or poll?
  4. 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.

  1. 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.
  2. 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.
  3. 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.

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

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.

StepCell removedNew cells added, in orderFrontier in next-removal order
1(1,1)PredictPredict
2–4Record each stepRecord each stepRecord 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?

  1. Which lines differ between printStackOrder and printQueueOrder? Everything else is copied. In Project 05 you will write the shared part once.
  2. 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:

SectionWhat it checks
Tasks 1 and 3: StackLIFO behavior, empty pop and peek, and head, tail, and size after every push and pop
Task 4: QueueFIFO behavior, emptying and refilling, and the same pointer checks after every offer and poll
Task 3: other list methodstail after insert and remove by index and after clear, when those methods exist
Task 5: Mazeneighbor order, obstacles, reset, and iteration
Task 6: frontier orderyour printQueueOrder, on a different grid from your hand trace

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.

Begin Project 05 →