Stack and queue
- C course
- Intermediate
- Lesson 74/116
- 5 min
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.
Practice 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));.
Starter code
#include <stdio.h>
#include <stdlib.h>
#define STACK_CAP 100
typedef struct {
int data[STACK_CAP];
int top;
} Stack;
// stack_init: top = 0
// stack_push: data[top++] = v
// stack_pop: return data[--top]
// main: init, push 10 and 20, print two pops
int main(void) {
// write here
return 0;
}Sample 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;
}Expected output
20 10
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Stack and queue
| Term | Meaning |
|---|---|
stack |
LIFO |
queue |
FIFO |
push |
add |
pop |
remove |
2 If a stack does push(10), push(20) then two pops, what's the output?
- 10 10
- 10 20
- 20 10 Correct answer
- 20 20
Explanation: LIFO: last in (20) first out, then 10.
3 The push operation
void stack_push(Stack *s, int v) { s->data[s->____++] = v; }void stack_push(Stack *s, int v) { s->data[s->top++] = v; }Explanation: data[top++] writes to top then increments.