数据结构之栈和队列

ops/2025/1/8 19:27:07/

数据结构之栈和队列

  • 数据结构之栈和队列
    • 数据结构之栈（Stack）
      • 1. 栈的定义
      • 2. 栈的存储结构
        • 2.1 顺序存储实现
        • 2.2 链式存储实现
      • 3. 时间复杂度
      • 4. 栈的应用
    • 数据结构之队列（Queue）
      • 1. 队列的定义
      • 2. 队列的存储结构
        • 2.1 顺序存储实现
        • 2.2 链式存储实现
      • 3. 队列的变种
        • 3.1 双端队列（Deque）
        • 3.2 循环队列（Circular Queue）
      • 4. 队列的复杂度分析
      • 5. 队列的应用

数据结构之栈和队列

数据结构之栈（Stack）

1. 栈的定义

栈（Stack）是一种特殊的线性数据结构，遵循“后进先出”（LIFO, Last In First Out）的原则。也就是说，最后压入栈中的元素最先被弹出。栈可以被看作是一个有序集合，其操作主要包括添加（压栈）和移除（弹栈）元素。

栈的基本操作：

  • 压栈（Push）：将一个元素添加到栈顶。
  • 弹栈（Pop）：从栈顶移除并返回一个元素。
  • 查看栈顶元素（Peek/Top）：返回栈顶的元素，但不移除它。
  • 判断栈是否为空（IsEmpty）：检查栈中是否有元素。
  • 获取栈的大小（Size）：返回栈中元素的数量。

2. 栈的存储结构

栈可以通过顺序存储（数组）或链式存储（链表）两种方式实现。

2.1 顺序存储实现

使用数组实现栈的顺序存储。

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 定义栈的最大容量typedef struct {int data[MAX_SIZE]; // 存储栈元素int top;            // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = -1; // 栈为空时，栈顶指针为 -1
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == -1;
}// 判断栈是否满
int isFull(Stack *s) {return s->top == MAX_SIZE - 1;
}// 压栈
void push(Stack *s, int value) {if (isFull(s)) {printf("栈满，无法压栈！\n");return;}s->data[++s->top] = value; // 先增加栈顶指针，然后赋值
}// 弹栈
int pop(Stack *s) {if (isEmpty(s)) {printf("栈空，无法弹栈！\n");return -1; // 返回一个错误值}return s->data[s->top--]; // 返回栈顶元素，然后减少栈顶指针
}// 查看栈顶元素
int peek(Stack *s) {if (isEmpty(s)) {printf("栈空，无法查看栈顶元素！\n");return -1; // 返回一个错误值}return s->data[s->top];
}// 测试栈的功能
int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);push(&s, 30);printf("栈顶元素: %d\n", peek(&s)); // 输出: 30while (!isEmpty(&s)) {printf("弹栈元素: %d\n", pop(&s));}pop(&s); // 尝试从空栈弹栈return 0;
}
2.2 链式存储实现

使用链表来实现栈的链式存储。

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
typedef struct Node {int data;struct Node *next;
} Node;// 栈结构
typedef struct {Node *top; // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack *s) {s->top = NULL;
}// 判断栈是否为空
int isEmpty(Stack *s) {return s->top == NULL;
}// 压栈
void push(Stack *s, int value) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = value;newNode->next = s->top; // 新节点指向原栈顶s->top = newNode; // 更新栈顶
}// 弹栈
int pop(Stack *s) {if (isEmpty(s)) {printf("栈空，无法弹栈！\n");return -1; // 返回一个错误值}Node *temp = s->top; // 临时保存当前栈顶int poppedValue = temp->data;s->top = s->top->next; // 更新栈顶free(temp); // 释放旧栈顶的内存return poppedValue;
}// 查看栈顶元素
int peek(Stack *s) {if (isEmpty(s)) {printf("栈空，无法查看栈顶元素！\n");return -1; // 返回一个错误值}return s->top->data;
}// 测试栈的功能
int main() {Stack s;initStack(&s);push(&s, 10);push(&s, 20);push(&s, 30);printf("栈顶元素: %d\n", peek(&s)); // 输出: 30while (!isEmpty(&s)) {printf("弹栈元素: %d\n", pop(&s));}pop(&s); // 尝试从空栈弹栈return 0;
}

3. 时间复杂度

所有基本操作的时间复杂度均为 O(1)：

  • 插入、删除仅涉及栈顶的操作，无需遍历。

4. 栈的应用

栈在计算机科学中有许多重要的应用，包括但不限于：

  1. 函数调用管理：程序执行时的函数调用和返回过程使用栈来存储局部变量和返回地址。
  2. 表达式求值：在计算器中，栈被用于解析和计算表达式（如中缀表达式转换成后缀表达式）。
  3. 括号匹配：检查表达式中的括号是否匹配（如 (), {}, []）。
  4. 深度优先搜索（DFS）：树或图的深度优先遍历可以使用栈来实现。
  5. 撤销操作：在文本编辑器中，用户的操作可以通过栈来管理，以实现撤销功能。

数据结构之队列（Queue）

1. 队列的定义

队列（Queue）是一种特殊的线性数据结构，遵循“先进先出”（FIFO, First In First Out）的原则。也就是说，最先加入队列的元素最先被移除。队列可以看作是一个有序集合，它的操作主要包括添加（入队）和移除（出队）元素。

队列的基本操作：

  • 入队（Enqueue）：将一个元素添加到队列的尾部。
  • 出队（Dequeue）：从队列的头部移除并返回一个元素。
  • 查看队头元素（Front/Peek）：返回队列头部的元素，但不移除它。
  • 判断队列是否为空（IsEmpty）：检查队列中是否有元素。
  • 获取队列的大小（Size）：返回队列中元素的数量。

2. 队列的存储结构

队列可以通过顺序存储（数组）或链式存储（链表）两种方式实现。

2.1 顺序存储实现

使用数组实现队列的顺序存储。

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 定义队列的最大容量typedef struct {int data[MAX_SIZE]; // 存储队列元素int front;          // 队头指针int rear;           // 队尾指针
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = 0; // 队头指针初始化为 0q->rear = 0;  // 队尾指针初始化为 0
}// 判断队列是否为空
int isEmpty(Queue *q) {return q->front == q->rear;
}// 判断队列是否满
int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}// 入队
void enqueue(Queue *q, int value) {if (isFull(q)) {printf("队列满，无法入队！\n");return;}q->data[q->rear] = value; // 将元素添加到队尾q->rear = (q->rear + 1) % MAX_SIZE; // 更新队尾指针
}// 出队
int dequeue(Queue *q) {if (isEmpty(q)) {printf("队列空，无法出队！\n");return -1; // 返回一个错误值}int value = q->data[q->front]; // 获取队头元素q->front = (q->front + 1) % MAX_SIZE; // 更新队头指针return value;
}// 查看队头元素
int front(Queue *q) {if (isEmpty(q)) {printf("队列空，无法查看队头元素！\n");return -1; // 返回一个错误值}return q->data[q->front];
}// 测试队列的功能
int main() {Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);printf("队头元素: %d\n", front(&q)); // 输出: 10while (!isEmpty(&q)) {printf("出队元素: %d\n", dequeue(&q));}dequeue(&q); // 尝试从空队列出队return 0;
}
2.2 链式存储实现

使用链表实现队列的链式存储。

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
typedef struct Node {int data;struct Node *next;
} Node;// 队列结构
typedef struct {Node *front; // 队头指针Node *rear;  // 队尾指针
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = NULL;q->rear = NULL;
}// 判断队列是否为空
int isEmpty(Queue *q) {return q->front == NULL;
}// 入队
void enqueue(Queue *q, int value) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (isEmpty(q)) {q->front = newNode; // 如果队列为空，队头和队尾都指向新节点} else {q->rear->next = newNode; // 将新节点链接到队尾}q->rear = newNode; // 更新队尾指针
}// 出队
int dequeue(Queue *q) {if (isEmpty(q)) {printf("队列空，无法出队！\n");return -1; // 返回一个错误值}Node *temp = q->front; // 临时保存当前队头int value = temp->data;q->front = q->front->next; // 更新队头指针if (q->front == NULL) { // 如果队列变为空，更新队尾指针q->rear = NULL;}free(temp); // 释放旧队头的内存return value;
}// 查看队头元素
int front(Queue *q) {if (isEmpty(q)) {printf("队列空，无法查看队头元素！\n");return -1; // 返回一个错误值}return q->front->data;
}// 测试队列的功能
int main() {Queue q;initQueue(&q);enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);printf("队头元素: %d\n", front(&q)); // 输出: 10while (!isEmpty(&q)) {printf("出队元素: %d\n", dequeue(&q));}dequeue(&q); // 尝试从空队列出队return 0;
}

3. 队列的变种

除了基本的队列之外，还有几个常见的队列变种，每个变种具有不同的特性和用途：

3.1 双端队列（Deque）

双端队列（Deque, Double-Ended Queue）是一种允许在两端插入和删除元素的队列。它可以被视为一个可以从前端或后端进行操作的队列。

  • 操作：
    • push_front: 在队头插入元素。
    • push_back: 在队尾插入元素。
    • pop_front: 从队头移除元素。
    • pop_back: 从队尾移除元素。

使用链表实现双端队列：

#include <stdio.h>
#include <stdlib.h>// 链表节点结构
typedef struct Node {int data;struct Node *next;struct Node *prev; // 指向前一个节点
} Node;// 双端队列结构
typedef struct {Node *front; // 队头指针Node *rear;  // 队尾指针
} Deque;// 初始化双端队列
void initDeque(Deque *dq) {dq->front = NULL;dq->rear = NULL;
}// 判断双端队列是否为空
int isEmpty(Deque *dq) {return dq->front == NULL;
}// 从队头插入
void push_front(Deque *dq, int value) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = value;newNode->next = dq->front;newNode->prev = NULL;if (isEmpty(dq)) {dq->rear = newNode; // 如果队列为空，队头和队尾都指向新节点} else {dq->front->prev = newNode; // 更新原队头的前向指针}dq->front = newNode; // 更新队头指针
}// 从队尾插入
void push_back(Deque *dq, int value) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (isEmpty(dq)) {newNode->prev = NULL; // 队列为空时，前向指针为空dq->front = newNode; // 队头指向新节点} else {newNode->prev = dq->rear; // 更新新节点的前向指针dq->rear->next = newNode; // 更新原队尾的后向指针}dq->rear = newNode; // 更新队尾指针
}// 从队头移除
int pop_front(Deque *dq) {if (isEmpty(dq)) {printf("双端队列空，无法出队！\n");return -1;}Node *temp = dq->front;int value = temp->data;dq->front = dq->front->next; // 更新队头if (dq->front != NULL) {dq->front->prev = NULL; // 更新新的队头的前向指针} else { dq->rear = NULL; // 如果队列变为空，更新队尾指针}free(temp); // 释放旧队头的内存return value;
}// 从队尾移除
int pop_back(Deque *dq) {if (isEmpty(dq)) {printf("双端队列空，无法出队！\n");return -1;}Node *temp = dq->rear;int value = temp->data;dq->rear = dq->rear->prev; // 更新队尾if (dq->rear != NULL) {dq->rear->next = NULL; // 更新新的队尾的后向指针} else {dq->front = NULL; // 如果队列变为空，更新队头指针}free(temp); // 释放旧队尾的内存return value;
}// 测试双端队列功能
int main() {Deque dq;initDeque(&dq);push_back(&dq, 10);push_back(&dq, 20);push_front(&dq, 5);printf("队头元素: %d\n", pop_front(&dq)); // 输出: 5printf("队尾元素: %d\n", pop_back(&dq));   // 输出: 20return 0;
}
3.2 循环队列（Circular Queue）

循环队列（Circular Queue）是一种特殊的队列实现方式，它利用数组的循环性质来有效地使用空间，避免因“队列满”而无法插入元素的情况，即使数组中有空闲的位置。

在循环队列中，队头和队尾指针以环形方式移动。

下面是循环队列的实现：

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 5 // 定义队列的最大容量typedef struct {int data[MAX_SIZE]; // 存储队列元素int front;          // 队头指针int rear;           // 队尾指针
} CircularQueue;// 初始化循环队列
void initCircularQueue(CircularQueue *q) {q->front = 0;q->rear = 0;
}// 判断循环队列是否为空
int isEmpty(CircularQueue *q) {return q->front == q->rear;
}// 判断循环队列是否满
int isFull(CircularQueue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}// 入队
void enqueue(CircularQueue *q, int value) {if (isFull(q)) {printf("循环队列满，无法入队！\n");return;}q->data[q->rear] = value; // 将元素添加到队尾q->rear = (q->rear + 1) % MAX_SIZE; // 更新队尾指针
}// 出队
int dequeue(CircularQueue *q) {if (isEmpty(q)) {printf("循环队列空，无法出队！\n");return -1; // 返回一个错误值}int value = q->data[q->front]; // 获取队头元素q->front = (q->front + 1) % MAX_SIZE; // 更新队头指针return value;
}// 查看队头元素
int front(CircularQueue *q) {if (isEmpty(q)) {printf("循环队列空，无法查看队头元素！\n");return -1; // 返回一个错误值}return q->data[q->front];
}// 测试循环队列的功能
int main() {CircularQueue q;initCircularQueue(&q);enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);enqueue(&q, 40);enqueue(&q, 50); // 这里应该会提示队列满printf("队头元素: %d\n", front(&q)); // 输出: 10while (!isEmpty(&q)) {printf("出队元素: %d\n", dequeue(&q));}dequeue(&q); // 尝试从空队列出队return 0;
}

4. 队列的复杂度分析

队列的基本操作（入队、出队、查看队头元素）的时间复杂度均为 O(1)，无论是顺序存储、链式存储还是循环队列。

  • 空间复杂度：
    • 顺序队列：O(n)，其中 n 是队列的最大容量。
    • 链式队列：O(n)，其中 n 是队列中当前元素的数量。
    • 循环队列：O(n)，同样取决于最大容量。

5. 队列的应用

队列在计算机科学中有许多重要的应用，包括但不限于：

  1. 任务调度：操作系统中的进程调度、线程池中的任务管理等。
  2. 宽度优先搜索（BFS）：图的遍历算法使用队列来维护当前节点。
  3. 缓冲区：在输入输出处理中，使用队列作为缓冲区（如打印队列、网络数据包处理）。
  4. 消息队列：用于异步消息传递和事件处理的机制。
  5. 流量控制：在网络通信中，使用队列来管理流量和数据包。

http://www.ppmy.cn/ops/148251.html

相关文章

《探秘计算机视觉与深度学习：开启智能视觉新时代》

《探秘计算机视觉与深度学习：开启智能视觉新时代》

《探秘计算机视觉与深度学习&#xff1a;开启智能视觉新时代》 一、追溯起源&#xff1a;从萌芽到崭露头角二、核心技术&#xff1a;解锁智能视觉的密码&#xff08;一&#xff09;卷积神经网络&#xff08;CNN&#xff09;&#xff1a;图像识别的利器&#xff08;二&#xff0…
阅读更多...
最新版Edge浏览器加载ActiveX控件之Adobe PDF阅读器控件

最新版Edge浏览器加载ActiveX控件之Adobe PDF阅读器控件

背景 Adobe PDF阅读器控件是一个ActiveX控件&#xff0c;用于在Windows平台上显示和操作PDF文件。它提供了一系列方法和属性&#xff0c;可以实现对PDF文件的加载、显示、搜索、打印、保存等操作。 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件…
阅读更多...
【计算机网络】第四章·网络层

【计算机网络】第四章·网络层

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;计算机网络_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1. 前言 2…
阅读更多...
wujie无界微前端框架初使用

wujie无界微前端框架初使用

先说一下项目需求&#xff1a;将单独的四套系统的登录操作统一放在一个入口页面进行登录&#xff0c;所有系统都使用的是vue3&#xff0c;&#xff08;不要问我为啥会这样设计&#xff0c;产品说的客户要求&#xff09; 1.主系统下载wujie 我全套都是vue3&#xff0c;所以直接…
阅读更多...
H7-TOOL固件2.27发布，新增加40多款芯片脱机烧录，含多款车轨芯片，发布LUA API手册，CAN助手增加负载率，错误状态信息检测

H7-TOOL固件2.27发布，新增加40多款芯片脱机烧录，含多款车轨芯片，发布LUA API手册，CAN助手增加负载率，错误状态信息检测

H7-TOOL详细介绍&#xff08;含操作手册&#xff09;&#xff1a;H7-TOOL开发工具&#xff0c;1拖4/16脱机烧录&#xff0c;高速DAPLINK&#xff0c;RTOS Trace&#xff0c;CAN/串口助手, 示波器, RTT等&#xff0c;支持WiFi&#xff0c;以太网&#xff0c;高速USB和手持 - H7-…
阅读更多...
数据结构排序

数据结构排序

文章目录 排序插入排序折半插入排序希尔排序冒泡排序快速排序简单选择排序堆排序 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;数据结构专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2025年1月3日15点01分 排序 将各元素按关键字递增或递减…
阅读更多...
使用Python类库pandas操作Excel表格

使用Python类库pandas操作Excel表格

Date: 2025.01.02 20:33:30 author: lijianzhan 简述&#xff1a;pandas 是处理 Excel 文件的强大工具&#xff0c;它提供了简单易用的接口来读取、操作和写入 Excel 数据。以下是使用 pandas 处理 Excel 文件的详细指南&#xff0c;包括常见操作和示例代码。 安装依赖,pandas …
阅读更多...
WordPress Crypto插件前台任意用户登录漏洞复现（CVE-2024-9989）（附脚本）

WordPress Crypto插件前台任意用户登录漏洞复现（CVE-2024-9989）（附脚本）

0x01 产品描述： ‌WordPress Crypto插件是一种为WordPress网站提供加密货币支付、信息显示或交易功能的插件‌。这些插件通常与WordPress电子商务插件（如WooCommerce）集成，使网站能够接受多种加密货币支付，或展示加密货币实时信息。0x02 漏洞描述： WordPress 的 Crypto 插…
阅读更多...
最新文章

Copyright @ 2022~2023