By the end of this lesson, cadets will be able to:

1. Implement a stack ADT with push, pop, and peek operations on a linked list. (Outcome 2)
2. Implement a queue ADT with enqueue and dequeue operations on a linked list. (Outcome 2)
3. Choose between a stack and a queue based on the order a problem requires. (Outcomes 2, 3)

Complete before class. There is no Beej chapter for this lesson; the supplementary notes are your reading.

1. 1 Read the Lesson 31 supplementary notes.

   They walk through the stack, the queue, the back pointer, and the two empty-queue special cases. They are short and they are the reading; do not skip them.

2. 2 Predict the output.

   You push 3, then 5, then 8 onto a stack, then pop once. What comes back? Now enqueue the same three values onto a queue and dequeue once. What comes back?

   Click for the answer

   The stack returns 8 (last in, first out). The queue returns 3 (first in, first out). Same three inputs, opposite ends. That contrast is the whole lesson.

For two lessons you have built and modified a singly linked list. Today the node does not change at all; what changes is the rule about where you add and remove. That single rule turns a plain list into a stack or a queue, the two most common ADTs in everyday programming. The reference below covers what you will see in lecture and practice in the two widgets.

Slides

The Lesson 31 deck covers the stack, the queue, why the queue needs a back pointer, the two empty-queue special cases, and how to choose between the two ADTs. The slides are the spine of the lecture; the two widgets are where you practice.

Open Lesson 31 slides →

The stack: one end, last in first out

A stack tracks a single pointer, top, aimed at the most recently added node. push makes a new node, points its next at the old top, and becomes the new top. pop removes the top, moves the pointer down, and returns the value. peek reads the top without removing it. Every operation touches only the top, so all three are O(1) with no walk down the chain. This is the insert-at-head from Lesson 29, renamed.

void history_push(history_t *h, const char *url) {
    page_t *node = malloc(sizeof(page_t));
    node->url  = copy_string(url);   /* your own heap copy */
    node->next = h->top;             /* point at the old top */
    h->top     = node;               /* become the new top  */
    h->count++;
}

The queue: two ends, first in first out

A queue adds at the back and removes from the front. enqueue links a new node after the current back and advances the back to it. dequeue removes the front node and returns its value. peek reads the front. The split, adding at one end and removing at the other, is the entire difference from a stack. Same node, opposite access pattern.

Two moments need care. Enqueuing into an empty queue must set both front and back to the new node, since there is no old back to link after. And dequeuing the last node must reset back to NULL along with front; see the next subsection.

Why the queue keeps a back pointer

Removing from the front is easy: front is right there. Adding at the back is the problem. With only a front pointer, every enqueue would walk the whole chain to find the last node, which is O(n). A second pointer that always aims at the last node makes enqueue a single step, O(1). That is the whole reason a queue carries back.

The trap that follows: when the last node leaves and the queue empties, front becomes NULL but back is left pointing at the node you just freed. The queue looks empty by front, but the next enqueue writes through that dangling back and corrupts memory. When the queue empties, reset both ends.

char *dequeue(queue_t *q) {
    if (queue_is_empty(q)) return NULL;
    ticket_t *node = q->front;
    char *summary = node->summary;  /* hand value to caller */
    q->front = node->next;
    if (q->front == NULL) q->back = NULL;  /* reset back too! */
    q->count--;
    free(node);                      /* free node, not the string */
    return summary;
}

Choosing between them

Ask one question: in what order should things come back out? Most recent first, or "undo the last thing," means a stack. Oldest first, or "serve in arrival order," means a queue. The order the problem demands picks the structure. Both are O(1) on a linked list, so you are choosing on meaning, not speed.

Today's two labs make the contrast concrete: a browser Back button is a stack (most recent page first), and a help-desk ticket line is a queue (oldest ticket served first).

Lesson 31 introduces no new DFCS C Programming Standard section. The memory-cleanup rule (§8.5, free what you allocate) still applies and is checked in both labs with valgrind, but it was introduced earlier and is enforced here, not retaught. The full standard lives in the course Resources section.

Five things to do in class. Use the checklist to track your progress.

• Take Quiz 9. Covers linked lists from Lessons 29 and 30. Delivered through Git per your instructor's setup. 20 minutes max.
• Work through the stacks and queues walkthrough below. Seventeen guided tasks: drive a stack through push, pop, peek, and the empty guard, then a queue through enqueue and dequeue with both the back pointer and the empty-queue reset. About 25 minutes.
• Take the stack & queue self-check. Six questions on choosing an ADT, tracing LIFO and FIFO, the back pointer, and the empty-queue reset. About 10 minutes.
• Complete Lab 1: Browser Back Button (stack). Build a history stack with push, pop, peek, and the empty guards. Auto-graded through GitHub Classroom; worth 1 point.
  Accept Lab 1 on GitHub Classroom →
• Complete Lab 2: Help-Desk Ticket Queue (queue). Build a ticket queue with enqueue, dequeue, peek, the back pointer, and the empty-queue reset. Auto-graded through GitHub Classroom; worth 1 point.
  Accept Lab 2 on GitHub Classroom →

Stacks and Queues Walkthrough

Seventeen tasks across three sections. Type each operation at the prompt. The terminal shows what the operation did; the structure pane draws the node chain, the pointers tracking its ends, and the value each removal hands back.

Stack & Queue Self-Check

Six questions covering which ADT a problem needs, tracing LIFO and FIFO removal, why a queue keeps a back pointer, and what to reset when a queue empties. Pass at 70% or above; below that, replay the walkthrough and take the quiz again.

• Finish Lab 1 and Lab 2 if you did not complete them in class. Each is its own GitHub Classroom assignment with its own Gradescope submission; both are due before Lesson 32.
• Submit the Lesson 31 reflection in Blackboard. The reflection asks for the walkthrough and self-check completion codes and one short response from the question bank.
• Read the Lesson 32 supplementary notes. Lesson 32 takes the same linked structures you have been walking with loops and traverses them with recursion instead, where the call stack does the bookkeeping your loop made explicit.
• Your ethics discussion main post is due around now. Check the discussion board in Blackboard for the exact date and post your response applying two ACM Code of Ethics principles.
• Quiz 9 was today and covered Lessons 29 and 30. If you want to review it, your graded copy is in the course repo.