数据结构之栈和队列(超详解

server/2024/9/24 6:50:25/

目录

一.栈

1.栈的基本概念

2.栈的基本操作

3.栈的储存结构

 ①栈的顺序储存

(1)基本概念

 (2)代码实现

②栈的链式储存

 (1)基本概念

(2)代码实现

 二.队列

1.队列的基本概念

2.队列的基本操作

3.队列的储存结构

①队列的链式储存

(1)基本概念

​编辑 (2)代码实现

②循环队列

(1)基本概念

 (2)代码实现

一.栈

1.栈的基本概念

栈是一种常见的数据结构，它是一种“后进先出”（Last In First Out，LIFO）的数据结构，即最后放入栈的元素最先被取出。在计算机中，栈通常由一段连续的内存区域组成，它具有两个基本操作：压栈（Push）和弹栈（Pop）。

压栈将一个元素放入栈顶，弹栈将栈顶元素取出并从栈中删除。

除此之外，栈还具有一个特点：访问栈顶元素的时间复杂度是 O(1)，也就是说，无论栈中有多少元素，访问栈顶元素的时间复杂度都是常数级别的。

2.栈的基本操作

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

3.栈的储存结构

链式储存的栈相比于顺序储存的栈具有更好的动态性和灵活性，因为链式储存的栈可以动态地扩展或缩小，不需要事先确定储存空间的大小。但是由于链式储存需要使用指针，因此它的空间开销较大，同时由于每个节点都需要动态分配内存，所以它的时间开销也会相对较大。

 ①栈的顺序储存

(1)基本概念

栈是一种线性数据结构，可以通过数组实现顺序储存。栈的顺序储存特点是使用数组作为底层数据结构，只能从一端插入和删除元素，这一端被称为栈顶。栈的顺序储存还需要记录栈顶指针，用来指向当前栈顶元素的位置。

 (2)代码实现

栈的顺序存储结构可描述为：

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 栈顶int _capacity;  // 容量 
}Stack;

基本操作:

#include<stdlib.h>
#include<assert.h>
// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_capacity = 0;//top指向栈顶的下一个元素ps->_top = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);if (ps->_capacity == ps->_top) {ps->_capacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* newnode = (STDataType)realloc(ps->_a,sizeof(STDataType) * ps->_capacity);if (newnode==NULL){perror("realloc:");return;}ps->_a = newnode;}ps->_a[ps->_top] = data;ps->_top++;
}
// 出栈 
void StackPop(Stack* ps)
{assert(ps);assert(ps->_a);ps->_top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_a);return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);return ps->_top==0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{ps->_a = NULL;ps->_capacity = 0;ps->_top = 0;
}

代码测试:

#include<stdio.h>
int main()
{Stack s;StackInit(&s);StackPush(&s, 1);StackPush(&s, 2);StackPush(&s, 3);StackPush(&s, 4);printf("栈中有%d个数字\n", StackSize(&s));while (!StackEmpty(&s)) {printf("%d\n", StackTop(&s));StackPop(&s);}StackDestroy(&s);return 0;
}

 

②栈的链式储存

 (1)基本概念

栈的链式储存是将栈中的元素通过链表的方式进行储存。

具体来说，链式储存的栈由两个部分组成：栈顶指针和链表。

其中，栈顶指针指向链表中的第一个元素，每次入栈操作都会将新元素插入到链表头部并更新栈顶指针，而出栈操作则是删除链表头部元素并更新栈顶指针。如果栈为空，则栈顶指针为空指针。

(2)代码实现

栈的链式储存结构可描述为:

/*构造节点*/
typedef struct StackNode{SElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{LinkStackPrt top;int count;
}LinkStack;

基本操作:

#include<stdio>
#include<stdlib>
#define OK 1
#define ERROR 0
typedef int SElemType; 
typedef int Status; //初始化链栈
Status InitLinkStack(LinkStack **S)
{*S = (LinkStack*)malloc(sizeof(LinkStack)); //申请内存空间if ((*S) == NULL) //判断申请内存空间是否成功{printf("申请内存空间失败，初始化失败！\n"); //输出提示语return ERROR;}(*S)->top = NULL; //栈为空时，为NULL,这样最后一个结点的指针域为NULL(*S)->count = -1; //链栈为空时，赋值为-1printf("初始化成功！\n"); //输出提示语return OK;
}//建立链栈
Status CreateLinkStack(LinkStack *S)
{int i = 0;SElemType e;StackNode *N;printf("请输入元素(每个元素之间空格分开，最后一个元素输入后直接换行)：");do{scanf("%d", &e);N = (StackNode*)malloc(sizeof(StackNode)); //创建结点申请内存空间if (N == NULL) //判断申请内存空间是否成功{printf("申请内存空间失败，无法继续创建结点！"); //输出提示语return ERROR;}N->data = e; //将e的值赋值给结点N的数据域N->next = S->top; //由于链栈的栈顶在链头，所以入栈操作，插入的新结点的指针域要指向原来的栈顶S->top = N; //将N结点成为栈顶S->count++; //链栈长度加一} while(getchar()!='\n'); //判断为换行时 输入结束printf("所有元素入栈成功！\n");return OK;
}//压栈(与链表的头插操作相似)
Status Push(LinkStack *S, SElemType e){LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));p->data = e;p->next = S->top;    //把当前的栈顶元素赋值给新节点的直接后继S->top = p; //将新的结点S赋值给栈顶指针S->count++;return OK;
}//判断栈是否为空
bool StackEmpty(LinkStack *S)
{if (S->count == -1) //判断是否为空栈{return true;}return false;
}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
//弹栈(与链表的头删操作相似)
Status Pop(LinkStack *S, SElemType *e){LinkStackPrt p;if(StackEmpty(S)){return ERROR;}*e = S->top->data;p = S->top; //将栈顶结点赋值给pS->top = S->top->next;  //使得栈顶指针下移一位，指向后一结点free(p);    //释放结点pS->count--;return OK;
}//输出链栈的元素个数
Status LengthLinkStack(LinkStack *S)
{if (S->count == -1) //判断链栈是否为空栈{printf("链栈为空栈，元素个数为零！\n"); return ERROR;}printf("链栈的元素个数为：%d\n", S->count + 1); return OK;
}//输出栈顶元素
Status OutTop(LinkStack *S)
{if (S->count == -1) //判断链栈是否为空栈{printf("链栈为空栈，没有栈顶元素！\n"); //输出提示语return ERROR;}printf("链栈的栈顶元素为：%d\n", S->top->data); //输出链栈栈顶元素的值return OK;
}
//输出链栈各个元素
Status OutValue(LinkStack *S)
{StackNode *N;int i = 1;if (S->count == -1) //判断是否为空栈{printf("链栈为空栈，没有元素可输出！\n"); //输出提示语return ERROR;}N = S->top; //将栈顶指针赋值给Ndo{printf("第%d个元素为：%d\n", i++, N->data);N = N->next; //N指向下一个结点} while (N != NULL);printf("所有元素按照从栈顶到栈底的顺序完毕！\n"); //输出提示语return OK;
}
//销毁链栈
Status ClearStack(LinkStack *S)
{StackNode *N;if (S->count == -1) //判断链栈是否为空栈{printf("链栈为空栈，不用清空，请勿重复执行此功能！\n");return ERROR;}do{N = S->top; S->top = N->next; //栈顶指针指向N结点的下一个结点 free(N); //释放N所指向的内存空间} while (S->top != NULL); //最后一个结点的指针域指向NULLfree(S->top); //释放最后一个结点S->count = -1; //链栈长度置为-1printf("链栈清空成功！\n"); //输出提示语return OK;
}

代码测试:


int main()
{LinkStack *S;SElemType e;InitLinkStack(&S);//初始化链栈CreateLinkStack(S); //建立链栈LengthLinkStack(S);  //输出链栈的元素个数OutTop(S); //输出链栈栈顶元素//插入指定元素到栈顶printf("要插入的元素的值为：");scanf("%d", &e);Push(S, e);//删除栈顶元素if (Pop(S, &e)){printf("删除成功！\n删除的栈顶元素的值为：%d\n", e);}OutValue(S);  //输出链栈各个元素ClearStack(S);  //清空链栈//链栈是否为空if (StackEmpty(S)){printf("栈为空栈！\n");}else{printf("栈不为空！\n");}free(S);//释放Sreturn 0;
}

 

 二.队列

1.队列的基本概念

队列是一种常用的数据结构，它具有先进先出（FIFO）的特点。

1. 队头：队列的第一个元素。
2. 队尾：队列的最后一个元素。
3. 入队：将一个元素加入到队列的末尾。
4. 出队：从队列的头部删除一个元素。
5. 队列长度：队列中元素的个数。

2.队列的基本操作

队列通常包含两个基本操作：入队和出队。入队将元素加入到队列的末尾，而出队则从队列的头部删除元素。除此之外，队列还包括判空和判满等操作。


// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

3.队列的储存结构

①队列的链式储存

(1)基本概念

链队列:采用链式存储结构实现的队列。通常链队列用单链表来表示。一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队列添加一个头结点，并令头指针始终指向头结点。

 (2)代码实现

存储结构:

// 链式结构：表示队列 
typedef struct QListNode
{QDataType _data;struct QListNode* _next;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;

 基本操作:

#include<assert.h>
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
// 初始化队列 
void QueueInit(Queue* q)
{q->_front = NULL;q->_rear = NULL;q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc:");return;}newnode->_data = data;newnode->_next = NULL;if (q->_front == NULL){q->_front = q->_rear = newnode;}else{q->_rear->_next = newnode;q->_rear = newnode;}q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{if (!QueueEmpty(q)){q->_front = q->_front->_next;}
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q && q->_front);return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q && q->_rear);return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{if (q->size==0){return true;}return false;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{while (q->_front){QNode* p = q->_front;q->_front = q->_front->_next;free(p);p = NULL;}q->_front = q->_rear = NULL;
}

代码测试:

int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("有%d个元素\n", QueueSize(&q));printf("%d ", QueueFront(&q));QueuePop(&q);printf("%d ", QueueFront(&q));QueuePop(&q);printf("%d ", QueueFront(&q));QueuePop(&q);printf("%d ", QueueFront(&q));QueuePop(&q);QueueDestroy(&q);return 0;
}

 

②循环队列

(1)基本概念

循环队列:是将数组的首尾相连，组成的一个特殊结构。头、尾指针以及队列元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增1"的操作可用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。 

 (2)代码实现

储存结构:

typedef struct {int* st;int length, top, tail;
} MyCircularQueue;

基本操作:


#include <stdio.h>
#include <stdlib.h>#define OK 1
#define ERROR 0
#define OVERFLOW -1#define MAXSIZE 7bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
//循环队列的创建
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*) malloc(sizeof(MyCircularQueue));obj->st = (int*) malloc(sizeof(int) * k);obj->top = 0;obj->tail = 0;obj->length = k;return obj;
}
//循环队列入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) return false;obj->st[obj->top] = value;obj->top = (obj->top + 1) % obj->length;return true;
}
//循环队列出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) return false;obj->tail = (obj->tail + 1) % obj->length;return true;
}
//求队头元素
int myCircularQueueFront(MyCircularQueue* obj) {return myCircularQueueIsEmpty(obj) ? -1 : obj->st[obj->tail];
}
//求队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {return myCircularQueueIsEmpty(obj) ? -1 : obj->st[(obj->top + obj->length - 1) % obj->length];
}
//循环队列的判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->top == obj->tail;
}
//循环队列的判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->top + 1) % obj->length == obj->tail;
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->st);free(obj);
}

代码测试:


int main() {MyCircularQueue *sq;//循环队列的创建 sq=myCircularQueueCreate(MAXSIZE);//入队 myCircularQueueEnQueue(sq, 1);myCircularQueueEnQueue(sq, 2);myCircularQueueEnQueue(sq, 3);myCircularQueueEnQueue(sq, 4);int rEnQueue = myCircularQueueEnQueue(sq, 5);if (rEnQueue == OK) {printf("向循环队列入队成功！\n");} else {printf("向循环队列入队失败！\n");}//输出链表元素DisplayQueue(sq);printf("\n");//出队 int rDeQueue = myCircularQueueDeQueue(sq);if (rDeQueue == OK) {printf("向循环队列出队成功！\n");} else {printf("向循环队列出队失败！\n");}//输出链表元素DisplayQueue(sq);printf("\n");//求队头元素int topData = myCircularQueueFront(sq);printf("向循环队列获取队头元素：%d\n", topData);//求队尾元素int tailData = myCircularQueueRear(sq);printf("向循环队列获取队头元素：%d\n", tailData);//判空bool ClearStatus = myCircularQueueIsEmpty(sq);if (ClearStatus == true) {printf("循环队列为空！\n\n");}else {printf("循环队列不为空！\n\n");}//销毁 myCircularQueueFree(sq);return 1;
}

 


http://www.ppmy.cn/server/43053.html

相关文章

2024目前网上最火短剧机器人做法，自动搜索发剧 自动更新资源 自动分享资源

2024目前网上最火短剧机器人做法，自动搜索发剧 自动更新资源 自动分享资源

目前整个项目圈子很多的短剧机器人&#xff0c;我写的&#xff0c;自动搜索发剧&#xff0c;自动更新资源&#xff0c;自动分享资源&#xff0c;前段时间大部分做短剧的都是做的短剧分成&#xff0c;我的一个学员做的30W播放量才200块收益&#xff0c;备受启发&#xff0c;我就…
阅读更多...
光速入门python的OpenCV

光速入门python的OpenCV

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文整理python的OpenCV模块的关键知识点 争取用最短的时间入门OpenCV 并且做到笔记功能直接复制使用 OpenCV简介 不浪费时间的介绍: 就是类似于ps操作图片。 至于为什么不直接用ps&#xff0c;因为只有程序能…
阅读更多...
Ubuntu 整编 AOSP

Ubuntu 整编 AOSP

文章目录 前言1 准备一台Ubuntu系统电脑2 安装依赖工具3 安装 repo4 下载 AOSP 源码5 整编AOSP6 运行 前言 作为Android应用层开发多年, 一直不了解 Framework和Android系统的运行原理真的说不过去。希望本篇博客可以带你构建自己的Android系统&#xff0c;打开通向 Framework…
阅读更多...
M功能-支付平台(三)

M功能-支付平台(三)

target&#xff1a;离开柬埔寨倒计时-221day 前言 今天周六&#xff0c;但是在柬埔寨还是工作日&#xff0c;想着国内的朋友开始休周末就羡慕呀&#xff0c;记不清在这边过了多少个周六了&#xff0c;多到我已经习惯了。而且今天技术部还停电了&#xff0c;真的是热的受不了呀…
阅读更多...
Shell编程之免交互

Shell编程之免交互

目录 1、Here Document免交互 &#xff08;1&#xff09;Here Document 概述 &#xff08;2&#xff09;免交互执行命令 1&#xff09;免交互read赋值 2&#xff09;免交互修改密码 3&#xff09;免交互统计行数 4&#xff09;免交互创建文件并编辑文件内容 5&#xff0…
阅读更多...
Gitee在已有项目基础上创建仓库中遇到的问题和解决

Gitee在已有项目基础上创建仓库中遇到的问题和解决

问题一&#xff1a;fatal: remote origin already exists 解释&#xff1a;当前仓库添加了一个名为"origin"的远程仓库配置&#xff0c;此时输入 git remote add origin https://xxx就会提示上面的内容。 解决方案1:移除旧的origin git remote remove origin 解决方案…
阅读更多...
windows使用gzip和bzip2对文件进行压缩

windows使用gzip和bzip2对文件进行压缩

git软件 git bash&#xff1a;下载地址https://git-scm.com/downloads&#xff0c;安装时一路next。 这个软件是给程序员提交代码用的工具&#xff0c;内置linux系统的命令行&#xff0c;可以使用linux系统特有的压缩软件gzip和bzip2. gzip使用 gzip一般用于压缩tar包&#…
阅读更多...
原型模式（Prototype Pattern）

原型模式（Prototype Pattern）

文章目录 1.原型模式定义2.UML图3.实现方式4.具体实现4.1 接口方式4.2 类继承方式 1.原型模式定义 复制已有对象&#xff0c; 而又无需使代码依赖它们所属的类。 2.UML图 3.实现方式 创建原型接口&#xff0c; 并在其中声明 克隆方法。 如果你已有类层次结构&#xff0c; 则…
阅读更多...
最新文章

Copyright @ 2022~2023