C
Stack and queue
Learn to implement stack and queue with linked list.
Stack and queue
A stack follows last-in first-out (LIFO): the last item added is the first removed. A queue follows first-in first-out (FIFO).
A stack has two core operations: push (add) and pop (remove). Implemented with an array, it keeps a top index; push does data[top++] = v;, pop returns data[--top]. A queue has enqueue and dequeue operations; head and tail are tracked separately. Stacks model function calls and backtracking; queues model tasks processed in order.
Array-based stack
A stack is implemented with a fixed-size array and a top index. top points to the next free slot; it starts at 0.
Definitions: typedef struct { int data[100]; int top; } Stack;. Init with void stack_init(Stack *s) { s->top = 0; }. Push with void stack_push(Stack *s, int v) { s->data[s->top++] = v; }. Pop with int stack_pop(Stack *s) { return s->data[--s->top]; }. top++ uses the value then increments; --top decrements then reads. So push uses top and increments, pop decrements then reads. Capacity checks are application-specific; skipped in this simple example.
Exercise Implement a stack
Write void stack_init(Stack *s): s->top = 0;. Write void stack_push(Stack *s, int v): s->data[s->top++] = v;. Write int stack_pop(Stack *s): return s->data[--s->top];. In main do Stack s; stack_init(&s);, stack_push(&s, 10);, stack_push(&s, 20);, printf("%d %d\n", stack_pop(&s), stack_pop(&s));.
Show example solution
#include <stdio.h>
#include <stdlib.h>
#define STACK_CAP 100
typedef struct {
int data[STACK_CAP];
int top;
} Stack;
void stack_init(Stack *s) { s->top = 0; }
void stack_push(Stack *s, int v) {
s->data[s->top++] = v;
}
int stack_pop(Stack *s) {
return s->data[--s->top];
}
int main(void) {
Stack s;
stack_init(&s);
stack_push(&s, 10);
stack_push(&s, 20);
printf("%d %d\n", stack_pop(&s), stack_pop(&s));
return 0;
}
Test yourself
-
Stack and queue
- stack
- LIFO
- queue
- FIFO
- push
- add
- pop
- remove
-
If a stack does push(10), push(20) then two pops, what's the output?
Show answer
20 10 — LIFO: last in (20) first out, then 10.
-
The push operation
void stack_push(Stack *s, int v) { s->data[s->____++] = v; }
Show answer
void stack_push(Stack *s, int v) { s->data[s->top++] = v; }
Next lesson: Summary - Dynamic data
