栈和队列（C语言）

ops/2025/1/21 18:06:46/

目录

数据结构之栈

定义

 实现方式

基本功能实现

1）定义，初始化栈

2）入栈

3）出栈

4）获得栈顶元素

5)获得栈中有效元素个数

6）检测栈是否为空

7）销毁栈

数据结构之队列 

定义

实现方式

基本功能实现

1）定义，初始化队列

2）入队

3）出队

4）获得队列头部元素

5）获得队尾元素

6）队列元素个数

7）队列是否为空

8）销毁队列

栈和队列练习

1.1 有效括号

用栈的先入后出性质

数据结构之栈

定义

栈：一种特殊的线性表，其特点是只允许在一端进行插入和删除的操作，这一端叫做栈顶，另一端叫做栈底；栈中的数据使用的时候必须遵行先入后出(先进入的后出来)的原则。就好比一群人上电梯，最先进去的站在里面，最后出来，而最后上来的站在门口，最先出来。

压栈：向栈顶插入元素；

出栈：将栈顶元素删去；

原则：入栈和出栈的操作对象都是栈顶。

 实现方式

栈的实现方式有两种，可以用前面的顺序表也可以使用链表。

1）使用链表实现，要记录尾节点(避免遍历链表找尾)方便压栈；同时还要记录倒数第二个节点，方便出栈时，将尾节点释放。所以一共需要定义两个结构体：链表结构体，结构体(记录头节点，尾节点，倒数第二个节点)；

2）使用顺序表实现，顺序表有栈内的总个数，可以直接找到尾，也可以直接出栈，相比于链表更简单。所以我们更推荐使用顺序表来实现栈。

顺序表（含通讯录）-CSDN博客文章浏览阅读743次，点赞16次，收藏11次。C语言实现顺序表及其基本功能的实现，包含通讯录项目。https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098https://blog.csdn.net/2401_87944878/article/details/144408098

链表(C语言)-CSDN博客文章浏览阅读730次，点赞18次，收藏7次。用C语言实现数据结构中单链表和双链表的详细介绍https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576https://blog.csdn.net/2401_87944878/article/details/144423576

基本功能实现

1）定义，初始化栈

栈的底层逻辑是顺序表，所以可以直接使用顺序表的初始化。

typedef int SDateType;typedef struct Stack
{SDateType* a;int size;int capacity;
}Stack;//栈的初始化
void StackInit(Stack* ps)
{assert(ps);ps->capacity = 4;ps->a = (SDateType*)malloc(sizeof(SDateType)*(ps->capacity));if (ps->a == NULL)perror("malloc failed!");ps->size = 0;
}

2）入栈

向栈顶添加元素，ps->size就是栈顶位置的下标；

//入栈
void StackPush(Stack* ps,  SDateType x)
{assert(ps);//判断空间够不够if (ps->capacity == ps->size){ps->capacity *= 2;SDateType* new = (SDateType*)realloc(ps->a,sizeof(SDateType) * (ps->capacity));if (new == NULL)perror("realloc failed!");ps->a = new;}//入栈ps->a[ps->size] = x;ps->size++;
}

3）出栈

出栈不需要对栈顶元素进行处理，只需要将栈内元素个数-1即可，将栈顶元素看作无效数据；

//出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps->size);ps->size--;
}

4）获得栈顶元素

//获得栈顶元素
SDateType StackTop(Stack* ps)
{assert(ps->a);assert(ps->size);return ps->a[ps->size - 1];
}

5)获得栈中有效元素个数

//获得栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps->size;
}

6）检测栈是否为空

//检测栈是否为空
bool IsStackEmpty(Stack* ps)
{assert(ps);if (ps->size == 0)return true;return false;
}

7）销毁栈

将malloc的空间释放，将顺序表中的变量制空。

//栈的销毁
void StackDestory(Stack* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

数据结构之队列 

定义

队列：也是一种特殊的线性表，其特点是只允许在一端(队尾)进行插入，另一端(队头)进行删除。队列的数据结构必须遵循先入先出(先进入的先出来原则。就好比车辆进站加油，先进入的车会先出来。

入队：向队尾添加元素；

出队：将队头的元素删去；

实现方式

与栈相同，队列也有两种实现方式；

1）顺序表实现，用顺序表可以直接找到队尾，进行入队，但是在出队的时候将队头元素删除后，要将后面元素整体向前移动，效率低。

2）链表实现，用链表实现的时候，只要记录了尾节点，头节点就可以直接对队列进行入队和出队操作，链表实现的效率更高，此处以链表实行为例。

基本功能实现

1）定义，初始化队列

定义两个结构体，1）链表；2）用于记录头节点，尾节点及链表长度的结构体。

//定义队列
typedef int QDateType;typedef struct QueNode
{QDateType date;struct QueNode* next;
}QueNode;typedef struct Queue
{QueNode* front;QueNode* tail;int size;
}Queue;//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->front = pq->tail = NULL;pq->size = 0;
}

2）入队

向队尾添加元素；

//入队
void QueuePush(Queue* pq, QDateType x)
{assert(pq);//创建新节点QueNode* newnode = (QueNode*)malloc(sizeof(QueNode));newnode->date = x;newnode->next = NULL;if (pq->front == NULL)pq->front = pq->tail = newnode;else{pq->tail->next = newnode;pq->tail = pq->tail->next;}
}

3）出队

将队头元素删去。

//出队
void QueuePop(Queue* pq)
{assert(pq);//记录队头QueNode* del = pq->front;pq->front = pq->front->next;free(del);del = NULL;
}

4）获得队列头部元素

//获得队列头部元素
QDateType QueTop(Queue* pq)
{assert(pq);assert(pq->size);return pq->front->date;
}

5）获得队尾元素

//获得队尾元素
QDateType QueTail(Queue* pq)
{assert(pq);assert(pq->size);return pq->tail->date;
}

6）队列元素个数

//获得队列元素个数
int QueSize(Queue* pq)
{assert(pq);return pq->size;
}

7）队列是否为空

//判断队列是否为空
bool IsQueueEmpty(Queue* pq)
{assert(pq);if (pq->size == 0)return true;return false;
}

8）销毁队列

//销毁队列
void QueDestory(Queue* pq)
{assert(pq);//要销毁队列的每一个元素while (!IsQueueEmpty){QueuePop(pq);}pq->front = pq->size = NULL;
}

栈和队列练习

1.1 有效括号

20. 有效的括号 - 力扣（LeetCode）

用栈的先入后出性质

遍历字符串，对于左括号入栈，当遇到右括号的时候，出栈，将出栈元素和左括号进行对比，看是否配对。

//有效括号
bool isValid(char* s) {Stack sta;StackInit(&sta);char* cur = s;while(*cur!='\0'){//判断是否是左括号if ((*cur) == '(' || (*cur) == '{' || (*cur) == '['){StackPush(&sta, *cur);cur++;}//将左括号和右括号进行对比else{if (IsStackEmpty(&sta))return false;char left = StackTop(&sta);StackPop(&sta);  //取出栈顶元素if ((left == '(' && (*cur) != ')') ||(left == '{' && (*cur) != '}') ||(left == '[' && (*cur) != ']'))return false;cur++;}}if(!IsStackEmpty(&sta))return false;   //栈中还有元素return true;
}


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

相关文章

Jupyter notebook中运行dos指令运行方法

Jupyter notebook中运行dos指令运行方法

Jupyter notebook中运行dos指令运行方法 目录 Jupyter notebook中运行dos指令运行方法一、DOS(磁盘操作系统）指令介绍1.1 DOS介绍1.2 DOS指令1.2.1 DIR - 显示当前目录下的文件和子目录列表。1.2.2 CD 或 CHDIR - 改变当前目录1.2.3 使用 CD .. 可以返回上一级目录1…
阅读更多...
PHP企业IM客服系统

PHP企业IM客服系统

💬 企业IM客服系统——高效沟通，无缝连接的智慧桥梁 🚀 卓越性能，释放无限可能 在瞬息万变的商业环境中，我们深知沟通的力量。因此，基于先进的ThinkPHP5框架与高性能的Swoole扩展，我们匠心独运…
阅读更多...
matlab实现了一个完整的语音通信系统的模拟，包括语音信号的读取、编码（PCM 和汉明码）、调制

matlab实现了一个完整的语音通信系统的模拟，包括语音信号的读取、编码（PCM 和汉明码）、调制

% step 1: 读入语音信号，并进行归一化处理 [audio, fs] = audioread(D:\txyp4.m4a); len_speech = length(audio); % 计算语音信号的采样点个数
阅读更多...
HTML 的基础知识及其重要性

HTML 的基础知识及其重要性

前言 HTML（超文本标记语言）是构建网页的基础，它为我们提供了结构化内容和重要信息。无论是个人博客、企业官网还是大型电子商务平台，HTML 都是不可或缺的一部分。本文将介绍 HTML 的基本概念、结构及其在网页开发中的重要性。 什…
阅读更多...
ESP32-C3物联网芯片方案，设备智能化交互联动，无线通信控制技术

ESP32-C3物联网芯片方案，设备智能化交互联动，无线通信控制技术

在科技的浩瀚星空中，物联网芯片犹如一颗璀璨的明星，正散发着耀眼的光芒。它以其独特的魅力和强大的功能，吸引着无数科技爱好者和行业的目光。 在当今数字化浪潮席卷的时代，物联网技术正在不断的改变着我们的生活与生产方式&#…
阅读更多...
数据结构：栈和队列详解（上）

数据结构：栈和队列详解（上）

一.栈 1.概念与结构： 栈：一种特殊的线性表，只允许在顺序表的一段插入和删除数据，进行插入和删除的一端叫做栈顶，另外一端则叫做栈底，而我们将在栈顶插入数据叫做压栈（入栈或进栈）&a…
阅读更多...
一次理清楚Java中的日期和时间

一次理清楚Java中的日期和时间

Java中的日期和时间 概述 学习最大的问题困难在于沉下心，现实社会纷乱复杂，充满诱惑，同时随着成家立业年岁增长更无当年之志，顿感无力。回想公瑾当年之言：“日抚谣琴听音，夜有娇妻伴读，此生足矣…
阅读更多...
MCU中的LSB、MSB和大端模式、小端模式

MCU中的LSB、MSB和大端模式、小端模式

第一章 LSB和MSB 1.1 最低有效位(Least Significant Bit, LSB) 红外接收器接收了0x45（0100 0101）之后，怎么将这个数据发送给MCU; LSB（least significant bit）：最低有效位优先，例如红外通信是以…
阅读更多...
最新文章

Copyright @ 2022~2023