文档介绍：栈与队列
1
第10次课栈与队列
主要内容
链式结构复习(单链表,循环链表,链栈)
双栈结构的实现(程序示例)
循环队列复习
运动会比赛安排(链队实现)
2
1、双栈结构
为同时出现的两个栈共同开辟一存储空间,两个栈的栈底设于存储空间的两端
b1
b2
…
bs
……
an
…
a2
a1
栈2底
栈2顶
top2
栈1顶
top1
栈1底
优点: 两栈互补余缺充分利用存储空间。
3
双栈的存储结构定义
typedef struct {
ElemType *elem; //待分配存储空间
int top1;//队头指针
int top2; //队尾指针
} DStack;
;
4
双栈操作
栈初始化 InitDStack(DStack &ds )
入栈 PushDStack(DStack &ds,ElemType elem,int iFlag)
出栈 OutDStack(DStack &ds,ElemType &elem,int iFlag)
判栈空 IsEmpty(Dstack ds,int iflag)
判栈满 IsFull(DStack ds)
销毁栈 DestroyDStack(Dstack &ds)
5
2、循环队列复习
队列的顺序存储结构
typedef struct {
ElemType *elem; //待分配存储空间
int front;//队头指针
int rear; //队尾指针
} SeqQueue ;
a1
a2
a3
a4
a5
…
存储空间
6
循环队列操作
0
1
2
3
4
5
6
7
InitQueue(SeqQueue &sq)
{ =new ElemType[MAXSIZE];//MAXSIZE
= = 0;
}
InQueue(SeqQueue &sq,ElemType e)
InitQueue(SeqQueue &sq)
OutQueue(SeqQueue &sq,ElemType &e)
Destroy(SeqQueue &sq)
7
循环队列操作
0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
InQueue(SeqQueue &sq,ElemType e)
InitQueue(SeqQueue &sq)
OutQueue(SeqQueue &sq,ElemType &e)
Destroy(SeqQueue &sq)
8
循环队列操作
0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
a7
InQueue(SeqQueue &sq,ElemType e)
InitQueue(SeqQueue &sq)
OutQueue(SeqQueue &sq,ElemType &e)
Destroy(SeqQueue &sq)
InQueue(SeqQueue &sq, ElemType e)
{ if((+1)%MAXSIZE ! = )
[]=e;
= (+1)%MAXSIZE;
}
9
循环队列操作
InQueue(SeqQueue &sq,ElemType e)
InitQueue(SeqQueue &sq)
OutQueue(SeqQueue &sq,ElemType &e)
Destroy(SeqQueue &sq)
OutQueue(SeqQueue &sq, ElemType &e)
{ if(!=)
{e = [];
=(+1)%MAXSIZE;} }
0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
a7
10