[中文版本](/posts/c教程/zh-CN/04-数据结构/037-Stacks and Queues with Structs)

You’ve learned how to build a linked list, now you’ll use that foundation to create two classic data structures: Stacks (LIFO, Last In, First Out) and Queues (FIFO, First In, First Out). Both are essential for real-world programs, from parsing expressions to managing tasks and kernel scheduling.

1. The Stack

A stack is like a pile of plates. You add to the top (push), and remove from the top (pop).

Operations:

• push(x)→ add an item to the top
• pop()→ remove the top item
• peek()→ look at the top item without removing it

Stack Implementation Using Linked List

Each stack node holds data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int value;
    struct Node *next;
} Node;
typedef struct {
    Node *top;
} Stack;
Stack* create_stack(void) {
    Stack *s = malloc(sizeof(Stack));
    s->top = NULL;
    return s;
}
void push(Stack *s, int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = s->top;
    s->top = n;
}
int pop(Stack *s) {
    if (!s->top) {
        printf("Stack underflow!\n");
        return -1;
    }
    Node *temp = s->top;
    int val = temp->value;
    s->top = temp->next;
    free(temp);
    return val;
}
int peek(const Stack *s) {
    return s->top ? s->top->value : -1;
}
void free_stack(Stack *s) {
    while (s->top) pop(s);
    free(s);
}
int main(void) {
    Stack *s = create_stack();
    push(s, 10);
    push(s, 20);
    push(s, 30);
    printf("Top: %d\n", peek(s));
    printf("Popped: %d\n", pop(s));
    printf("Popped: %d\n", pop(s));
    printf("Top now: %d\n", peek(s));
    free_stack(s);
    return 0;
}

Output:

Top: 30
Popped: 30
Popped: 20
Top now: 10

Why Use a Stack?

Stacks are used in:

• Function calls (the call stack)
• Undo/redo systems
• Parsing expressions (e.g., evaluating(2 + 3) * 4)
• Depth-first search (DFS) in graphs

2. The Queue

A queue is like a line at a store. You add to the back (enqueue), and remove from the front (dequeue).

Operations:

• enqueue(x)→ add to the end
• dequeue()→ remove from the front

Queue Implementation Using Linked List

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int value;
    struct Node *next;
} Node;
typedef struct {
    Node *front;
    Node *rear;
} Queue;
Queue* create_queue(void) {
    Queue *q = malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}
void enqueue(Queue *q, int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = n;
        return;
    }
    q->rear->next = n;
    q->rear = n;
}
int dequeue(Queue *q) {
    if (q->front == NULL) {
        printf("Queue underflow!\n");
        return -1;
    }
    Node *temp = q->front;
    int val = temp->value;
    q->front = temp->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(temp);
    return val;
}
void print_queue(const Queue *q) {
    for (Node *p = q->front; p != NULL; p = p->next)
        printf("%d ", p->value);
    printf("\n");
}
void free_queue(Queue *q) {
    while (q->front) dequeue(q);
    free(q);
}
int main(void) {
    Queue *q = create_queue();
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    printf("Queue: ");
    print_queue(q);
    printf("Dequeued: %d\n", dequeue(q));
    printf("Dequeued: %d\n", dequeue(q));
    printf("Remaining: ");
    print_queue(q);
    free_queue(q);
    return 0;
}

Output:

Queue: 1 2 3 
Dequeued: 1
Dequeued: 2
Remaining: 3

Stack vs Queue Summary

Feature	Stack	Queue
Access Order	LIFO (Last In, First Out)	FIFO (First In, First Out)
Main Operations	push / pop	enqueue / dequeue
Used For	Recursion, parsing, backtracking	Task scheduling, buffering
Example	Undo system	Printer jobs

Tiny Code Exercise: Dual Queue-Stack

Here’s a minimal snippet that lets you switch between stack and queue mode:

typedef enum { STACK_MODE, QUEUE_MODE } Mode;

You could use the same linked list logic but change whether new nodes are added at the head (stack) or tail (queue).

Why It Matters

Stack and queue behavior underlie every major system abstraction:

• CPU scheduling
• IO buffering
• Event loops
• Expression parsing
• Recursive algorithms

Building them in raw C solidifies your understanding of pointer-based data structures and memory ownership.

Try It Yourself

1. Implementis_empty() for both stack and queue.
2. Extend the queue to handle strings instead of ints.
3. Add a functionreverse_queue() using a stack.
4. Implement a “bounded queue” that has a fixed maximum size.
5. Write a small program simulating customer arrivals using a queue.

Stacks and queues are the control flow primitives of memory and time. Next, you’ll combine them with hashing and function pointers to build your own hash table, the basis for efficient lookups and symbol tables in C.