In the world of data structures in C language, arrays and linked lists provide us with the basic means of linear data storage. However, they can be inflexible and inefficient in certain specific scenarios—such as when we need to access data strictly in a “Last In First Out” or “First In First Out” order.
At this point, two classic and elegant linear data structures come into play: Stacks and Queues.
A stack follows the Last In First Out (LIFO) principle, like a stack of plates where the last one placed is the first one to be taken away; a queue follows the First In First Out (FIFO) principle, like a line for tickets where the first to arrive is the first to be served. Although their structures are simple, they are indispensable cornerstones in algorithm and system design, widely used in function calls, expression evaluation, task scheduling, network communication, and various other fields.
In this article, we will explain the core concepts, basic operations, C language implementation methods, and typical application scenarios of stacks and queues in a straightforward manner, helping you master these two fundamental yet powerful data structures.
1. Stack (Stack)
A stack is a data structure that follows the “Last In First Out” (LIFO) principle. It can be understood as a container from which you can only add or remove elements from the top.
1. Basic Operations of Stack
· Push: Add an element to the top of the stack.· Pop: Remove an element from the top of the stack.· Peek: View the top element of the stack.· IsEmpty: Check if the stack is empty.· Size: Get the number of elements in the stack.#include <stdio.h>#include <stdlib.h>#define MAX 5 // Maximum capacity of the stack// Stack structuretypedef struct Stack { int arr[MAX]; // Array to store stack elements int top; // Top pointer of the stack} Stack;// Initialize stackvoid initStack(Stack *s) { s->top = -1; // Initialize top pointer to -1, indicating the stack is empty}// Check if stack is fullint isFull(Stack *s) { return s->top == MAX - 1;}// Check if stack is emptyint isEmpty(Stack *s) { return s->top == -1;}// Pushvoid push(Stack *s, int value) { if (isFull(s)) { printf("Stack is full!\n"); } else { s->arr[++s->top] = value; printf("Pushed %d into stack\n", value); }}// Popint pop(Stack *s) { if (isEmpty(s)) { printf("Stack is empty!\n"); return -1; } else { return s->arr[s->top--]; }}// Get top elementint peek(Stack *s) { if (isEmpty(s)) { printf("Stack is empty!\n"); return -1; } else { return s->arr[s->top]; }}// Print elements in stackvoid display(Stack *s) { if (isEmpty(s)) { printf("Stack is empty!\n"); } else { printf("Stack elements: "); for (int i = 0; i <= s->top; i++) { printf("%d ", s->arr[i]); } printf("\n"); }}int main() { Stack stack; initStack(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); display(&stack); printf("Popped element: %d\n", pop(&stack)); display(&stack); printf("Top element: %d\n", peek(&stack)); return 0;}2. Explanation
1. initStack: Initializes the stack, setting the top pointer to -1.2. push: If the stack is not full, adds an element to the top.3. pop: If the stack is not empty, removes an element from the top.4. peek: Views the top element without removing it.5. display: Prints all elements in the stack.2. Queue (Queue)
A queue is a data structure that follows the “First In First Out” (FIFO) principle. You can think of it as a line of people where the first to join is the first to leave.
1. Basic Operations of Queue
· Enqueue: Add an element to the end of the queue.· Dequeue: Remove an element from the front of the queue.· Front: View the front element of the queue.· IsEmpty: Check if the queue is empty.· IsFull: Check if the queue is full.#include <stdio.h>#include <stdlib.h>#define MAX 5 // Maximum capacity of the queue// Queue structuretypedef struct Queue { int arr[MAX]; // Array to store queue elements int front; // Front pointer of the queue int rear; // Rear pointer of the queue} Queue;// Initialize queuevoid initQueue(Queue *q) { q->front = -1; q->rear = -1;}// Check if queue is fullint isFull(Queue *q) { return q->rear == MAX -1;}// Check if queue is emptyint isEmpty(Queue *q) { return q->front == -1 || q->front > q->rear;}// Enqueuevoid enqueue(Queue *q, int value) { if (isFull(q)) { printf("Queue is full!\n"); } else { if (q->front == -1) { // If the queue is empty, set front to 0 q->front = 0; } q->arr[++q->rear] = value; printf("Enqueued %d to queue\n", value); }}// Dequeueint dequeue(Queue *q) { if (isEmpty(q)) { printf("Queue is empty!\n"); return -1; // Return -1 indicates the queue is empty } else { int value = q->arr[q->front++]; if (q->front > q->rear) { // Reset when the queue is empty q->front = q->rear = -1; } return value; }}// Get front elementint front(Queue *q) { if (isEmpty(q)) { printf("Queue is empty!\n"); return -1; // Return -1 indicates the queue is empty } else { return q->arr[q->front]; }}// Print elements in queuevoid display(Queue *q) { if (isEmpty(q)) { printf("Queue is empty!\n"); } else { printf("Queue elements: "); for (int i = q->front; i <= q->rear; i++) { printf("%d ", q->arr[i]); } printf("\n"); }}int main() { Queue q; initQueue(&q); enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30); display(&q); printf("Dequeued element: %d\n", dequeue(&q)); display(&q); printf("Front element: %d\n", front(&q)); return 0;}2. Explanation
1. initQueue: Initializes the queue, setting the front and rear pointers to -1.2. enqueue: If the queue is not full, adds an element to the rear.3. dequeue: If the queue is not empty, removes an element from the front.4. front: Views the front element without removing it.5. display: Prints all elements in the queue.3. Summary
· Stack: Follows the Last In First Out principle, commonly used in function calls, depth-first search, etc.· Queue: Follows the First In First Out principle, commonly used in breadth-first search, task scheduling, etc.
· Stack is a Last In First Out (LIFO) data structure, with core operations being push and pop, simulating real-world logic such as function calls, undo operations, and bracket matching;
· Queue is a First In First Out (FIFO) data structure, with core operations being enqueue and dequeue, reflecting fairness and order principles in queuing, task scheduling, and message processing.
Although both are simple, they are the key entry points to understanding more complex algorithms (such as recursion, tree traversal, graph BFS/DFS) and system mechanisms (such as function call stacks, event loops, message queues).
Mastering stacks and queues not only allows you to quickly find concise and efficient solutions to specific problems but also lays a solid foundation for learning more advanced data structures and algorithms in the future.
The charm of data structures often lies in this “simple yet powerful” logic. Keep up the good work, comrades!