文档介绍：第三章第三章栈和队列栈和队列 栈栈————存储结构存储结构 队列队列————存储结构存储结构【例】栈 S = ( A, B, C, D,E ) 一、顺序存储: 顺序栈( 静态和动态) top base 空栈: top= =base top base A B C D E满栈: top= =5 静态: char s[5]; 动态: malloc ( sizeof ( char ) * 5 ); 注: 栈有栈顶、栈底、栈容量。?顺序栈的动态分配 typedef struct { char * base; char * top; int stacksize ; } SqStack ; top 1 2 3 4 50进栈 A 栈满 B C D E F top top top top top1 2 3 4 50 空栈 top base base top top 出栈 1 2 3 4 50 A B C D E F top top top top 栈空 base top top top 【例】栈 S = ( A, B, C, D,E ) 二、链式存储: 链栈( 动态)∧ ED CB A 队列的链式存储队列的链式存储————链队列链队列队列的顺序存储队列的顺序存储————循环队列循环队列?【例】队列 Q = ( a, b, c, d ) a ∧d front ∧空队列 b rearc rear front typedef struct QNode { // 结点类型 char data ; struct QNode * next ; } QNode , * QueuePtr ; typedef struct { //链队列类型 QNode * front ; //队头指针 QNode * rear ; //队尾指针} LinkQueue ; ?链队列的实现?队列 Q = (a, b, c, d, e, f ) 1 2 3 4 50空队列 rear=0 front=0 a b c rear rear 1 2 3 4 50 d,e,f 入队 d e f front rear rear 1 2 3 4 50 front a,b,c 入队 rear 1 2 3 4 50 a,b,c 出队 a b c front front front front ?存在问题: ?当 front=0,rear=6 时,再有元素入队发生溢出——真溢出?当 front ≠ 0,rear=6 时,再有元素入队发生溢出——假溢出?解决方案?循环队列?基本思想:把队列设想成环形,让 base[0] 接在 base[M-1] 之后,若 rear+1==M, 则令 rear=0; ?实现:利用“模”运算?入队: base[rear] = e; rear = (rear+1)%M; ?出队: e = base[front]; front = (front+1)%M; ?队满、队空判定条件