第三章栈和队列整理软件08505班

第三章 栈和队列 掌握程度 1、考点: 栈和队列的定义特点,循环队(队空队满)条件,根据栈队定义判断插入删除元素的位置,以及出入栈出入队的顺序(选择填空概率较大).有可能和第二章链表部分出算法题.(如链栈链队等) 2、重点掌握在顺序栈和链栈上实现的栈的基本运算，特别注意栈满和栈空的条件及它们的描述。 3、重点掌握在循环队列和链队列上实现的基本运算，特别注意队满和队空的描述方法。 一.栈和队列的比较.

栈 队列 定义 栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 特点 后进先出(LIFO)或先进后出（FILO） 先进先出(FIFO)或后进后出(LILO) 应用 进制转换,表达式求值,递归乘方. 迷宫最短路径,待打印文档,系统进程. 二.需要掌握操作 顺序栈,链栈,循环队列, 顺序栈  初始化（栈置空）操作  判栈空函数  进栈操作  出栈函数  读栈顶元函数 void Init_SeqStack(SeqStack *s) { s->top= 0; }//初始化（栈置空）操作 int Empty_SeqStack(SeqStack *s) { if (s->top== 0) return 1; else return 0; }//判栈空函数 int Push_SeqStack (SeqStack *s, int x) /* 入栈*/ { if (s->top==MAXSIZE) return 0; /*栈满不能入栈*/ else { s->data[s->top]=x; s->top++; /*栈顶上移*/ return 1; } }//进栈操作 int Pop_SeqStack(SeqStack *s, int *x) { if (s->top== 0) return 0; /*栈空不能出栈 */ else { s->top--; *x=s->data[s->top]; return 1; }/*栈顶元素存入*x，返回*/ }//出栈函数 int Top_SeqStack(SeqStack *s) { if (s->top== 0) return 0; /*栈空*/ else return (s->data[s->top-1] ); }//读栈顶元函数 链栈  初始化操作  进栈操作  出栈操作

void Init_LinkStack（StackNode * top） { top=NULL; }//初始化操作 StackNode * Push_LinkStack（StackNode * top, int x） { StackNode *s; s=(StackNode * )malloc（sizeof（StackNode））; s->data=x; s->next=top; top=s; return top; }//进栈操作 StackNode * Pop_LinkStack (StackNode * top, int *x) { StackNode *p; if （top= =NULL） return NULL; else { *x = top->data; p = top; top = top->next; free (p); return top; } }//出栈操作 循环队列  初始化操作的实现  判队空函数  判队满  入队列操作  出队列操作

void Init_SeQueue(c_SeQueue *q) { q->front=q->rear=0; }//初始化操作的实现 int Empty_SeQueue(c_SeQueue *q) { if (q->rear == q->front) return 1; else return 0; }//判队空函数 int Full_SeQueue(c_SeQueue *q) /*判队满*/ { if ((q->rear+1) % MAXSIZE== q->front) return 1; else return 0; }//判队满 int In_SeQueue(c_SeQueue *q ,int x) /*入队列*/ { if ( (q->rear+1) % MAXSIZE== q->front) { printf("队满"); return -1; /*队满不能入队*/ } else { q->rear=(q->rear+1) % MAXSIZE; q->data[q->rear]=x; return 1; /*入队完成*/ } }//入队列操作 int Out_SeQueue(c_SeQueue *q ,int *x) /*出队列*/ { if(q->rear == q->front) { printf("队空"); return -1; /*队空不能出队*/ } else { q->front=(q->front+1)%MAXSIZE; *x=q->data[q->front]; /*读出队头元素*/ return 1; /*出队完成*/ } }//出队列操作 三.习题答案 书P131----四.简答题 1. 什么是栈?什么是队列?试分别举两个应用实例. 答：栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表. 栈: 进制转换,表达式求值,递归乘方. 队列: 迷宫最短路径,待打印文档,系统进程. 2. 说明线性表,栈和队列的异同点. 答：相同点： 逻辑结构相同，都是线性的；都可以用顺序存储或链表存储； 栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同： 线性表为随机存取； 而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO； 队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同： 线性表比较通用； 堆栈用于函数调用、递归和简化设计等； 队列用于离散事件模拟、操作系统作业调度和简化设计等。 3. 设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序. 答：有14种。 ①全进之后再出情况，只有1种：4，3，2，1 ② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 ③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

根据卡特兰数特点本题符合及可用公式算出一共有C2nn/(n+1)=

C84/(4+1)=14(种)

结点进栈与出栈问题实质是一个中序遍历二叉树的过程。求N个结点的不同形态的二叉树数目,其个数即为上卡特兰数结果. 4. 假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？ 答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出； 堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。 哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是„„） 若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。 5. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？ 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三： ① 设置一个布尔变量以区别队满还是队空； ② 浪费一个元素的空间，用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数（即队列长度）。 我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N 6. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 答：用队列长度计算公式： (N＋r－f)% N ① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32 7. 试述栈的基本性质. 答：栈(Stack) 是限制仅在表的一端进行插入和删除操作的线性表。后进先出(LIFO)或先进后出（FILO） 8. 设输入元素为1,2,3,P和A,输入次序为123PA,元素设输入元素为1、2、3、P和A，输入次序为123PA。元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。 答:一般说，高级语言的变量名是以字母开头的字母数字序列。AP321,PA321,P3A21,P32A1,P321A。 9. 内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 答: S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。 10. 计算表达式”6*3/2-5*1”,要求绘出堆栈的处理过程. 答: 操作数栈 运算符栈 第一次 6 空 第二次 6 * 第三次 3 空 6 * 18 空