栈与队列(没有用指针)

1、第三章 栈和队列3.1 栈3.2 栈的应用举例3.3 队列1 3.1.1 栈的定义 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom).当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。3.1 栈栈：限定只能在表的一端进行插入和删除的特殊的线性表. 设栈s=（a1，a2，. . . ,ai，. . . ，an），

2、其中a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端； 栈顶的当前位置由栈顶指针的位置指示器指示。栈底（bottom):不允许插入和删除的一端。进栈或入栈：栈的插入操作。出栈或退栈：栈的删除操作。 a1 a2 . an进栈出栈栈顶栈底3.1.1 栈的定义空栈：没有元素的栈栈的特性：先进后出（LIFO），即只能在末端（栈顶）进行插、删的操作3.1.1 栈的定义例：一叠书或一叠盘子。 栈顶 栈底3.1.1 栈的定义栈中的几种基本操作： 1.插入一个新的栈顶元素（进栈）:push(S,x); 2.删除栈顶元素（出栈）: pop(S); 3.读取栈顶元素:getTop(S); 4

3、.判空栈:stackEmpty(S); 3.1.1 栈的定义栈的存储结构顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，一般用一维数组表示必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置链栈采用链表作为存储结构实现的必须设置一个栈顶指针永远指向栈顶3.1.2 栈的表示和实现一、顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的。3.1.2 栈的表

4、示和实现 需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。一、顺序栈顺序栈的结构int stack105;stack0 = a1;stack1 = a2;top = 2stacktop+ = a3; 一、顺序栈a2a1top-一、顺序栈对应的出栈操作为：top- 进栈操作为：top+ 得到栈顶元素为：atop判断栈为空的操作为：if(top = 0)进栈算法int Push(int stack, int x) if(top maxsize ) return 0; stacktop+ = x; retur

5、n 1; a2 a3 a4987654321 a10top一、顺序栈栈的判空操作int stackempty() if ( top = 0) return 1; else return 0;出栈算法： a2 a3 a4987654321 a10top一、顺序栈int pop (int stack) top - ; return stacktop;二、链栈 栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 3.1.2 栈的表示和实现 antop栈底 用指针来实现的栈叫

6、链栈。栈的容量事先不能估计时采用这种存储结构。链栈的类型说明如下：typedef struct Lnode int data； struct Lnode next； node;node LinkStack；top头指针永远指向头结点二、链栈进栈算法二、链栈void push(node LinkStack,int x) node *temp; temp = (node*)malloc(sizeof(node); temp-data = x; temp-next = LinkStack-next; LinkStack-next = temp出栈算法二、链栈void pop(node LinkSta

7、ck,int &x) node *temp; temp = LinkStack-next; LinkStack-next = LinkStack-next-next; x = temp-data; free(temp); 1 数制的转换 sdut 21312 括号匹配的检验 sdut 21343 表达式求值 sdut 2132 2133hdu 1022水题大战的题目。（模拟栈的过程）3.2 栈的应用 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作

8、业排队。 先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。3.3.1 队列的定义下图是队列的示意图：出队入队队头队尾 a1a2an3.3.1 队列的定义队尾：在队列中，允许插入的一端队头：在队列中，允许删除的一端队列的主要运算设置一个空队列；插入一个新的队尾元素，称为进队；删除队头元素，称为出队；读取队头元素；等3.3.1 队列的

9、定义队列的存储结构（1）顺序存储结构(a) 线性队列 (b) 循环队列（2）链式存储结构3.3.2 队列的表示和实现队列的类型定义：#define MAXSIZE 50typedef struct int elem MAXSIZE; int front;int rear;SeqQueue;e1,e2出队，e4入队队满 e1 e2 e3 (b)rearfronte1,e2,e3入队 队空时， 令rear=front=0，当有新元素入队时，尾指针加1，当有元素出队时，头指针加1。故在非空队列中，头指针始终指向队头元素的位置，而尾指针始终指向队尾元素后一个位置rear=front=0(队空)fron

10、t 3 2 1 0 (a)rearrear=4 (c) e3 e4front队列的顺序存储 和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”（假溢出）现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。队列的顺序存储 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队

11、操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： if(i+1=QueueSize) i=0; else i+;利用模运算可简化为： i=(i+1)%QueueSize队列的顺序存储 显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。 如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“

12、空”还是“满”。 解决此问题的方法至少有三种： 其一是另设一个布尔变量以区别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；队列的顺序存储 其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。 #define QueueSize 100 typedef struct Queuedatatype dataqueuesize int front， rear; int len; sqqueue;队列的顺序存储（

13、1）置空队 void initqueue(sqqueue *q) qfront=qrear=-1; qlen=0; （2）判断队空 int queueempty(sqqueue *q) return qlen=0; （3）判断队满 int queuefull(sqqueue *q) return qlen=queuesize; 队列的顺序存储（4）入队 void inqueue(sqqueue *q,datatype x) if(queuefull(q) printf(“queue overflow”); return; qlen+; qdataqrear=x; qrear=(qrear+1)

14、%queuesize; 队列的顺序存储（5）出队 queuedatatype dequeue(sqqueue *q) datatype temp; if(queueempty(q) printf(“queue underflow”); return; temp=qdataqfront; qlen-; qfront=(qfront+1)%queuesize; return temp; 队列的顺序存储（6）取头元素 queuedatatype queuefront(sqqueue *q) if(queueempty(q) printf(“queue is empty.”); return(0);

15、return qdataqfront; 队列的顺序存储区分队列空与满另一种方法 少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满（注意：rear所指的单元始终为空）；队列的顺序存储循环队列 rear front 0 1 2 3(3) 队空队满条件：(Q.rear+1)%MAX=Q.front注：实际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。(1)一般情况 rear front 0 1 2 3e4e3 (2) 队满 front e3 e4 0 1 2 3 reare5队列的顺序存储#define MAXSIZE 50t

16、ypedef structQueueElementType elementMAXSIZE; int front;int rear;SeqQueue;注意事项：1、出队时，头指针的变化为front=(front+1) mod MAXSIZE2、入队时，尾指针的变化为rear=(rear+1) mod MAXSIZE3、凡是遇到指针要发生变化，头和尾指针的有效范围为0,MAXSIZE-1，所以用取模运算来保证头尾指针的取值循环队列的类型定义循环队列中加入一个元素的算法： int EnQueue(SeqQueue *Q,int x) Q为已有的循环队列将插入的值循环队列循环队列中加入一个元素的算法：

17、 int EnQueue(SeqQueue *Q,int x) if(Q-rear+1)%MAXSIZE= =Q-front) return(0); else Q-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3rearX循环队列循环队列中删除一个元素的算法：int DeQueue(SeqQueue *Q，int *py) 已有的循环队列返回删除的值的地址循环队列循环队列中删除一个元素的算法：int DeQueue(SeqQueue *Q，int *py) if(Q-rear= =Q-front) retu

18、rn(0); else*py=QQ-front; Q-front=(Q-front+1)%MAXSIZE; return(1); rear front 0 1 2 3e4e3front循环队列链式存储结构 an a2 a1Q.frontQ.rear队头队尾typedef struct NodeQueueElementType data; struct Node *next;LinkQueueNode;/*结点的定义*/typedef structLinkQueueNode *front; LinkQueueNode *rear;LinkQueue;/*队列的定义*/注意：队头永远指向头结点，队尾永远指向最后一个