建设网站制,找不到网页,龙华城市建设局网站,微信企业网站 源码文章主题#xff1a;顺序表和链表详解#x1f331;所属专栏#xff1a;深入理解数据结构#x1f4d8;作者简介#xff1a;更新有关深入理解数据结构知识的博主一枚#xff0c;记录分享自己对数据结构的深入解读。#x1f604;个人主页#xff1a;[₽]的个人主页#x… 文章主题顺序表和链表详解所属专栏深入理解数据结构作者简介更新有关深入理解数据结构知识的博主一枚记录分享自己对数据结构的深入解读。个人主页[₽]的个人主页 栈和队列详解 前言栈栈的概念及结构栈的实现 队列队列的概念及结构队列的实现 结语 前言
上文我们已经讲完了线性表中最基本的、最常用的顺序表和链表这一次博主为大家带来基于顺序表和链表实现的线性表中也是十分常用的数据结构栈和队列的详解希望能够让你对数据结构有一个更加深入的理解。 栈
栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈/弹栈。出数据也在栈顶。
栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小最简单。 静态数组栈 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
// 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;动态数组栈 Stack.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;
// 初始化栈
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);Stack.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Stack.h
void StackInit(Stack* ps)
{assert(ps);// 栈区数组未创建赋成NULLps-_a NULL;ps-_capacity 0;// 表示top指向栈顶元素ps-_top -1;// 表示top指向栈顶元素的下一个//ps-_top 0
}
void StackPush(Stack* ps, STDataType data)
{assert(ps);// 栈区数据已满扩容if (ps-_top 1 ps-_capacity){// 确定扩容后的新容量如果是 0 就扩容为 4 如果已经扩过容了就将容量在增加一个原来这么多即扩大为原来的两倍int newcapacity ps-_capacity 0 ? 4 : ps-_capacity * 2;// 扩容STDataType* tmp (STDataType*)realloc(ps-_a, newcapacity * sizeof(STDataType));// 扩容失败打印失败原因后返回if (tmp NULL){perror(realloc fail);return;}// 未失败将容量更新成新容量数据指针更新成新指针ps-_capacity newcapacity;ps-_a tmp;}// 插入数据ps-_top;ps-_a[ps-_top] data;
}
void StackPop(Stack* ps)
{assert(ps);// 栈不为空时才能删除数据assert(ps-_top 1 0);// 栈顶元素坐标下移删除数据ps-_top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);// 不为空为空弹不出数据来进行访问并且访问会导致数组越界assert(ps-_top 1 0);// 返回栈顶元素值return ps-_a[ps-_top];
}
int StackSize(Stack* ps)
{assert(ps);// 返回栈中有效元素个数栈顶元素 1 即为栈中有效元素个数return ps-_top 1;
}
int StackEmpty(Stack* ps)
{assert(ps);// 为空则返回非 0 的真return ps-_top 1 0;
}
void StackDestroy(Stack* ps)
{assert(ps);// 数据内存释放再将记录数据的各值清空free(ps-_a);ps-_a NULL;ps-_capacity 0;ps-_top -1;
}Test.c
#include Stack.h
void StackTest1()
{// 初始化栈Stack S1;StackInit(S1);// 数据入栈StackPush(S1, 1);StackPush(S1, 2);StackPush(S1, 3);StackPush(S1, 4);StackPush(S1, 5);// 销毁栈StackDestroy(S1);// 检测是否销毁成功if (S1._a NULL S1._capacity 0 S1._top -1)printf(销毁成功\n);elseprintf(销毁失败。\n);
}
void StackTest2()
{// 初始化栈Stack S1;StackInit(S1);// 数据入栈StackPush(S1, 1);StackPush(S1, 2);StackPush(S1, 3);StackPush(S1, 4);StackPush(S1, 5);// 从栈顶读取数据后弹出栈中数据while (!StackEmpty(S1)){printf(%d , StackTop(S1));StackPop(S1);}printf(\n);// 销毁栈StackDestroy(S1);
}
void StackTest3()
{// 初始化栈Stack S1;StackInit(S1);// 栈为空时也弹出数据StackPop(S1);// 销毁栈StackDestroy(S1);
}
int main()
{StackTest3();return 0;
}队列
队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 入队队列的插入操作叫做入队入数据在队尾。 出队队列的删除操作叫做出队。出数据在队头。 栈和对列都是将出数据的地方叫作顶/头
队列的实现
队列也可以数组和链表的结构实现使用链表带头的单链表的结构实现更优一些(时间复杂度O(1)比数组来说在队头删除数据更加简洁)因为如果使用数组的结构出队列在数组头上出数据效率会比较低(时间复杂度为O(N))。 队列 Queue.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.htypedef int QDataType;
// 链式结构表示队列
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 队列的结构
typedef struct Queue
{QNode* _front;QNode* _rear;int _size;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 销毁队列
void QueueDestroy(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
int QueueEmpty(Queue* q);Queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Queue.h
void QueueInit(Queue* q)
{assert(q);// 首尾指针都赋成NULL元素个数赋0q-_front q-_rear NULL;q-_size 0;
}
void QueueDestroy(Queue* q)
{assert(q);// 释放队列数据内存QNode* cur q-_front;while (cur){QNode* tmp cur;cur cur-_next;free(tmp);}// 将队列中的首尾指针数据赋成NULL队列元素个数也置为0q-_front q-_rear NULL;q-_size 0;
}
void QueuePush(Queue* q, QDataType data)
{assert(q);// 创建新节点QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(maloc fail);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)
{assert(q);// 无节点assert(q-_front);// 有节点QNode* tmp q-_front;q-_front q-_front-_next;free(tmp);// 一个节点时尾指针因为释放节点变成野指针需要置空if (q-_front NULL)q-_rear NULL;// 队头出数据时总元素个数减一q-_size--;
}
QDataType QueueFront(Queue* q)
{assert(q);// 无节点assert(q-_front);// 有节点return q-_front-_data;
}
QDataType QueueBack(Queue* q)
{assert(q);// 无节点assert(q-_front);// 有节点return q-_rear-_data;
}
int QueueSize(Queue* q)
{assert(q);// 直接将储存队列主要数据的结构体中的元素个数拿出来返回return q-_size;
}
int QueueEmpty(Queue* q)
{assert(q);return q-_size 0;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Queue.h
void QueueTest1()
{// 队列初始化Queue Q1;QueueInit(Q1);// 队尾入数据QueuePush(Q1, 1);QueuePush(Q1, 2);QueuePush(Q1, 3);QueuePush(Q1, 4);QueuePush(Q1, 5);// 销毁队列QueueDestroy(Q1);if (Q1._front NULL Q1._rear NULL Q1._size 0)printf(销毁成功\n);elseprintf(销毁失败。\n);
}void QueueTest2()
{// 队列初始化Queue Q1;QueueInit(Q1);// 队尾入数据QueuePush(Q1, 1);QueuePush(Q1, 2);QueuePush(Q1, 3);QueuePush(Q1, 4);QueuePush(Q1, 5);// 打印队列中的数据printf(Queue: \n);while (!QueueEmpty(Q1)){printf(%d , QueueFront(Q1));QueuePop(Q1);}printf(\n);// 销毁队列QueueDestroy(Q1);
}void QueueTest3()
{// 队列初始化Queue Q1;QueueInit(Q1);// 队尾入数据QueuePush(Q1, 1);QueuePush(Q1, 2);QueuePush(Q1, 3);QueuePush(Q1, 4);QueuePush(Q1, 5);// 打印队列中的数据printf(Queue: \n);while (!QueueEmpty(Q1)){printf(%d , QueueFront(Q1));QueuePop(Q1);}printf(\n);// 无节点从队列中弹出数据QueuePop(Q1);// 销毁队列QueueDestroy(Q1);
}void QueueTest4()
{// 队列初始化Queue Q1;QueueInit(Q1);// 队尾入数据QueuePush(Q1, 1);QueuePush(Q1, 2);QueuePush(Q1, 3);QueuePush(Q1, 4);QueuePush(Q1, 5);// 打印队尾中的数据printf(BackNum: \n%d\n, QueueBack(Q1));// 打印队列中的数据printf(Queue: \n);while (!QueueEmpty(Q1)){printf(%d , QueueFront(Q1));QueuePop(Q1);}printf(\n);// 销毁队列QueueDestroy(Q1);
}void QueueTest5()
{// 队列初始化Queue Q1;QueueInit(Q1);// 队尾入数据QueuePush(Q1, 1);QueuePush(Q1, 2);QueuePush(Q1, 3);QueuePush(Q1, 4);QueuePush(Q1, 5);// 打印队列中的数据个数printf(QueueSize: \n%d\n, QueueSize(Q1));// 打印队列中的数据printf(Queue: \n);while (!QueueEmpty(Q1)){printf(%d , QueueFront(Q1));QueuePop(Q1);}printf(\n);// 销毁队列QueueDestroy(Q1);
}int main()
{QueueTest5();return 0;
}环形队列 另外扩展了解一下实际中我们有时还会使用一种队列叫循环队列。如操作系统中的生产者消费者模型中就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现差别不是很大并且环形队列的元素个数是固定的但也可以不是在栈区的静态数组实现的其可用在动态区用长度不变的数组来实现内存大小不变的效果可理解成动态数组大小不变所实现的仿静态效果并且虽逻辑结构上两种环形队列都相接数组型的环形队列物理结构上首尾不相接链表物理结构上相接。 通常为区分队头和队尾会在数组中多加一个元素来既防止数组越界又能够解决因空和满索引条件相同而造成无法判断的假溢出问题此时环形队列容量为数组总元素个数减一 结语
以上就是博主对栈和队列的详解希望对你的数据结构的学习有所帮助看都看到这了点个小小的赞或者关注一下吧当然三连也可以~你的支持就是博主更新最大的动力让我们一起成长共同进步
