第三章栈与队列

栈和队列的基本操作是线性表操作的子集，是限定性（操作受限制）的数据结构。

第三章栈和队列数据结构之栈和队列23. 1 栈¾定义：是限定仅在表尾进行插入或删除操作的线性表。

(后进先出线性表LIFO)¾栈底指针(base) :是线性表的基址；¾栈顶指针(top):指向线性表最后一个元素的后面。

¾当top=base 时，为空栈。

¾基本操作：InitStack(&S), DestroyStack(&S),StackEmpty(S) , ClearStack(&S),GetTop(S ,&e), StackLength(S) ,Push(&S, e): 完成在表尾插入一个元素e.Pop(&S,&e): 完成在表尾删除一个元素。

数据结构之栈和队列3¾栈的表示和实现¾顺序栈：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素；栈满之后，可再追加栈空间即为动态栈。

¾顺序栈的结构类型定义：typedef int SElemType;typedef struct{SElemType *base; /* 栈底指针*/SElemType *top; /* 栈顶指针*/int stacksize; /* 栈空间大小*/ }SqStack;数据结构之栈和队列4¾基本算法描述¾建立能存放50个栈元素的空栈#define STACK_INIT_SIZE 50#define STACKINCREMENT 10Status InitStack_Sq(Stack &S){S.base=(SET*)malloc(STACK_INIT_SIZE *sizeof(SET)); /*为栈分配空间*/if(S.base==NULL)exit(OVERFLOW); /*存储分配失败*/ S.top=S.base;S.stacksize = STACK_INIT_SIZE;return OK; }数据结构之栈和队列5¾出栈操作算法void pop(Sqstack s,SElemType e){if(s.top= = s.base)return ERROR;else{s.top--;e= *s.top;}return OK;}出栈操作topABY topABYbase base数据结构之栈和队列6¾压栈操作算法void Push(SqStack s,SElemType e)if(s.top-s.base>= S.stacksize;) {S.base=(SET*)realloc(S,base,(S.stacksize+STACKINCREMEN T) *sizeof(SET)); /*为栈重新分配空间*/if(！S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;}return OK; }topAB压栈操作topABebase base数据结构之栈和队列7¾栈的销毁void DestroyStack_Sq(Stack &S){ if (S.base) free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;}¾栈的清除void ClearStack_Sq(Stack &S){ S.top = S.base ;}数据结构之栈和队列8¾判断栈是否为空栈Status StackEmpty_Sq(Stack S){ if(S.top==S.base) return TRUE;else return FALSE;}¾获得栈的实际长度int StackLength_Sq(Stack S){return(abs(S.top-S.base));}数据结构之栈和队列9¾多个栈共享邻接空间两个栈共享一空间::::::top1top21m中间可用空间栈1栈2地址Base1Base 2……数据结构之栈和队列103. 3 栈与递归¾递归函数：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数。

第3章数据结构栈和队列数据结构是计算机科学中重要的基础知识之一，它是用于组织和管理数据的方法。

栈和队列是其中两种常见的数据结构，它们分别以后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的方式操作数据。

本文将详细介绍栈和队列的概念、特点以及应用。

一、栈栈是一种限制仅在表尾进行插入和删除操作的线性表。

插入和删除操作称为入栈和出栈，即数据项的入栈相当于把数据项放入栈顶，而数据项的出栈相当于从栈顶移除数据项。

栈具有后进先出的特点，即后入栈的数据项先出栈，而最先入栈的数据项最后出栈。

类比现实生活中的例子就是一叠盘子，我们只能从最上面取盘子或放盘子。

栈的实现方式有两种：基于数组和基于链表。

基于数组的栈实现相对简单，通过一个数组和一个指向栈顶的指针来完成栈的操作。

基于链表的栈实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针来操作栈。

栈的应用非常广泛，比如浏览器中的返回功能就是通过栈来实现的。

当我们点击浏览器的返回按钮时，当前页面会入栈，点击前进按钮时，当前页面会出栈。

在编程中，栈也被广泛应用，比如函数调用栈用于存储函数调用的上下文信息。

二、队列队列是一种限制仅在表头删除和在表尾插入的线性表。

表头删除操作称为出队列，表尾插入操作称为入队列。

和栈不同，队列采用先进先出的原则，即最先入队列的元素最先出队列。

队列的实现方式也有两种：基于数组和基于链表。

基于数组的队列实现和栈类似，通过一个数组和两个指针（一个指向队头，一个指向队尾）来完成队列的操作。

基于链表的队列实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针和尾指针来操作队列。

队列同样具有广泛的应用，比如操作系统中的进程调度就是通过队列来实现的。

CPU会按照进程到达的顺序，依次从队列中取出进程进行执行。

在编程中，队列也常用于解决一些需要按顺序处理数据的问题。

第3章桟和队列3.1 选择题1．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是（）A）不确定 B）n-i+1 C）i D）n-i【答案】B【解析】根据栈的性质（LIFO），若输出的第一个元素是n，则表明所有的元素已经入栈，则出栈顺序为n，n-1，…，3，2，1。

2．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是（）A）6 B）4 C）3 D）2【答案】C【解析】根据栈的性质（LIFO）得，e2出栈前，栈中存有e1和e2两个元素，e4出栈前，栈中存有e1、e3和e4三个元素，e4和e3出栈以后，e5和e6入栈，栈中同样存在e1、e5和e6三个元素，然后三个元素依次出栈，所以栈的容量至少应该为3。

3．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）A）top=top+1; V[top]=x B）V[top]=x; top=top+1C）top=top-1; V[top]=x D）V[top]=x; top=top-1【答案】C【解析】栈式运算受限的线性表，只允许在栈顶进行插入和删除操作。

本题中栈顶指针为n+1，该数组将栈顶放在了下标大的一端，所以在进行入栈操作时top指针应该进行减一操作。

通常元素进栈的操作为：先移动栈顶指针后存入元素。

4．如果我们用数组A[1..100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。

请问在top为100时，再进行入栈操作，会产生（）A）正常动作 B）溢出 C）下溢 D）同步【答案】B【解析】当top为100时，表示栈已经满了，此时再进行入栈操作，则会造成溢出。

5．栈在（）中应用。

A）递归调用 B）子程序调用 C）表达式求值 D）A，Ｂ，Ｃ【答案】D7．用链接方式存储的队列，在进行删除运算时（）A）仅修改头指针 B）仅修改尾指针C）头、尾指针都要修改 D）头、尾指针可能都要修改【答案】D【解析】若队列中的元素多于一个，删除队列中的队尾元素，只需修改队尾指针；若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。