数据结构（栈Stack和队列Queue）
3.1栈和队列的定义和特点3.1.1栈的定义和特点*栈是仅限于表尾进行插入和删除操作的线性表*栈的表尾称为栈顶（top），表头称为栈底(base)。不含元素的空表称为空栈*插入元素到栈顶称为入栈（push），也称压栈*从栈顶删除一个元素称为出栈（pop），也称弹栈*栈是一种后进先出的线性表（LIFO）***已知入栈顺序，求可能的出栈顺序问题*栈的存储结构分...
3.1栈和队列的定义和特点
3.1.1栈的定义和特点
*栈是仅限于表尾进行插入和删除操作的线性表
*栈的表尾称为栈顶（top），表头称为栈底(base)。不含元素的空表称为空栈
*插入元素到栈顶称为入栈（push），也称压栈
*从栈顶删除一个元素称为出栈（pop），也称弹栈
*栈是一种后进先出的线性表（LIFO）
***已知入栈顺序，求可能的出栈顺序问题
*栈的存储结构分为顺序栈和链栈，顺序栈更常见
3.1.2队列的定义和特点
*队列是只允许在表头删除和在表尾插入的线性表（头插尾删）
*允许插入的一端叫队尾（rear），允许删除的一端叫对头（front）
*插入元素到队尾称为入队，在队首删除元素称为出队
*队列是一种先进先出的线性表（FIFO）
*队列的存储结构有顺序队和链队，循环顺序队列最常见
3.2栈和队列常见问题
数值转换，括号匹配，表达式求值——栈
舞伴问题——队列
3.3栈的表示和操作的实现
3.3.1栈的抽象数据类型定义
书p57
3.3.2顺序栈的表示和实现
顺序栈的结构：用一组连续的内存空间依次存放从栈底到栈顶的数据，同时附设top指示栈顶元素的位置，base指针指示栈底元素的位置。
结构定义：
#define MAXSIZE 100
typedef struct{
SElemtype *base; //栈底指针
SElemtype *top; //栈顶指针
int stacksize; //栈可用最大容量，表示有n个元素
}SqStack; *为了操作方便，top通常指向栈顶元素之上的下标地址 
当top==base时，表示栈为空
当top-base==stacksize时，表示栈满
初始化完成后，base始终指向占地元素。base==NULL表示栈不存在。每次压栈，指针top+1，每次出栈，指针top-1
算法3.1顺序栈的初始化
算法步骤：1.为顺序栈分配一个最大容量MAXSIZE的内存空间，使base指向栈底
2.置空栈，即令top==base
3.stacksize职位栈的最大容量MAXSIZE
算法描述：
status InitStack(SqStack &S)
{
S.base = new QElemtype[MAXSIZE]; //分配内存空间
if(!s.base)return ERROR; //判断是否分配成功
S.top = S.base; //置空栈
S.stacksize = MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
return OK;
}算法3.2：判断栈是否为空
算法步骤：判断top是否等于base
算法描述：
bool StackEmpty(SqStack &S)
{
if(S.top==S.base)return TRUE; //栈空的依据：top==base
else return FALSE;
}算法3.3：求顺序栈的元素个数
算法步骤：求top指针和base指针的差值
算法描述：
int StackLength(SqStack S)
{
return S.top-S.base;
}算法3.4：清空顺序栈
算法步骤：令top指针和base指针相同即可
算法描述：
status ClearStack(SqStack &S)
{
if(S.base) //先判断栈是否存在
{
S.top = S.base; //通过指针置空栈即可
return OK;
}
else
return ERROR;
}算法3.5：销毁顺序栈
算法步骤：1.释放掉基地址
2.最大容量置为0，指针置空
算法描述：
status DestroyStack(SqStack &S)
{
if(S.base)
{
delete S.base; //释放内存
S.stacksize = 0; //清除长度
S.base = S.top = NULL;//置空指针
}
return OK;
}算法3.6：顺序栈的入栈
算法步骤：1.判断栈是否满，满了返回ERROR
2.将新元素压入栈顶，栈顶指针+1
notice：如果栈满仍然添加元素则会溢出，称为上溢（OVERFLOW）
算法描述：
status Push(SqStack &S,SElemtype e)
{
if(top-base = S.stacksize) return ERROR; //判断是否栈满
*S.top = e; //赋值
S.top++; //指针上移
return OK;
}算法3.7：顺序栈的出栈
算法步骤：1.判断栈是否为空，若为空则返回ERROR
2.栈顶指针-1，栈顶元素出栈
notice：如果栈空仍然要出栈也会溢出，称为下溢（UNDERFLOW）
算法描述：
status Pop(SqStack &S,SElemtype e)
{
if(top==base) return ERROR; //判断是否栈空
S.top--; //top指针下移
e = *S.top; //元素e出栈
return OK;
}注：上溢一般是一种错误，而下溢一般是一种结束条件
算法3.8：取顺序栈的栈顶元素
算法步骤：取值
算法描述：
SElemtype GetTop(SqStack S)
{
if(!S.top==S.base) //保证栈非空
return *(S.top-1);
}3.3.3链栈的表示和实现
链栈通常以单链表来实现，定义如下
typedef struct StackNode
{
Elemtype data;
struct StackNode *next;
}StackNode,*LinkStack;*链栈的头指针就是栈顶
*链栈没有头结点（区别链队）
*基本不存在栈满的情况
*空栈相当于头指针置空
*插入和删除都在栈顶进行（头插法等）
链栈的结构示意：
与单链表（a1->a2.....->an）顺序不同，链栈的指针方向实际上指向的是前驱结点（an->....a2->a1）
算法3.9初始化链栈
算法步骤：构造一个空栈，头指针置空
算法描述：
status InitStack(LinkStack &S)
{
S = NULL; //构造一个空栈，头指针置空
return OK;
}算法3.10：判断链栈为空
算法步骤：判断头指针是否为空即可
算法描述：
bool StackEmpty(LinkStack S)
{
if(!S) return TRUE;
else return FALSE;
}算法3.11：链栈的入栈
算法步骤：1.为入栈元素e分配空间，指针p指向
2.新结点数据域置为e
3.将新结点插入栈顶
4.修改栈顶指针为p
算法描述：
status Push(LinkStack &S,SElemtype e)
{
LinkStack *p = new LinkStack; //开辟新的内存空间
p->data = e; //新空间数据域为e
p->next = S; //新结点接在原来的头结点前
S = p; //更改头指针指向
return OK;
}算法3.12：链栈的出栈
算法步骤：1.判断链栈是否为空，空返回ERROR
2.将栈顶元素赋给e
3.临时保存栈顶元素的空间，以备释放
4.修改栈顶指针，指向新的栈顶元素
5.释放原栈顶元素的空间
算法描述：
status Pop(LinkStack &S,SElemtype &e)
{
if(!S) return ERROR; //判断链栈是否为空
e = S->data; //保存栈顶数据
LinkStack *p = S; //保存要栈顶空间的位置
S = S->next; //头指针指向下一位置
delete p; //删除原栈顶
return OK;
}算法3.13：取栈顶元素
算法步骤：直接取头指针所指结点的数据即可
算法描述：
SElemtype GetTop(LinkStack S)
{
if(!S) return ERROR;
else
return S->data;
}3.4栈与递归
p61
3.5队列的表示与实现
3.5.1队列的抽象数据类型定义 p69
3.5.2队列的顺序表示和实现——循环队列
对于顺序队，除了用一组连续的地址来储存元素外，还需另设front和rear指针分别指向队头和队尾
顺序队的类型定义：
#define MAXSIZE 100
typedef struct
{
QElemtype *base; //存储空间的基地址
int front; //队头指针
int rear; //队尾指针
}SqQueue;初始化创建空队列时，令front=rear=0.每当添加新的尾元素时，rear增1，每当删除一个头元素时，front增1。尾指针始终指向尾元素的下一位置
顺序队列的结构示意图：
问题1：如何解决假溢出
如上右图，此时已不可再插入新的尾元素，而队列的内存空间并未真正填满。这种状态称为假溢出：front != 0;rear == maxsize；
解决方法：可以通过使用循环队列的方法来解决假溢出问题：头尾指针均使用模运算实现增减，队列可以想象成一个环状结构
即：Q.rear == (Q.rear+1)%MAXSIZE;
问题2：如何判断循环队列是否为空
循环队列队满或队空时，都有front=rear，则无法通过该点判断空满
解决方法：1.少用一个元素空间。即队列空间为m时，有m-1个元素即视为队满
队空的条件：front == rear
队满的条件：front==（rear+1）%MAXSIZE
2.设置count计数
3.另设一个标志来表示队空或队满
算法3.14初始化循环队列
算法步骤：1.为队列分配一个最大容量为MAXSIZE的内存空间，base指向首地址
2.头指针和尾指针置空
算法描述：
status InitQueue(SqQueue &Q)
{
QElemtype base = new QElemtype[MAXSIZE]; //分配内存空间
if(!Q.base) exit(OVERFLOW); //判断是否分配成功
Q.front=Q.rear=0; //指针置空
return OK;
}算法3.15求循环队列的长度
算法步骤：考虑到循环队列front可能>rear，仍然采用取模方式
算法描述：
int QueueLength(SqQueue &Q)
{
return (rear - front + MAXSIZE)%MAXSIZE;
}算法3.16：循环队列的入队
算法步骤：1.判断是否队满
2.将新元素插入到队尾
3.尾指针增1
算法描述：
status EnQueue(SqQueue &Q,QElemtype e)
{
if(!(rear + 1)%MAXSIZE) return ERROR; //判断是否队满
Q.base[Q.rear] = e; //插入元素
Q.rear = (Q.rear + 1)%MAXSIZE; //尾指针增1
return OK;
}算法3.17：循环队列的出队
算法步骤：1.判断是否队空
2.保存队头元素
3.头指针增1
算法描述：
status DeQueue(SqQueue &Q,QElemtype &e)
{
if(Q.rear==Q.front) return ERROR； //判断是否队空
e = Q.base[Q.front]; //保存队头元素
Q.front = (Q.front + 1)%MAXSIZE; //头指针上移
return OK;算法3.18：取队头元素:
算法步骤：取队头元素
算法描述：
QElemtype GetHead(SqQueue Q)
{
if(Q.front!=Q.rear) //判断队列非空
return Q.base[Q.front];
}3.5.3链队的表示和实现
链队通常以单链表来实现，显然需要两个指针分别指示队头和队尾。为了方便，给链队添加一个头结点，并令头指针指向头结点。（区别链栈没有头结点）
链队的类型定义：
typedef struct QNode
{
QElemtype data;
struct QNode *next;
}QNode,*QueuePtr;
————————————————————链队的结点
typedef struct
{
QueuePtr front; //指针类型
QueuePtr rear; //指针类型
}LinkQueue;
————————————————————链队的指针 链队的结构示意图：
算法3.19初始化链队
算法步骤：1.生成新结点作为头结点，头指针和尾指针指向该结点
2.头结点指针域置空
算法描述：
status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = new QNode; //生成新结点
Q.front->next = NULL; //头结点的指针域置空
return OK;
}算法3.20销毁链队
算法步骤：从头结点开始，依次释放所有结点
算法描述：
status DestryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear = Q.front->next;
delete Q.front;
Q.front = Q.rear;
}
return OK;
}算法3.21链队的入队
算法步骤：1.为入队元素分配新结点，用p指向，数据域置为e
2.新结点插入到队尾
3.尾指针置为p
算法描述：
status EnQueue(LinkQueue &Q,QElemtype e)
{
QNode* p = new QNode; //生成新结点
p->data = e; //新结点数据域置为e
Q.rear->next = p; //新结点连接到原尾结点后
p->next = NULL;
Q.rear = p; //尾指针指向新的尾结点
return OK;
}算法3.22链队的出队
算法步骤：1.判断队列是否为空，空返回ERROR
2.临时保存队头元素的空间，以备释放
3.修改头结点指针域，指向下一节点
4.判断出队元素是否是最后一个，如果是，尾指针重新赋值，指向头结点
5.释放原头结点的空间
算法描述：
status DeQueue(LinkQueue &Q,QElemtype &e)
{
if(Q.front==Q.rear) return ERROR; //若队空则返回ERROR
QNode* p = Q.front->next; //设置新指针指向待删除结点
e = p->data; //保存数据
Q.front->next = Q.front->next->next; //头结点连接到下一结点
if(Q.rear==p) Q.rear = Q.front; //如果删除的是最后一个元素，要为尾指针重新赋值
delete p; //删除队头元素
return OK;
}算法3.23取链队队头元素
算法描述：
QElemtype GetHead(LinkQueue Q)
{
return Q.front->next->data;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献3条内容
所有评论(0)