【数据结构】栈和队列

在计算机科学的世界里，数据结构是构建高效算法的基础。栈（Stack）和队列（Queue）作为两种基本且重要的数据结构，在软件开发、算法设计等众多领域都有着广泛的应用。今天，我们就来深入探讨一下栈和队列的奥秘。

1.栈（后进先出）

1.1栈的基本概念和结构

栈是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构。想象一下一摞盘子，你只能从最上面拿走盘子，也只能把新盘子放在最上面。栈就类似这摞盘子，最后放入栈中的元素会最先被取出。

1.2栈的操作

入栈（Push）：将一个元素添加到栈的顶部。这就好比在一摞盘子的最上面再放一个盘子。
出栈（Pop）：移除并返回栈顶部的元素。相当于从一摞盘子中拿走最上面的那个盘子。
查看栈顶元素（Peek）：返回栈顶部的元素，但不移除它。
判断栈是否为空（isEmpty）：检查栈中是否有元素。

1.3栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100// 定义栈结构体
typedef struct {int items[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack* s) {s->top = -1;
}// 判断栈是否为空
int isEmpty(Stack* s) {return s->top == -1;
}// 判断栈是否已满
int isFull(Stack* s) {return s->top == MAX_SIZE - 1;
}// 入栈操作
void push(Stack* s, int item) {if (isFull(s)) {printf("栈已满，无法入栈！\n");return;}s->items[++(s->top)] = item;
}// 出栈操作
int pop(Stack* s) {if (isEmpty(s)) {printf("栈为空，无法出栈！\n");return -1;}return s->items[(s->top)--];
}// 查看栈顶元素
int peek(Stack* s) {if (isEmpty(s)) {printf("栈为空，无栈顶元素！\n");return -1;}return s->items[s->top];
}int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);push(&s, 30);printf("栈顶元素: %d\n", peek(&s));printf("出栈元素: %d\n", pop(&s));printf("出栈后栈顶元素: %d\n", peek(&s));return 0;
}

栈结构体：定义了一个包含数组 items 和栈顶指针 top 的结构体 Stack。
初始化栈：initStack 函数将栈顶指针初始化为 -1，表示栈为空。
判断栈状态：isEmpty 函数判断栈是否为空，isFull 函数判断栈是否已满。
入栈操作：push 函数在栈未满时将元素添加到栈顶。
出栈操作：pop 函数在栈不为空时移除并返回栈顶元素。
查看栈顶元素：peek 函数在栈不为空时返回栈顶元素。

2.队列（先进后出）

2.1队列的概念和结构

2.2队列的操作

入队（Enqueue）：将一个元素添加到队列的尾部。类似于在排队的末尾加入一个人。
出队（Dequeue）：移除并返回队列头部的元素。就像排队的第一个人买到票后离开队伍。
查看队头元素（Peek）：返回队列头部的元素，但不移除它。
判断队列是否为空（isEmpty）：检查队列中是否有元素。

2.3队列的实现

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100// 定义队列结构体
typedef struct {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = 0;q->rear = -1;
}// 判断队列是否为空
int isEmptyQueue(Queue *q) {return q->rear < q->front;
}// 判断队列是否已满
int isFullQueue(Queue *q) {return q->rear == MAX_SIZE - 1;
}// 入队操作
void enqueue(Queue *q, int item) {if (isFullQueue(q)) {printf("队列已满，无法入队！\n");return;}q->items[++(q->rear)] = item;
}// 出队操作
int dequeue(Queue *q) {if (isEmptyQueue(q)) {printf("队列为空，无法出队！\n");return -1;}return q->items[(q->front)++];
}// 查看队头元素
int peekQueue(Queue *q) {if (isEmptyQueue(q)) {printf("队列为空，无队头元素！\n");return -1;}return q->items[q->front];
}int main() {Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);printf("队头元素: %d\n", peekQueue(&q));printf("出队元素: %d\n", dequeue(&q));printf("出队后队头元素: %d\n", peekQueue(&q));return 0;
}