重生之“我打数据结构，真的假的？”--3.栈和队列（无习题）

栈和队列

C语言中的栈和队列总结

在C语言中，**栈（Stack）和队列（Queue）**是两种非常重要的数据结构。它们广泛用于各种应用中，比如内存管理、任务调度、表达式求值等。本文将对这两种数据结构进行详细的介绍，并展示如何在C语言中实现它们。

1. 栈（Stack）

栈是一种先进后出（LIFO，Last In First Out）数据结构，类似于一摞盘子，最后放上去的盘子最先被拿下来。
在这里插入图片描述

1.1 栈的特点

  • 先进后出（LIFO）：最后入栈的元素最先出栈。
  • 单端操作：栈的插入和删除操作都发生在栈顶。

1.2 栈的基本操作

  • 压栈（Push）：将元素压入栈顶。
  • 弹栈（Pop）：从栈顶移除元素。
  • 查看栈顶元素（Peek/Top）：获取栈顶元素但不删除它。
  • 判断栈是否为空（isEmpty）。

1.3 栈的实现方式

栈可以通过数组或链表来实现。以下分别讨论栈的数组实现和链表实现。

1.3.1 使用数组实现栈

以下是用C语言实现栈的数组版：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct Stack {
    int items[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 判断栈是否已满
bool isFull(Stack* stack) {
    return stack->top == MAX_SIZE - 1;
}

// 压栈操作
void push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("栈已满，无法压入元素。\n");
        return;
    }
    stack->items[++stack->top] = value;
    printf("压入元素：%d\n", value);
}

// 弹栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法弹出元素。\n");
        return -1;
    }
    return stack->items[stack->top--];
}

// 查看栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，没有栈顶元素。\n");
        return -1;
    }
    return stack->items[stack->top];
}

// 遍历栈
void traverseStack(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空。\n");
        return;
    }
    for (int i = 0; i <= stack->top; i++) {
        printf("%d ", stack->items[i]);
    }
    printf("\n");
}

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("栈的内容：");
    traverseStack(&stack);

    printf("弹出元素：%d\n", pop(&stack));
    printf("栈顶元素：%d\n", peek(&stack));

    printf("栈的内容：");
    traverseStack(&stack);

    return 0;
}
1.3.2 使用链表实现栈

以下是使用链表实现栈的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Stack {
    Node* top;
} Stack;

// 初始化栈
void initStack(Stack* stack) {
    stack->top = NULL;
}

// 判断栈是否为空
bool isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// 压栈操作
void push(Stack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
    printf("压入元素：%d\n", value);
}

// 弹栈操作
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，无法弹出元素。\n");
        return -1;
    }
    Node* temp = stack->top;
    int poppedValue = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return poppedValue;
}

// 查看栈顶元素
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("栈为空，没有栈顶元素。\n");
        return -1;
    }
    return stack->top->data;
}

// 遍历栈
void traverseStack(Stack* stack) {
    Node* current = stack->top;
    if (isEmpty(stack)) {
        printf("栈为空。\n");
        return;
    }
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("栈的内容：");
    traverseStack(&stack);

    printf("弹出元素：%d\n", pop(&stack));
    printf("栈顶元素：%d\n", peek(&stack));

    printf("栈的内容：");
    traverseStack(&stack);

    return 0;
}

1.4 栈的应用

  • 函数调用栈：计算机系统使用栈来保存函数调用的返回地址。
  • 表达式求值和括号匹配：在表达式求值中，栈用于临时保存操作数和操作符。
  • 深度优先搜索（DFS）：在图的遍历中，栈可以用于实现深度优先搜索。

2. 队列（Queue）

队列是一种先进先出（FIFO，First In First Out）数据结构，类似于排队买票，第一个到达的人先买票。

2.1 队列的特点

  • 先进先出（FIFO）：第一个入队的元素第一个出队。
  • 双端操作：插入操作发生在队尾，而删除操作发生在队头。

2.2 队列的基本操作

  • 入队（Enqueue）：在队尾添加一个元素。
  • 出队（Dequeue）：从队头移除一个元素。
  • 查看队头元素（Front）。
  • 判断队列是否为空（isEmpty）。

2.3 队列的实现方式

队列可以通过数组或链表来实现。以下分别介绍这两种实现方式。

2.3.1 使用数组实现队列

以下是使用数组实现队列的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct Queue {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = -1;
    queue->rear = -1;
}

// 判断队列是否为空
bool isEmpty(Queue* queue) {
    return queue->front == -1;
}

// 判断队列是否已满
bool isFull(Queue* queue) {
    return queue->rear == MAX_SIZE - 1;
}

// 入队操作
void enqueue(Queue* queue, int value) {
    if (isFull(queue)) {
        printf("队列已满，无法入队元素。\n");
        return;
    }
    if (isEmpty(queue)) {
        queue->front = 0;
    }
    queue->items[++queue->rear] = value;
    printf("入队元素：%d\n", value);
}

// 出队操作
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队元素。\n");
        return -1;
    }
    int value = queue->items[queue->front];
    if (queue->front >= queue->rear) {
        // 队列为空
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    return value;
}

// 查看队头元素
int front(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，没有队头元素。\n");
        return -1;
    }
    return queue->items[queue->front];
}

// 遍历队列
void traverseQueue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空。\n");
        return;
    }
    for (int i = queue->front; i <= queue->rear; i++) {
        printf("%d ", queue->items[i]);
    }
    printf("\n");
}

int main() {
    Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("队列的内容：");
    traverseQueue(&queue);

    printf("出队元素：%d\n", dequeue(&queue));
    printf("队头元素：%d\n", front(&queue));

    printf("队列的内容：");
    traverseQueue(&queue);

    return 0;
}
2.3.2 使用链表实现队列

以下是使用链表实现队列的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
bool isEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(Queue* queue, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(queue)) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    printf("入队元素：%d\n", value);
}

// 出队操作
int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，无法出队元素。\n");
        return -1;
    }
    Node* temp = queue->front;
    int value = temp->data;
    queue->front = queue->front->next;

    if (queue->front == NULL) {
        queue->rear = NULL;
    }

    free(temp);
    return value;
}

// 查看队头元素
int front(Queue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空，没有队头元素。\n");
        return -1;
    }
    return queue->front->data;
}

// 遍历队列
void traverseQueue(Queue* queue) {
    Node* current = queue->front;
    if (isEmpty(queue)) {
        printf("队列为空。\n");
        return;
    }
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("队列的内容：");
    traverseQueue(&queue);

    printf("出队元素：%d\n", dequeue(&queue));
    printf("队头元素：%d\n", front(&queue));

    printf("队列的内容：");
    traverseQueue(&queue);

    return 0;
}

2.4 队列的应用

  • 操作系统中的任务调度：队列用于实现任务调度和处理。
  • 广度优先搜索（BFS）：在图的遍历中，队列用于实现广度优先搜索。
  • 缓存（Buffer）：队列可用于实现环形缓冲区或缓冲机制。

3. 栈和队列的对比

特性栈（Stack）队列（Queue）
数据结构类型线性线性
操作模式LIFO（后进先出）FIFO（先进先出）
插入/删除位置只在一端操作（栈顶）两端操作（队头和队尾）
应用场景函数调用、递归、括号匹配任务调度、广度优先搜索

4. 小结

栈和队列都是重要的线性数据结构，栈采用LIFO原则，而队列采用FIFO原则。栈和队列的操作非常简单，但它们在实际应用中起到了至关重要的作用。在C语言中，栈和队列可以通过数组或链表来实现，每种实现方式都有其优缺点。

在理解了这些数据结构的基本操作后，可以更好地应用它们来解决实际问题，如表达式求值、任务调度、图遍历等。掌握这些基础数据结构也为进一步学习更加复杂的数据结构（如树、图等）打下了坚实的基础。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/901031.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

从零开始的Go语言之旅（2 Go by Example: Values）

从零开始的Go语言之旅（2 Go by Example: Values）

Go 语言有多种值类型&#xff0c;包括字符串、整数、浮点数、布尔值等。以下是一些基本示例。 package mainimport "fmt"func main() {fmt.Println("go" "lang")fmt.Println("11 ", 11)fmt.Println("7.0/3.0 ", 7.0/3.0)f…
阅读更多...
深度学习——线性神经网络（五、图像分类数据集——Fashion-MNIST数据集）

深度学习——线性神经网络（五、图像分类数据集——Fashion-MNIST数据集）

目录 5.1 读取数据集5.2 读取小批量5.3 整合所有组件 MNIST数据集是图像分类中广泛使用的数据集之一&#xff0c;但是作为基准数据集过于简单&#xff0c;在本小节将使用类似但更复杂的Fashion-MNIST数据集。 import torch import torchvision from torch.utils import data fr…
阅读更多...
你了解的spring框架有哪些

你了解的spring框架有哪些

列举一些重要的Spring模块&#xff1f; Spring Core&#xff1a; 基础,可以说 Spring 其他所有的功能都需要依赖于该类库。主要提供 IOC 依赖注入功能。**Spring Aspects ** &#xff1a; 该模块为与AspectJ的集成提供支持。Spring AOP &#xff1a;提供了面向方面的编程实现。…
阅读更多...
logback 如何将日志输出到文件

logback 如何将日志输出到文件

如何作 将日志输出到文件需要使用 RollingFileAppender&#xff0c;该 Appender 必须定义 rollingPolicy &#xff0c;另外 rollingPollicy 下必须定义 fileNamePattern 和 encoder <appender name"fileAppender" class"ch.qos.logback.core.rolling.Rollin…
阅读更多...
重构案例：将纯HTML/JS项目迁移到Webpack

重构案例：将纯HTML/JS项目迁移到Webpack

我们已经了解了许多关于 Webpack 的知识&#xff0c;但要完全熟练掌握它并非易事。一个很好的学习方法是通过实际项目练习。当我们对 Webpack 的配置有了足够的理解后&#xff0c;就可以尝试重构一些项目。本次我选择了一个纯HTML/JS的PC项目进行重构&#xff0c;项目位于 GitH…
阅读更多...
Elliott Wave Prophet，艾略特波浪预测指标！预测未来走势！免费公式！（指标教程）

Elliott Wave Prophet，艾略特波浪预测指标！预测未来走势！免费公式！（指标教程）

指标名称&#xff1a;艾略特波浪预测 Elliott Wave Prophet 版本&#xff1a;MT4 ver. 2.0 Elliott Wave Prophet &#xff0c;艾略特波浪预测指标是一款创新的外汇指标&#xff0c;旨在帮助进行波浪分析&#xff0c;并基于已形成的波浪来一定程度上预测未来的价格走势。Elli…
阅读更多...
【设计模式-状态模式】

【设计模式-状态模式】

状态模式&#xff08;State Pattern&#xff09;是一种行为设计模式&#xff0c;它允许一个对象在内部状态改变时改变它的行为。换句话说&#xff0c;这种模式让对象在不同的状态下能够表现出不同的行为&#xff0c;而不需要修改对象的代码。状态模式通过将对象的行为与状态进行…
阅读更多...
江协科技STM32学习- P21 ADC模数转换器

江协科技STM32学习- P21 ADC模数转换器

&#x1f680;write in front&#x1f680; &#x1f50e;大家好&#xff0c;我是黄桃罐头&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流 &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​…
阅读更多...
FFMPEG+Qt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频

FFMPEG+Qt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频

FFMPEGQt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频 文章目录 FFMPEGQt 实时显示本机USB摄像头1080p画面以及同步录制mp4视频1、前言1.1 目标1.2 一些说明 2、效果3、代码3.1 思路3.2 工程目录3.3 核心代码 4、全部代码获取 1、前言 本文通过FFMPEG(7.0.2)与Qt(5.13.…
阅读更多...
多线程初阶（七）：单例模式指令重排序

多线程初阶（七）：单例模式指令重排序

目录 1. 单例模式 1.1 饿汉模式 1.2 懒汉模式 2. 懒汉模式下的问题 2.1 线程安全问题 2.2 如何解决 --- 加锁 2.3 加锁引入的新问题 --- 性能问题 2.4 指令重排序问题 2.4.1 指令重排序 2.4.2 指令重排序引发的问题 1. 单例模式 单例模式, 是设计模式中最典型的一种模…
阅读更多...
【ArcGIS微课1000例】0125：ArcGIS矢量化无法自动完成面解决方案

【ArcGIS微课1000例】0125：ArcGIS矢量化无法自动完成面解决方案

文章目录 一、坐标系统问题二、正确使用自动完成面工具一、坐标系统问题 1. 数据库坐标系 arcgis矢量化的过程中，无法自动完成面，可能是因为图层要素没有坐标系造成的。双击数据库打开数据库属性，可以查看当前数据框的坐标系。 2. 图层坐标系 双击图层，打开图层属性，切…
阅读更多...
Safari 中 filter: blur() 高斯模糊引发的性能问题及解决方案

Safari 中 filter: blur() 高斯模糊引发的性能问题及解决方案

目录 引言问题背景&#xff1a;filter: blur() 引发的问题产生问题的原因分析解决方案&#xff1a;开启硬件加速实际应用示例性能优化建议常见的调试工具与分析方法 引言 在前端开发中&#xff0c;CSS滤镜&#xff08;如filter: blur()&#xff09;的广泛使用为页面带来了各种…
阅读更多...
使用query-string库出现错误Module parse failed: Unexpected token

使用query-string库出现错误Module parse failed: Unexpected token

环境 node v12query-string 9.1.0 报错信息 Failed to compile../node_modules/query-string/base.js 350:14 Module parse failed: Unexpected token (350:14) File was processed with these loaders:* ./node_modules/babel-loader/lib/index.js You may need an additio…
阅读更多...
正则表达式和通配符

正则表达式和通配符

文章目录 正则表达式和通配符的区别正则表达式&#xff08;Regex&#xff09;通配符&#xff08;Wildcards&#xff09;总结 正则表达式的概念正则表达式的由来为什么要使用正则表达式 正则表达式的语法组成修饰符元字符\f\b\B 在Linux中的基础正则和扩展正则基础正则(BRE)^$.*…
阅读更多...
【南方科技大学】CS315 Computer Security 【Lab6 IoT Security and Wireless Exploitation】

【南方科技大学】CS315 Computer Security 【Lab6 IoT Security and Wireless Exploitation】

目录 Introduction (Part 1: OS Security for IoT )Software RequirementsStarting the Lab 6 Virtual MachineSetting up the Zephyr Development EnvironmentDownload the Zephyr Source CodeInstalling Requirements and DependenciesSetting the Project’s Environment Va…
阅读更多...
《a16z : 2024 年加密货币现状报告》解析

《a16z : 2024 年加密货币现状报告》解析

加密社 原文链接&#xff1a;State of Crypto 2024 - a16z crypto译者&#xff1a;AI翻译官&#xff0c;校对&#xff1a;翻译小组 当我们两年前第一次发布年度加密状态报告的时候&#xff0c;情况跟现在很不一样。那时候&#xff0c;加密货币还没成为政策制定者关心的大事。 比…
阅读更多...
Ubuntu 安装 npm

Ubuntu 安装 npm

1. 升级apt sudo apt-get update 2. 安装nodejs sudo apt install nodejs 3. 安装npm sudo apt-get install npm 4. 查看版本 node -v npm -v 完成安装&#xff01;
阅读更多...
记一次AWS服务器扩容

记一次AWS服务器扩容

1、首先通过下列命令列出设备详情&#xff0c;可以看到红色框起来的部分有160G&#xff0c;需要把新增的20G扩容到根目录(139.9)上 lsblk查看文件系统 df -h2.执行sudo growpart /dev/xvda 1即可把20G的空间扩容到根目录上 扩容成功 但是可以看到并未生效 3.列出文件系统格…
阅读更多...
ue5实现数字滚动增长

ue5实现数字滚动增长

方法1 https://www.bilibili.com/video/BV1h14y197D1/?spm_id_from333.999.0.0 b站教程 重写loop节点 方法二 写在eventtick里
阅读更多...
NVR小程序接入平台/设备EasyNVR多品牌NVR管理工具/设备的多维拓展与灵活应用

NVR小程序接入平台/设备EasyNVR多品牌NVR管理工具/设备的多维拓展与灵活应用

在数字化安防时代&#xff0c;NVR批量管理软件/平台EasyNVR作为一种先进的视频监控系统设备&#xff0c;正逐步成为各个领域监控解决方案的首选。NVR批量管理软件/平台EasyNVR作为一款基于端-边-云一体化架构的国标视频融合云平台&#xff0c;凭借其部署简单轻量、功能多样、兼…
阅读更多...
最新文章

Copyright @ 2022~2023