数据结构--堆栈和队列
数据结构
仔细看完课本,发现堆栈和队列并没有自己理解的那么困难
在逻辑结构上,堆栈和队列都是线性表
在存储结构上,都可以划分为顺序结构和链表结构
在运算结构上,堆栈是后进先出,队列是先进先出。
可以将堆栈和数列理解为运算受限的线性表
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
下面是我课前预习收集整理的资料,受益匪浅 侵权立删
堆栈和队列(数据结构)
(1)堆栈
基本概念
(a)定义:限定只能在固定一端进行插入和删除操作的线性表。
特点:后进先出。
(b)允许进行插入和删除操作的一端称为栈顶,另一端称为栈底。
作用:可以完成从输入数据序列到某些输出数据序列的转换。
堆栈抽象数据类型
数据集合:
{a0,a1,…,an-1} ,ai的数据类型为DataType。
操作集合:
(a) StackInitiate(S) :初始化堆栈S
(b) StackNotEmpty(S):堆栈S非空否
(c)StackPush(S, x) :入栈
(d)StackPop(S, d):出栈
(e)StackTop(S, d):取栈顶数据元素
堆栈类型
(a)顺序堆栈
顺序堆栈:顺序存储结构的堆栈。
顺序栈的存储结构:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。
数据结构:
typedef struct
{
DataTypestack[MaxStackSize];
int top;
}SeqStack;
(b)链式堆栈
链式堆栈:链式存储结构的堆栈。
链式栈的存储结构:它是以头指针为栈顶,在头指针处插入或删除,带头结点的链式堆栈结构:
链栈中每个结点由两个域构成:data域和next域。
结点结构体定义如下
typedef struct snode
{
DataType data;
struct snode *next;
} LSNode;
采用链栈存储方式的优点是:当栈中元素个数变化较大,准确数字难以确定时,链栈较顺序堆栈方便。
(2)队列
基本概念
定义:只能在表的一端进行插入操作(队尾),在表的另一端进行删除操作的线性表(队头)。一个队列的示意图如下:
队列抽象数据类型
数据集合:{a0,a1,…,an-1},ai的数据类型为DataType。
操作集合:
(a)初始化QueueInitiate(Q)
(b)非空否QueueNotEmpty(Q)
(c)入队列QueueAppend(Q,x)
(d)出队列QueueDelete(Q,d)
(e)取队头数据元素QueueGet(Q, d)
队列类型:
(a)顺序队列
顺序队列:顺序存储结构的队列。
顺序队列的存储结构:有6个存储空间的顺序队列动态示意图如下。
顺序队列的“假溢出”问题:因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况。
可采取四种方法解决://前一种方法自然是最为常用的 但是没有学习数据结构之前,后面三种都可以解决类似的问题
1)采用顺序循环队列;
2)按最大可能的进队操作次数设置顺序队列的最大元素个数(最差的方法);
3)修改出队算法,使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置;
4)修改入队算法,增加判断条件,当假溢出时,把队列中的数据元素向对头移动,然后方完成入队操作。
(b)顺序循环队列
基本原理:把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后,再前进一个位置就自动到0。
顺序循环队列的队空和队满判断问题:
在顺序循环队列中,队空特征是front=rear,队满时也会是front=rear,判决条件将出现二义性,解决方案有三:
1)使用一个计数器记录队列中元素个数(即队列长度);
判队满:count>0 && rear==front
判队空:count==0
2)设标志位:出队时置0,入队时置1,则可识别当前front=rear 属于何种情况;
判队满:tag==1 && rear==front
判队空:tag==0 && rear==front
3)少用一个存储单元
判队满:front=(rear+1)%MaxQueueSize
判队空:rear==front
顺序循环队列的结构体定义如下:
typedef struct
{
DataType queue[MaxQueueSize];
int rear;
int front;
int count;
} SeqCQueue;
(c)链式队列
链式队列:链式存储结构的队列。
链式队列的存储结构:链式队列的队头指针指向队列的当前队头结点;队尾指针指在队列的当前队尾结点。一个不带头结点的链式队列的结构。
结点的结构体可定义如下:
typedef struct qnode
{
DataTypedata;
struct qnode*next;
}LQNode;
队头指针front和队尾指针rear的结构体类型:
typedef struct
{
LQNode *front;
LQNode *rear;
}LQueue;
(d)优先级队列
优先级队列:带有优先级的队列。
顺序优先级队列:用顺序存储结构存储的优先级队列。
优先级队列和一般队列的主要区别:优先级队列的出队列操作不是把队头元素出队列,而是把队列中优先级最高的元素出队列。
它的数据元素定义为如下结构体:
struct DataType
{
ElemType elem;//数据元素
int priority; //优先级
};
注:顺序优先级队列除出队列操作外的其他操作的实现方法与前边讨论的顺序队列操作的实现方法相同。
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
整理的很好,我只是略加修改
希望每一位努力的小伙都能得到应获得的
最近在关注陶崇园事件,以后我也要考研
我为他发声,也是为自己