【数据结构】栈和队列

        在计算机科学的世界里，数据结构是构建高效算法的基础。栈（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; } 队列结构体：定义了一个包含数组 items、队头指针 front 和队尾指针 rear 的结构体 Queue。初始化队列：initQueue 函数将队头指针初始化为 0，队尾指针初始化为 -1。判断队列状态：isEmptyQueue 函数判断队列是否为空，isFullQueue 函数判断队列是否已满。入队操作：enqueue 函数在队列未满时将元素添加到队尾。出队操作：dequeue 函数在队列不为空时移除并返回队头元素。查看队头元素：peekQueue 函数在队列不为空时返回队头元素。