第3章-栈和队列数据结构

3.1线性表的基本概念第3章栈和队列3.1.1栈的基本概念1．栈的定义栈(Stack)是限制在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端（表尾端）为栈顶(Top)，另一端（表头端）为栈底(Bottom)。当表中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。3.1线性表的基本概念第3章栈和队列2．栈的基本操作栈作为运算受限的线性表，其基本操作除了入栈、出栈外，还有建立堆栈（栈的初始化）、判断栈是否为空、判断栈是否满及获取栈顶元素等操作。（1）InitStack(S)初始化操作，其作用是将栈S置为空栈。（2）ClearStack(S)清栈操作，其作用是将已经存在的栈S置成空栈。（3）IsEmpty(S)判栈空操作，其作用是判断已存在的栈S，若S为空栈，则返回TRUE，否则返回FALSE。3.1线性表的基本概念第3章栈和队列（4）IsFull(S)判栈满操作，其作用是判断已存在的栈S是否已满，若S为满栈，则返回TRUE，否则返回FALSE。（5）Push(S,x)入栈操作，其作用是将元素x插入栈S中，使x成为栈S新的栈顶元素。（6）Pop(S,&x)出栈操作，其作用是当栈非空时，删除(亦称弹出)S的栈顶元素，并用x带回该值。（7）GetTop(S,&x)取栈顶元素操作，当栈非空时，取出S的栈顶元素，与Pop(S,&x)的不同之处在于GetTop(S,&x)不改变栈顶的位置。3.1线性表的基本概念第3章栈和队列3.1.2栈的存储结构和操作实现1．顺序栈栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组两端的任何一个端点；栈顶位置是随着入栈和出栈操作而变化的，故需用一个变量top来指示当前栈顶的位置，通常称top为栈顶指针。3.1线性表的基本概念第3章栈和队列顺序栈可以用C语言描述如下：#defineTRUE1#defineFALSE0#defineStack_Size50

/*Stack_Size为栈的最大容量*/typedefstruct{StackDataTypedata[Stack_Size];/*用来存放栈中数据元素的一维数组，

StackDataType为栈中元素的类型*/inttop;

/*栈顶指针，用来存放栈顶元素的下标*/}SeqStack;SeqStack*S;

/*定义一个指向顺序栈的指针变量*/3.1线性表的基本概念第3章栈和队列图3-2顺序栈的操作示意图3.1线性表的基本概念第3章栈和队列2．顺序栈的实现（1）初始化voidInitStack(SeqStack*S){/*构造一个空栈S*/S->top=-1;}（2）判别栈是否为空intIsEmpty(SeqStack*S)/*判栈S为空栈时返回值为真，反之为假*/{

if(S->top==-1)returnTRUE;elsereturnFALSE;}3.1线性表的基本概念第3章栈和队列（3）判别栈是否满intIsFull(SeqStack*S){if(S->top==Stack_Size-1)returnTRUE;elsereturnFALSE;}（4）入栈intPush(SeqStack*S,StackDataTypex){

if(S->top==Stack_Size-1)return(FALSE);/*栈已满*/S->top++;S->data[S->top]=x;return(TRUE);}3.1线性表的基本概念第3章栈和队列（5）出栈intPop(SeqStack*S,StackDataType*x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中*/if(S->top==-1)/*栈为空*/return(FALSE);else{

*x=S->data[S->top];S->top--;

/*修改栈顶指针*/

return(TRUE);}}3.1线性表的基本概念第3章栈和队列（6）取栈顶元素intGetTop（SeqStack*S,StackDataType*x）{/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶位置保持不变*/if(S->top==-1)/*栈为空*/return(FALSE);else{

*x=S->data[S->top];

return(TRUE);}}3.1线性表的基本概念第3章栈和队列3．两栈共享空间栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是多栈的共享技术。在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。3.1线性表的基本概念第3章栈和队列两栈共享的数据结构定义如下：#defineM100typedefstruct{StackDataTypeStack[M];

inttop[2];/*top[0]和top[1]分别为两个栈顶指示器*/}DqStack;3.1线性表的基本概念第3章栈和队列4.链栈栈的链式存储结构简称为链栈，它是运算受限的单链表。由于只能在链表头部进行操作，故链栈没有必要像单链表那样附加头结点。链表的表头指针就作为栈顶指针，如图所示。链栈的示意图3.1线性表的基本概念第3章栈和队列链栈可用C语言描述如下：typedefstructnode{StackDataTypedata;

/*数据域*/

structnode*link;

/*指针域，用于存放下一结点的地址*/}LinkStackNode，*LinkStack;LinkStacktop；/*栈顶指针*/3.1线性表的基本概念第3章栈和队列⑴入栈操作intPush(LinkStacktop,StackDataTypex)/*将数据元素x压入栈top中*/{LinkStackNode*s;s=(LinkStackNode*)malloc(sizeof(LinkStackNode));

if(s==NULL)return(FALSE);/*申请空间失败*/

s->data=x;

s->link=top;top=s;/*修改当前栈顶指针*/return(TRUE);}3.1线性表的基本概念第3章栈和队列⑵出栈操作intPop(LinkStacktop,StackDataType*x){/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/LinkStackNode*s;s=top;if(s==NULL)/*栈为空*/return(FALSE);top=s->link;*x=s->data;free(s);

/*释放存储空间*/return(TRUE);}3.1线性表的基本概念第3章栈和队列3.1.3栈的应用实例——表达式求值表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。在本节中，首先讨论算术表达式的两种表示方法，即中缀表示法和后缀表示法，接着讨论后缀表达式求值的算法，最后讨论中缀表达式求值的算法。1. 算术表达式的两种表示通常书写的算术表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。操作数可以是常量、变量和函数，同时还可以是表达式。运算符包括单目运算符和双目运算符两类，单目运算符只要求一个操作数，并被放在该操作数的前面，双目运算符要求有两个操作数，并被放在这两个操作数的中间。单目运算符为取正“+”和取负“-”，双目运算符有加“+”,减“-”,乘“*”和除“/”等。为了简便起见，在我们的讨论中只考虑双目运算符。3.1线性表的基本概念第3章栈和队列2.

后缀表达式的求值算法后缀表达式的求值比较简单，扫描一遍即可完成。它需要使用一个栈，假定用st表示，其元素类型应为操作数的类型，假定为浮点型float，用此栈存储后缀表达式中的操作数、计算过程中的中间结果以及最后结果，同时假定后缀算术表达式以一个字符串的方式提供。后缀表达式求值算法的基本思路是：把包含后缀算术表达式的字符串定义为一个输入字符串流对象，每次从中读入一个字符（每个运算对象——数据输入结束后输入空格作为分隔符）时，若它是运算符，则表明它的两个操作数已经在栈st中，其中栈顶元素为运算符的后一个操作数，栈顶元素的下一个元素为运算符的前一个操作数，把它们弹出后进行相应运算即可，然后把运算结果再压入栈st中；否则，读入的字符必为操作数的最高位数字，应把它重新送回输入流中，然后把下一个数据作为浮点数输入，并把它压入到栈st中。依次扫描每一个字符（对于浮点数只需扫描它的最高位并一次输入整个浮点数）并进行上述处理，直到整个输入字符串流结束为止，表明后缀表达式计算完毕，最终结果保存在栈中，并且栈中仅存在这一个值，把它弹出返回即可。3.1线性表的基本概念第3章栈和队列3.

中缀表达式的求值算法如前所述，中缀表达式的求值比较复杂，为了实现中缀表达式的求值，需要使用两个工作栈。一个称做运算符栈ct，用以寄存运算符；另一个称做操作数栈st，用以寄存操作数和计算过程中的中间结果以及最后结果，和后缀表达式相同，假定中缀算术表达式也以一个字符串的方式提供，同时，为了简化求值过程，假设表达式开始和结束运算符为‘#’，且‘#’的运算优先级最低。3.1线性表的基本概念第3章栈和队列中缀表达式求值算法的基本思路是：（1）置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入中缀表达式字符串流，每次从中读入一个字符时，若它是运算符，则和ct栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即ct栈顶元素和当前读入的字符均为“#”）；否则，读入的字符必为操作数的最高位数字，应把它重新送回输入流中，然后把下一个数据作为浮点数输入，并把它压入到栈OPND中。依次扫描每一个字符并进行上述处理，直到整个输入字符串流结束为止，表明中缀表达式计算完毕，最终结果保存在st栈中，并且st栈中仅存在这一个值，把它弹出返回即可。3.2队列第3章栈和队列日常生活中，经常遇到排队办事的问题，如：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊，先到的人排在前面，后来的人则排在队尾等候；又如：乘坐公共汽车，应该在车站排队，先到的人排在前面，后来的人则排在后面，然后按顺序上车；此外，队列在程序设计中也经常出现，一个最典型的例子就是操作系统中的作业排队，在允许多道程序运行的计算机系统中，同时有几个作业运行，如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队等等。3.2队列第3章栈和队列3.2.1队列的基本概念1. 队列的定义队列(Queue)是另一种运算受限的线性表，它只允许在表的一端插入元素，而在另一端删除元素。通常称插入的一端为队尾(rear)，删除的一端为队头(front)。若队列中没有元素，则称为空队列。队列的插入操作被形象地称为入队，删除操作称为出队。假设队列为Q=(a1，a2，…，an)，如图3-5所示，a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列，即先进入队列的成员总是先离开队列。因此队列亦称作先进先出的线性表，简称FIFO(FirstInFirstOut)表。队列示意图3.2队列第3章栈和队列2. 队列的基本操作队列作为运算受限的线性表，其基本操作除了入队列、出队列外，还有建立队列（队列的初始化）、判断队列是否为空、及获取队头元素等操作。（1）InitQueue(Q)初始化操作，其作用是将队列Q置为空队列。（2）IsEmpty(Q)判队列是否为空操作，其作用是判断已存在的队列Q，若Q为空队列，则返回TRUE，否则返回FALSE。（3）EnterQueue(Q，x)入队操作，其作用是将元素x插入Q的队尾，使x成为Q新的队尾元素。（4）DeleteQueue(Q,&x)出队操作,其作用是当Q非空时，删除Q的队头元素，并用x带回该值。（5）GetHead（Q,&x）取队头元素操作，当队列非空时，取出Q的队头元素，与DeleteQueue(Q,&x)不同之处在于GetHead（Q,&x）不改变队头位置。（6）ClearQueue(Q)队列置空操作，将队列Q置为空队列。（7）DestroyQueue(&Q)销毁队列操作，释放队列的空间。3.2队列第3章栈和队列3.2.2队列的存储结构和操作实现1．队列的顺序存储结构队列的顺序存储结构简称为顺序队列，它也是运算受限的顺序表，即顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front和rear，分别指示队头元素和队尾元素在数组中的位置。3.2队列第3章栈和队列顺序队列可以用C语言描述如下：#defineMaxSize100/*队列的最大容量*/typedefstruct{

QueueDataTypedata[MaxSize];/*用来存放队列中数据元素的一维数组，

QueueDataType为队列中元素的类型*/intfront;/*队头指示器*/intrear;/*队尾指示器*/}SeqQueue;SeqQueue*Q；/*定义一个指向顺序队列的指针变量*3.2队列第3章栈和队列顺序队列示意图空队列示意图3.2队列第3章栈和队列3.2队列第3章栈和队列2．循环队列的实现（1）初始化操作voidInitQueue（SeqQueue*Q）{/*将*Q初始化为一个空的循环队列*/Q->front=Q->rear=0;}3.2队列第3章栈和队列（2）入队操作intEnterQueue(SeqQueue*Q,QueueDataTypex){/*将元素x入队*/if((Q->rear+1)%MaxSize==Q->front)/*队列已满*/

return(FALSE);Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MaxSize;/*重新设置队尾指针*/return(TRUE);/*操作成功*/}3.2队列第3章栈和队列（3）出队操作intDeleteQueue(SeqQueue*Q,QueueDataType*x){/*删除队列的队头元素，用x返回其值*/if（Q->front==Q->rear）

/*队列为空*/

return(FALSE);*x=Q->data[Q->front];Q->front=(Q->front+1)%MaxSize;/*重新设置队头指针*/return(TRUE);

/*操作成功*/}3.2队列第3章栈和队列3.链队列队列的链式存储结构简称为链队列，它是运算受限的单链表。为了操作方便，我们采用带头结点的链表结构，并设置一个队头指针和一个队尾指针，如图3-10所示。队头指针始终指向头结点，队尾指针指向当前最后一个元素。空的链队列的队头指针和队尾指针均指向头结点。带头结点的链队列3.2队列第3章栈和队列4.链队列的基本操作（1）初始化操作intInitQueue(LinkQueue*Q){/*将Q初始化为一个空的链队列*/Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));/*申请头结点*/if(Q->front!=NULL){Q->rear=Q->front;Q->front->link=NULL;

return(TRUE);}/*将Q初始化为带头结点的链队列*/elsereturn(FALSE);}3.2队列第3章栈和队列（2）入队操作3.2队列第3章栈和队列intEnterQueue(LinkQueue*Q,QueueDataTypex){/*将数据元素x插入到队列Q中*/LinkQueueNode*New;New=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(New!=NULL){New->data=x;

New->link=NULL;

Q->rear->link=New;Q->rear=New;return(TRUE);}elsereturn(FALSE);}3.2队列第3章栈和队列（3）出队操作3.2队列第3章栈和队列intDeleteQueue(LinkQueue*Q,QueueDataType*x){/*将队列Q的队头元素出队，并存放到x所指的存储空间中*/LinkQueueNode*p;if(Q->front==Q->rear)

return(FALSE);p=Q->