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

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

时间：2024-10-27 11:47:22浏览次数：8  
标签：return -- 真的假 queue 队列 int printf 习题 stack

栈和队列

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语言中，栈和队列可以通过数组或链表来实现，每种实现方式都有其优缺点。

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

标签：return,--,真的假,queue,队列,int,printf,习题,stack
From： https://blog.csdn.net/2301_80374809/article/details/143234599

相关文章

  • 移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——15.C++11（1）
    1.自动类型推导(auto)C++11引入了auto关键字，可以根据初始值的类型自动推导变量的类型，从而减少了手动声明类型的繁琐。例如：std::vector<int>vec={1,2,3,4};autoit=vec.begin();//自动推导类型为std::vector<int>::iteratorauto的引入使代码更加简洁......
  • AI助力医疗数据自动化：思通数科的诊断报告识别与管理
    一、系统概述思通数科推出的智能化诊断报告识别系统，基于信息抽取、文本挖掘、数据处理等技术，旨在帮助医疗机构更高效地管理庞大的诊断报告数据。系统通过自动提取诊断报告中的关键信息，解决了传统医疗数据管理中的信息碎片化、录入效率低、查询困难等问题，减轻医务人员的工作负担，提......
  • 【机器学习】任务九：卷积神经网络（基于 Cifar-10 数据集的彩色图像识别分类、基于 CNN
    1.卷积神经网络        卷积神经网络（ConvolutionalNeuralNetwork,CNN）是一种专门用于处理数据网格结构（如图像、视频等）的深度学习模型，在计算机视觉任务中被广泛应用，如图像分类、目标检测、图像分割等。以下是卷积神经网络的详细介绍：1.1 卷积神经网络(CNN)结构及......
  • 【思维导图】C语言—数据类型和变量
     今天我们来回顾——C语言【数据类型和变量】我们先梳理一下思路：首先学习数据的类型，然后学会用类型去创建变量，接着学习操作符进行变量之间的运算，最后学习scanf输入数据，printf进行数据的打印。回顾的时候最好结合代码的编写，才能更好更直观地理解知识的用法。 我已经把思......
  • 【学术论文投稿】Windows11开发指南：打造卓越应用的必备攻略
    【IEEE出版·南方科技大学】第十一届电气工程与自动化国际会议（IFEEA2024)_艾思科蓝_学术一站式服务平台 更多学术会议论文投稿请看：https://ais.cn/u/nuyAF3目录引言 一、Windows11开发环境搭建二、Windows11关键新特性三、Windows11设计指南四、Windows11开发实战代......
  • 基于SSM平面设计课程在线学习系统的设计
    管理员账户功能包括：系统首页，个人中心，学生管理，教师管理，课程类型管理，课程学习管理，试题讲解管理，作业信息管理前台账号功能包括：系统首页，个人中心，课程学习，在线讨论，系统公告，后台管理开发系统：Windows架构模式：SSMJDK版本：JavaJDK1.8开发工具：IDEA(推荐)数据库版本：mysql5.7数据库......
  • 基于SSM轻型卡车零部件销售系统的设计
    管理员账户功能包括：系统首页，个人中心，用户管理，配件类型管理，配件信息管理，订单信息管理，检修休息管理，系统管理用户账号功能包括：系统首页，个人中心，订单信息管理，检修信息管理，售后信息管理开发系统：Windows架构模式：SSMJDK版本：JavaJDK1.8开发工具：IDEA(推荐)数据库版本：mysql5.7数......
  • 给函数传入结构体和传入该结构体的指针的区别
    给函数传入结构体和传入该结构体的指针在C/C++中有以下几个关键区别：1.传递方式传入结构体（按值传递）:当把结构体按值传递给函数时，函数会创建一个结构体的副本。这意味着函数中对结构体的任何修改都不会影响原始结构体的数据，因为修改的只是副本。副本是结构体的一个独立拷......
  • 边缘计算的优势是什么
    边缘计算的优势有：一、降低数据传输延迟；二、减少网络带宽压力；三、增强数据隐私和安全性；四、提供离线服务能力；五、支持实时响应和快速决策等。降低数据传输延迟是指，边缘计算将计算和数据处理推向网络边缘，使得数据可以在离用户更近的地方进行处理，这样大大缩短了数据传输延迟，一、......
  • 一个数据类型困扰了我一下午
    用VBA写一个网络状态查看程序，调用用GetAdaptersAddresses函数。其中返回值的类型如上！没有现在的代码代参考。只能从MSDN上找help自己改写。结果返回的值就是对不上！本人知道是数据类型有问题，核对了好多次，就是找不到出错点！typedefstruct_IP_ADAPTER_ADDRESSES_LH{union{......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99