实现简单的栈与队列

news/2025/2/15 20:13:56/

前言：前面已经详细地介绍了基本的顺序表和链表，这次要介绍的是数据结构中的栈与队列。从本质上来说，二者是特殊的线性表，是依赖于顺序表或链表来实现的，所以只要能够很好地掌握顺序表和链表，再了解清楚栈与队列的概念及基本结构，就可以很好地将二者实现出来。

注：由上言以及下文可以知道栈与队列的实现与顺序表，链表的实现大同小异（甚至更简单），一些内容不会详细说明，不清楚的可以再看看以下两篇文章：

（1）顺序表的实现

（2）单链表的实现

目录：

一：栈

1. 栈的概念

2. 栈的结构(图示)

3. 栈的重要接口函数

4. 栈实现相关代码总览

二：队列

1. 队列的概念

2. 队列的结构(图示)

3. 队列的重要接口函数

4. 队列实现相关代码总览

一：栈

1. 栈的概念

(1) 栈: 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
(2) 压栈：栈的插入操作叫做压栈/进栈/入栈，即入数据在栈顶。
(3) 出栈：栈的删除操作叫做出栈。即出数据也在栈顶。

2. 栈的结构(图示)

注：栈一定要遵守先进后出的原则。

3. 栈的重要接口函数

我们可以使用顺序表来实现栈，也可以用链表实现栈，但是链表实现栈有两种方式，一种是头插头删，一种是尾插尾删。而单链表进行尾插尾删时要进行的找尾操作较为复杂(要遍历链表)，所以我们选择顺序表(数组)来实现栈，其结构相对链表而言较为优势。

栈相关的七个重要接口函数：

void StackInit(ST* st);//初始化
void StackPush(ST* st, STDataType x);//入栈
void StackPop(ST* st);//出栈
STDataType StackTop(ST* st);//获取栈顶元素
int StackSize(ST* st);//获取栈中的有效元素个数
bool StackEmpty(ST* st);//判断栈是否为空
void StackDestroy(ST* st);//销毁栈

4. 栈实现相关代码总览

（1）TestStack.c

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"void TestStack1()
{ST st;//定义一个栈StackInit(&st);//将栈初始化,要传递结构体指针才能在接口函数内对其进行改变StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);//压栈printf("%d\n", StackSize(&st));//打印此时的栈内元素个数while (!StackEmpty(&st))//打印出栈内的所有数据{printf("%d ", StackTop(&st));StackPop(&st);}//一个小疑问：Pop执行后的终点是top=0,但是此时st->a[0]不是等于1吗,这样不是没有删干净吗？printf("\n%d\n", StackSize(&st));StackDestroy(&st);
}void TestStack2()
{ST st;//定义一个栈StackInit(&st);//将栈初始化,要传递结构体指针才能在接口函数内对其进行改变StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);printf("%d\n", StackSize(&st));StackPop(&st);StackPop(&st);printf("%d\n", StackSize(&st));//Pop两次后栈内的元素个数while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}printf("\n%d\n", StackSize(&st));StackDestroy(&st);
}int main()
{TestStack1();//TestStack2();return 0;
}

（2）Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;//定义一个动态增长的数组栈
typedef struct Stack
{STDataType* a;//指针a指向动态开辟的数组int top;//表示栈内的有效元素个数int capacity;//表示栈的空间容量
} ST;//相关接口函数的定义
void StackInit(ST* st);//初始化
void StackPush(ST* st, STDataType x);//入栈
void StackPop(ST* st);//出栈
STDataType StackTop(ST* st);//获取栈顶元素
int StackSize(ST* st);//获取栈中的有效元素个数
bool StackEmpty(ST* st);//判断栈是否为空
void StackDestroy(ST* st);//销毁栈

（3）Stack.c

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"void StackInit(ST* st)
{assert(st);st->a = NULL;//top初始化为0时,top指向的是栈顶的下一个数据,因为压栈是先插入数据后top再加1st->top = st->capacity = 0;
}void StackPush(ST* st, STDataType x)//入栈,向栈内插入数据
{assert(st);if (st->top == st->capacity)//判断容量是否足够,不够就扩容{int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, sizeof(ST) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}st->a = tmp;st->capacity = newCapacity;}st->a[st->top] = x;st->top++;//先插入数据,top再++,即top此时指向的是栈顶的下一个数据
}void StackPop(ST* st)//出栈
{assert(st);//assert(st->top > 0);assert(!StackEmpty(st));//栈不能为空st->top--;
}bool StackEmpty(ST* st)//判断栈是否为空
{assert(st);return st->top == 0;
}STDataType StackTop(ST* st)//获取栈顶元素
{assert(st);return st->a[st->top - 1];//top下标指向的是栈顶的后一个数据
}int StackSize(ST* st)//获取栈内有效数据的个数
{assert(st);return st->top;
}void StackDestroy(ST* st)//销毁栈
{assert(st);while (!StackEmpty(st)){StackPop(st);}st->a = NULL;st->top = st->capacity = 0;
}

二：队列

1. 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。

2. 队列的结构(图示)

 注：队列一定要遵守先进先出的原则。

3. 队列的重要接口函数的实现

与栈相同，队列既可以通过顺序表来实现，也可以通过链表实现。但与栈实现起来不同的是，对于队列而言，链表的结构更适合它，因为队列主要涉及到的是头部尾部的插入与删除，而顺序表(数组)实现起来的效率会更低一些。

这里需要特别说明的是：选用的是单链表，并且我们需要给这个单链表定义好头节点 (head)和尾节点(tail)，将它们作为队列的基本框架，以形成一个较好头插尾删的单链表。

图示：

代码说明：

队列相关接口函数：

void QueueInit(Queue* pq);//初始化队列
void QueuePush(Queue* pq, QDataType x);//入队列
void QueuePop(Queue* pq);//出队列
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//返回队列中有效数个数
QDataType QueueFront(Queue* pq);//获取队头数据
QDataType QueueBack(Queue* pq);//获取队尾数据
void QueuePrint(Queue* pq);//打印队列(同时会清空队列的元素)
void QueueDestroy(Queue* pq);//销毁队列中动态开辟节点的链表

4. 队列实现相关代码总览

(1) TestQueue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"void TestQueue1()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("%d\n", QueueSize(&q));//打印此时队列内的元素个数QueuePop(&q);QueuePop(&q);printf("%d\n", QueueSize(&q));//打印此时队列内的元素个数QueuePrint(&q);//QueuePrint函数调用的同时会清空队列printf("\n%d\n", QueueSize(&q));QueueDestroy(&q);
}void TestQueue2()
{Queue q;QueueInit(&q);QueuePush(&q, 5);QueuePush(&q, 6);QueuePush(&q, 7);QueuePush(&q, 8);//打印此时队列元素个数,队头数据,对尾数据printf("%d %d %d\n", QueueSize(&q), QueueFront(&q), QueueBack(&q));QueuePrint(&q);//QueuePrint函数调用的同时会清空队列printf("\n%d\n", QueueSize(&q));QueueDestroy(&q);
}int main()//各个接口函数功能的测试
{TestQueue1();//TestQueue2();return 0;
}

(2) Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QDataType;//用单链表实现队列(定义队列中的链表结构)
typedef struct QueueListNode
{struct QueueListNode* next;//指针域QDataType data;//数据域
} QLNode;//为了更好地实现单链表的头删(出队列)与尾插(入队列),在队列的链表结构中在定义一个头节点与尾节点,可以表示队列的结构
typedef struct Queue
{QLNode* head;QLNode* tail;
} Queue;//队列相关接口函数的定义
void QueueInit(Queue* pq);//初始化队列
void QueuePush(Queue* pq, QDataType x);//入队列
void QueuePop(Queue* pq);//出队列
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//返回队列中有效数个数
QDataType QueueFront(Queue* pq);//获取队头数据
QDataType QueueBack(Queue* pq);//获取队尾数据
void QueuePrint(Queue* pq);//打印队列(同时会清空队列的元素)
void QueueDestroy(Queue* pq);//销毁队列中动态开辟节点的链表

(3) Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"void QueueInit(Queue* pq)//队列初始化
{assert(pq);pq->head = NULL;pq->tail = NULL;
}void QueuePrint(Queue* pq)//打印整个队列的元素(同时会清空队列的元素)
{assert(pq);while (!QueueEmpty(pq)){printf("%d ", QueueFront(pq));QueuePop(pq);//只有清理了对头元素,才可以继续向后读取数据}
}void QueuePush(Queue* pq, QDataType x)//入队列(单链表的尾插)
{QLNode* newnode = (QLNode*)malloc(sizeof(QLNode));//开辟新节点if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->next = NULL;newnode->data = x;//节点入列的两种情况if (pq->head == NULL)//1.原队列为空{pq->head = pq->tail = newnode;newnode->next = NULL;}else//原队列不为空{pq->tail->next = newnode;pq->tail = newnode;pq->tail->next = NULL;}
}void QueuePop(Queue* pq)//出队列,单链表的头删
{assert(pq);assert(!QueueEmpty(pq));//删除时队列不能为空QLNode* next = pq->head->next;free(pq->head);pq->head = next;
}bool QueueEmpty(Queue* pq)//判断队列是否为空
{assert(pq);return pq->head == NULL;
}int QueueSize(Queue* pq)//返回队列中有效数个数
{assert(pq);QLNode* cur = pq->head;int num = 0;while (cur)//遍历队列中的单链表{num++;cur = cur->next;}return num;
}QDataType QueueFront(Queue* pq)//获取队头数据
{assert(pq);assert(!QueueEmpty(pq));//队列不能为空return pq->head->data;
}QDataType QueueBack(Queue* pq)//获取队尾数据
{assert(pq);assert(!QueueEmpty(pq));//队列不能为空return pq->tail->data;
}void QueueDestroy(Queue* pq)//销毁队列中动态开辟节点的链表
{assert(pq);while (pq->head){QLNode* next = pq->head->next;free(pq->head);pq->head = next;}
}

总结：

栈与队列的实现最重要的是结构以及对链表，顺序表的理解程度，这里再强调一次：数据结构的学习中结构的理解十分重要，所以我们可以多画画相关的图，再结合图理解这样一定可以事半功倍。栈与队列的介绍就到这里结束，谢谢大家的阅读，再见。


http://www.ppmy.cn/news/20924.html

相关文章

【项目精选】基于Web的机票预订系统

【项目精选】基于Web的机票预订系统

文章目录 1 摘 要2 系统相关技术概述2.1 Java web2.2 三大框架SSM2.3 前端框架AngularJS2.4 数据库MySQL2.5 数据库Redis2.6 开发工具Eclipse 3 需求分析3.1 系统实现目标3.2 系统功能分析3.3 系统用列图 4 系统总体设计4.1 软件架构设计4.2 总体功能模块设计4.3 数据库设计4…
阅读更多...
数组中reduce方法详解

数组中reduce方法详解

数组的方法有很多&#xff0c;但是有很多刚入行的小伙伴最容易忽略掉reduce()方法&#xff0c;忽略的原因无非就是因为理解不动reduce(),那么今天兔叽带你详细的将它收纳进自己的知识库中。reduce简介及用途1.首先我们要明白redeuce是干什么的&#xff1f;2.我们再要明白什么时…
阅读更多...
电商前台项目（五）：完成加入购物车功能和购物车页面

电商前台项目（五）：完成加入购物车功能和购物车页面

Vue2项目前台开发&#xff1a;第五章一、加入购物车1.路由跳转前先发请求把商品数据给服务器&#xff08;1&#xff09;观察接口文档&#xff08;2&#xff09;写接口&#xff08;3&#xff09;dispatch调用接口传数据&#xff08;4&#xff09;判断服务器是否已经收到商品数据…
阅读更多...
华为OD机试 - 统一限载货物数最小值

华为OD机试 - 统一限载货物数最小值

题目描述 火车站附近的货物中转站负责将到站货物运往仓库，小明在中转站负责调度2K辆中转车（K辆干货中转车，K辆湿货中转车）。 货物由不同供货商从各地发来，各地的货物是依次进站，然后小明按照卸货顺序依次装货到中转车，一个供货商的货只能装到一辆车上，不能拆装，但是…
阅读更多...
PyQt5开发环境搭建 1.3 Python语法练习

PyQt5开发环境搭建 1.3 Python语法练习

第一组练习1阅读理解。输入红色框框中命令。说出文中大致意思。&#xff08;限30个字&#xff09;解&#xff1a;点击运行之后会跳到一个网站https://xkcd.com/353/练习2建立如下py文件并运行&#xff0c;贴出在Eric6下运行输出结果&#xff08;注意文件名中的bkjtest用自己的姓…
阅读更多...
【C++】类型转换

【C++】类型转换

​&#x1f320; 作者&#xff1a;阿亮joy. &#x1f386;专栏&#xff1a;《吃透西嘎嘎》 &#x1f387; 座右铭&#xff1a;每个优秀的人都有一段沉默的时光&#xff0c;那段时光是付出了很多努力却得不到结果的日子&#xff0c;我们把它叫做扎根 目录&#x1f449;C语言中的…
阅读更多...
C++基础——C++ 字符串

C++基础——C++ 字符串

C基础——C 字符串C 字符串C 风格字符串C 中的 String 类C 字符串 C 提供了以下两种类型的字符串表示形式&#xff1a; C 风格字符串C 引入的 string 类类型 C 风格字符串 C 风格的字符串起源于 C 语言&#xff0c;并在 C 中继续得到支持。字符串实际上是使用 null 字符 ‘…
阅读更多...
CRPS：贝叶斯机器学习模型的评分函数

CRPS：贝叶斯机器学习模型的评分函数

连续分级概率评分&#xff08;Continuous Ranked Probability Score, CRPS&#xff09;或“连续概率排位分数”是一个函数或统计量&#xff0c;可以将分布预测与真实值进行比较。 机器学习工作流程的一个重要部分是模型评估。这个过程本身可以被认为是常识&#xff1a;将数据分…
阅读更多...
最新文章

Copyright @ 2022~2023