数据结构--3章栈和队

1、2021/3/111 2010-7-21 数据结构2021/3/112 第三章 栈和队列引言：对线性表 L=(a1,a2,.,an), 可在任意第i(i=1,2,.n,n+1)个位置插入新元素， 或删除任意第i(i=1,2,.n)个元素 受限数据结构- 插入和删除受限制的线性表。 1.栈(stack), 2.队列(queue).3.1栈(stack)3.1.1栈的定义和操作 1.定义和术语 栈-限定在表尾作插入、删除操作的线性表。 (a1,a2, ,.，an） 插入元素(进栈) 删除元素(出栈） 表头 表尾 (栈底) (栈顶） 2021/3/113 an a1栈顶(top)栈底(bottom)

2、 出栈(pop) 进栈(push) 进栈-插入一个元素到栈中。或:入栈、推入、压入、push。 出栈-从栈删除一个元素。或：退栈、上托、弹出、pop。 栈顶-表中允许插入、删除元素的一端(表尾)。 栈顶元素-处在栈顶位置的元素。 栈底-表中不允许插入、删除元素的一端。 空栈-不含元素的栈。栈的示意图2021/3/114 栈的元素的进出原则: “后进先出”,“Last In First Out”。 栈的别名: “后进先出”表、“LIFO”表、反转存储器、地窖。 2021/3/1152.栈的基本操作 (1) Initstack(s)-置s为空栈。 (2) Push(s,e)-元素e进栈s。 若s已

3、满，则发生溢出。 若不能解决溢出，重新分配空间失败，则插入失败。 (3) Pop(s,e)-删除栈s的顶元素，并送入e 。 若s为空栈,发生“下溢”(underflow)； 为空栈时，表示某项任务未开始或已完成。 (4) Gettop(s,e)-栈s的顶元素拷贝到e。 若s为空栈，则结束拷贝。 (5) Empty(s)-判断s是否为空栈。 若s为空栈,则Empty(s)为true；否则为false。2021/3/116(1)输入A,B,C,产生输出A,B,C的过程： A B,C(1)A进栈 B,C(2)A出栈 B C(3)B进栈 (4)B出栈 C (5)C进栈 (6)C出栈CA,B,CAA,B

4、A,BA2021/3/117(2)输入A,B,C,产生输出C,B,A的过程： A B,C(1)A进栈 B A C(2)B进栈 C B A (3)C进栈 B A(4)C出栈 C (5)B出栈 (6)A出栈C,B,ACC,B2021/3/118(3)输入A,B,C,产生输出B,C,A的过程: A B,C(1)A进栈 B A C(2)B进栈 A C(3)B出栈 C A(4)C进栈 A (5)C出栈 (6)A出栈B,C,ABB,CB2021/3/119 当A,B,C依次进栈，C出栈后，由于栈顶元素是B,栈底元素是A,而A不能先于B出栈,所以不能在输出序列中, 使A成为C的直接后继, 即不可能由输入A,

5、B,C产生输出C,A,B。 一般地，输入序列(.,ai,.,aj,.,ak,.)到栈中,不能得到输出序列(.,ak,.,ai,.,aj,.)。 (1)初始状态 C B A (2)A,B,C进栈 B A (3)C出栈CA,B,C(4)输入A,B,C,不能产生输出C,A,B:2021/3/1110设依次输入元素A,B,C到栈中,可得哪几种输出? 设依次输入元素C,B,A到栈中,可得哪几种输出? A,B,C(1) A,B,C(2) A,C,B(3) B,A,C(4) B,C,A(5) C,A,B(6) C,B,A C,B,A(1) A,B,C(2) A,C,B(3) B,A,C(4) B,C,A(5

6、) C,A,B(6) C,B,A2021/3/1111 讨论： 假定输入元素 A,B,C,D 到栈中,能得当哪几种输出? 不能得到哪几种输出序列？ (1) A,B,C,D (7) B,A,C,D (13) C,A,B,D (19) D,B,C,A (2) A,B,D,C (8) B,A,D,C (14) C,A,D,B (20) D,B,A,C (3) A,C,B,D (9) B,C,A,D (15) C,B,A,D (21) D,C,B,A (4) A,C,D,B (10) B,C,D,A (16) C,B,D,A (22) D,C,A,B (5) A,D,B,C (11) B,D,A,C

7、(17) C,D,A,B (23) D,A,B,C (6) A,D,C,B (12) B,D,C,A (18) C,D,B,A (24) D,A,C,B 共5+5+3+1=14种输出序列。 A,B,C,D输入输出5种5种3种1种2021/3/1112 顺序栈的基本操作及算法： 顺序栈的类型定义如下所示： #define SackSize100 typedef struct Datatype dataSackSize; int top; SeqStack 定义一个指向顺序栈的指针： SeqStack *s; 2021/3/11133.1.2 栈的存储表示和操作实现 1.顺序栈-用顺序空间表示的栈

8、。 假设栈空间为data0. SackSize-1 (1)顶指针指向顶元素所在位置： top 栈顶指针栈顶栈底SackSize-1 n 1 0/ SackSize-1 1 0 -1 自由区自由区(a) 非空栈 (b) 空栈, stop=-1若删除元素，将发生“下溢”/ an . a2 a1 序号 top 序号2021/3/1114top 栈顶栈底SackSize-1 1 0(c)满栈,stop= SackSize-1 若插入元素,将发生“上溢” “Overflow” an . . . a2 a1 2.操作实现2021/3/1115 (1)置空栈：首先建立栈空间，然后初始化栈顶指针。 SeqSt

9、ack *InitStack() SeqStack *s; s=malloc(sizeof(SeqStack); s-top= -1; return s; (2)判空栈 int StackEmpty (SeqStack *s) return S-top= =-1; (3)判满栈int StackFull(SeqStack *s) return s-top= =SackSize-12021/3/1116 (4) 入栈 void Push (SeqStack *s, datatype x) if (StackFull(s) Error(“Stack overflow”); /*栈满不能入栈*/ s

10、-top+; s-datas-top=x; (5) 出栈 DataType Pop(SeqStack *s, datatype *x) if (StackEmpty ( s ) ) Error(“Stack underflow”); /*栈空不能出栈 */ return s-datas-top-;/*返回,栈顶指针减1 */ 2021/3/1117 (6) 取栈顶元素取栈顶元素 datatype Top_SeqStack(SeqStack *s) if ( EmptyStack ( s ) ) Error(“Stack is empty”); /*栈空栈空*/ return (s-datas-

11、top ); 以下几点说明：以下几点说明： 1. 对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为：为：s-top= =StackSize-1，栈满时，不能入栈，栈满时，不能入栈; 否则出现空否则出现空间溢出，引起错误，这种现象称为上溢。间溢出，引起错误，这种现象称为上溢。 2. 出栈和读栈顶元素操作，先判断栈是否为空，为空时不出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。条件。 2021/3/11182.链式栈-使用不带表头结点

12、的单链表 (1)结点和指针的定义 struct node ElemType data； /data为抽象元素类型 struct node *next； /next为指针类型 *top=NULL； /初始化,置top为空栈 (2)非空链式栈的一般形式 ana(n-1) a1data nexttop 栈顶栈底2021/3/1119(3)链式栈的进栈算法：/压入元素e到top为顶指针的链式栈struct node *push_link(struct node *top,Elemtype e) struct node *p； int leng=sizeof(struct node)； /确定新结点空间

13、的大小 p=(struct node *)malloc(leng)；/生成新结点 p-data=e； /装入元素e p-next=top； /插入新结点 top=p； /top指向新结点 return top； /返回指针top an a1 栈底top epX an a1 栈底top e.栈顶栈顶(1)插入e之前：(2)插入e之后：2021/3/11203.1.3 栈的应用举例 栈的基本用途-保存暂时不用 的数据或存储地址。 数制转换问题例. 给定十进制数 N=1348,转换为八进 制数 R=25041.依次求余数,并送入栈中： (1) r1=1348%8=4 /求余 n1=1348/8=16

14、8 /整除 (2) r2=168%8=0 /求余 n2=168/8=21 /整除 (3) r3=21%8=5 /求余 n3=21/8=2 /整除 (4) r4=2%8=2 /求余 n4=2/8=0 /整除2.依次退栈,得R=2504 4 0 4 5 0 4 2 5 0 4(1) 4进栈 (2) 0进栈 (3) 5进栈 (4) 2进栈 2021/3/1121十进制数N转换为B进制数算法思想： N0 r=N%B r入栈 N=N/B 算法：typedef int DataType; void szzh( int N,int B ) int i; SeqStack s; InitStack(&s);

15、/初始化栈 while( N ) /N=0转换结束 push( &s,N%B ); /余数入栈 N=N/B; while( !StackEmpty( &s ) i=Pop( &s ); printf(“%d”,i) yn栈非空，出栈显示2021/3/11223.2 队列（排队,queue)3.2.1 队列及其操作 1.定义和术语 队列-只允许在表的一端删除元素,在另一端插入元素 的线性表。 空队列-不含元素的队列。 队首-队列中只允许删除元素的一端。head,front 队尾-队列中只允许插入元素的一端。rear,tail 队首元素-处于队首的元素。 队尾元素-处于队尾的元素。 进队-插入一个

16、元素到队列中。又称：入队。 出队-从队列删除一个元素。 2.元素的进出原则: “先进先出”，“First In First Out” 队列的别名: “先进先出”表，“FIFO” 表，排队,queue2021/3/1123 队列示意图 a1, a2 ,., an head(front) tail(rear) 队首 队尾 进队出队 3.队列的基本操作： (1)InitQueue(q)- 初始化,将q置为空队列。 (2)QueueEmpty(q)-判断q是否为空队列。 (3)EnQueue(q,e)- 将e插入队列q的尾端。 (4)DeQueue(q,e)- 取走队列q的首元素,送e。 (5)Qet

17、Head(q,e)- 读取队列q的首元素,送e 。 (6)QueueClear(q)-置q为空队列。2021/3/1124 A A B C D 0 1 2 3 4 50 1 2 3 4 50 1 2 3 4 5 A进队f r B,C,D进队frfr(3)B,C,D进队后:3.2.2 队列的顺序表示和实现(1)初始化后:(2)A进队后:假设用一维数组Q0.5表示顺序队列1.顺序队列与“假溢出 设f指向队头元素，r指向队尾元素空队列2021/3/1125 D E F 0 1 2 3 4 5 D 0 1 2 3 4 5fr E,F 进队fr G进队,“假溢出”解决假溢出的办法之一:移动元素。(6)D

18、,E,F移到前端后： D E F 0 1 2 3 4 5fr G 进队(4)A,B,C 出队之后：(5)E,F 依次进队之后：2021/3/1126 D E F G 0 1 2 3 4 5fr2.循环队列与解决假溢出的办法之二 (7)G进队之后：解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。将这种形式表示的队列称之为循环队列。（5）中用循环队列表示012345DEFG/rff=(f+1)%QueueSiz；r=(r+1)%QueueSize；QueueSize为数组单为数组单元数目元数目2021/3/1127234501FGDE/ H,I进队234501FGDEIHH,I进队之后f

19、rfr“满队列”:将Q0.5解释为循环队列的示意图：D,E,F,G,H,I出队，“空队列”fr012345当 f=r 时，怎样判断队列是空还是满？2021/3/1128当f=r，判断队空和满的方法： a. 设置一个布尔量以区别队空队满。 b. 少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，相等，队满。 c. 使用计数器记录队中元素的总数。 下面以第三种方法定义循环队的类型： #define QueueSize 100 typedef char DataType; /DataType类型依赖具体应用 typedef struct datatype dataQueue

20、Size; /*数据的存储区*/ int front, rear; int count; /*计数器，记录队中元素的个数*/ CirQueue; /*循环队*/ 循环队列的6种基本运算：/*队头队尾指针；非空时，队尾指针指向队尾元素下一个位 置*/2021/3/1129 (1) 置队空置队空 void InitQueue (CirQueue *Q) Q-front=Q-rear=0; Q-count=0; (2) 判队空判队空 int QueueEmpty (CirQueue *Q) return Q-count = =0; (3) 判队满判队满 int QueueFull(CirQueue

21、*Q) return Q-count = =QueueSize; (4) 入队入队 void EnQueue( CirQueue *Q, DataType x ) if( QueueFull(Q) ) Error( “Queue overflow”); /队满上溢队满上溢 Q-count +; Q-dataQ-rear=x; / 新元素新元素x入队尾入队尾 Q-rear=( Q-rear+1)% QueueSize; 2021/3/1130 (5) 出队出队 DataType DeQueue( CirQueue *Q ) DataType temp; if (QueueEmpty (Q) Er

22、ror( “Queue undeflow”); /队空下溢队空下溢 temp= Q-dataQ-front ; Q -count-; Q- front=( Q-front+1)% QueueSize; return temp; (6) 取队头元素取队头元素 DataType QueueFront( CirQueue *Q ) if (QueueEmpty (Q) Error( “Queue is empty”); return Q-dataQ-front; 2021/3/1131 3.2.3链式队列: 用不带表头结点的单链表表示队列 1.一般形式 (1)空队列: (2) 非空队列: 其中： Q

23、-front -队头(首)指针,指向队头结点。 Q-rear-队尾指针，指向队尾结点。a1data next a2队头结点an队尾结点.Q-frontQ-rear*QQ-frontQ-rear*Q2021/3/1132 2.2.定义结点类型定义结点类型 (1)(1)存放元素的结点类型存放元素的结点类型 typedef struct qtypedef struct queuenode node DataType data DataType data； /data/data为抽象元素类型为抽象元素类型 struct qstruct queuenode node * *nextnext； /next/next为指针类型为指针类型 QQueueNodeNode； /结点类型结点类型, , 指针类型指针类型 (2)(2)由头、尾指针组成的结点类型由头、尾指针组成的结点类型 typedef struct typedef struct Q QueueNode Node * *frontfront； /头指针头指针 Q QueueNode Node * *rearrear； /尾指针尾指针 LinkQueueLi