第03章 栈与队列

if(S->top==-1) /*栈为空*/
return(FALSE);
else
{*x = S->elem[S->top];
return(TRUE);
}
返回主目录}[注意]：在实现GetTop操作时，也可将参数说明SeqStack *S 改为SeqStack S，也就是将传地址改为传值方式。传 值比传地址容易理解，但传地址比传值更节省时间、 空间。
返回主目录
算法:
void BracketMatch(char *str) {Stack S; int i; char ch; InitStack(&S); For(i=0; str[i]!='\0'; i++) {switch(str[i])
{case '(': case '[': case '{':
3.1.3 栈的应用举例
1. 括号匹配问题
思想：在检验算法中设置一个栈，若读入的是左括号， 则直接入栈，等待相匹配的同类右括号；若读入的是 右括号，且与当前栈顶的左括号同类型，则二者匹配， 将栈顶的左括号出栈，否则属于不合法的情况。另外， 如果输入序列已读尽，而栈中仍有等待匹配的左括号， 或者读入了一个右括号，而栈中已无等待匹配的左括 号，均属不合法的情况。当输入序列和栈同时变为空 时，说明所有括号完全匹配。
return(TRUE);
}
返回主目录
【思考题】
如果将可利用的空闲结点空间组织成链栈来管理，则申 请一个新结点（类似C语言中的malloc函数）相当于链 栈的什么操作？归还一个无用结点（类似C语言中的 free函数）相当于链栈的什么操作？试分别写出从链栈 中申请一个新结点和归还一个空闲结点的算法。

第3章栈和队列
一、选择题
1.栈结构通常采用的两种存储结构是（A）。
A、顺序存储结构和链表存储结构B、散列和索引方式
C、链表存储结构和数组D、线性链表结构和非线性存储结构
2.设栈ST用顺序存储结构表示，则栈ST为空的条件是（B）
A、ST.top-ST.base<>0B、ST.top-ST.base==0
5.在对链队列（带素个数为rear-front。
7.一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。
8.一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。
9.若以链表作为栈的存储结构，则进栈需要判断栈是否满。
图3.1
21.链栈和顺序栈相比，有一个比较明显的优势是（）
A、通常不会出现栈满的情况B、通常不会出现栈空的情况
C、插入操作更容易实现D、删除操作更加容易实现
22.若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是（C）
A、不确定B、n-iC、n-i+1D、n-i-1
A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;
C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;
15.用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）
A、仅修改队头指针B、仅修改队尾指针
C、队头尾指针都要修改D、队头尾指针都可能要修改。
16.栈和队列的共同点是（）

制转移到调用函数。
多个函数嵌套调用的规则是：
后调用先返回 ！
此时的内存管理实行“栈式管理”
例如：
void main( ){ void a( ){
…
…
a( );
b( );
…
…
}//main
}// a
void b( ){
… 函数b的数据区 函数a的数据区 Main的数据区
}// b
递归函数执行的过程可视为同一 函数进行嵌套调用.
例七、实现递归
当在一个函数的运行期间调用另一个函 数时，在运行该被调用函数之前， 需先完成三项任务：
• 将所有的实在参数、返回地址等信息传 递给被调用函数保存；
• 为被调用函数的局部变量分配存储区； • 将控制转移到被调用函数的入口。
从被调用函数返回调用函数之前，应该 完成下列三项任务：
• 保存被调函数的计算结果； • 释放被调函数的数据区； • 依照被调函数保存的返回地址将控
从原表达式求得后缀式的规律为：
1) 设立操作数栈； 2) 设表达式的结束符为“#”，
预设运算符栈的栈底为“#”；
3) 若当前字符是操作数， 则直接发送给后缀式。
从原表达式求得后缀式的规律为：
4) 若当前运算符的优先数高于栈顶运算 符，则进栈；
5) 否则，退出栈顶运算符发送给后缀式；
6) “(” 对它之前后的运算符起隔离作 用，“)”可视为自相应左括弧开始的 表达式的结束符。
// 从终端接收下一个字符
}
将从栈底到栈顶的字符传送至调用过程的数据区；
ClearStack(S);
// 重置S为空栈
if (ch != EOF) ch = getchar();
}

栈与队列的区别
数据存储方式
栈是后进先出（Last In First Out, LIFO）的数据结构，新元素总是被添加到栈顶，移除 元素时也是从栈顶开始。而队列是先进先出（First In First Out, FIFO）的数据结构，新 元素被添加到队列的尾部，移除元素时从队列的头部开始。
操作方式
栈的主要操作有push（添加元素）和pop（移除元素），而队列的主要操作有enqueue （添加元素）和dequeue（移除元素）。
《栈和队列》ppt课件
目录
CONTENTS
• 栈的定义与特性 • 队列的定义与特性 • 栈与队列的区别与联系 • 栈和队列的实现方式 • 栈和队列的算法实现 • 总结与思考
01 栈的定义与特性
CHAPTER
栈的定义
栈是一种特殊的线性 数据结构，遵循后进 先出（LIFO）原则。
栈中的元素按照后进 先出的顺序排列，最 新加入的元素总是位 于栈顶。
02
如何实现一个队列，并 实现其基本操作（ enqueue、dequeue、 front）？
03
栈和队列在应用上有哪 些区别？请举例说明。
04
请设计一个算法，使用 栈实现括号匹配的功能 ，并给出测试用例。
谢谢
THANKS
。
队列的应用场景
任务调度
在任务调度中，可以将任 务按照优先级放入队列中 ，按照先进先出的原则进 行调度。
网络通信
在网络通信中，可以将数 据包放入队列中，按照先 进先出的原则进行发送和 接收。
事件处理
在事件处理中，可以将事 件放入队列中，按照先进 先出的原则进行处理。
03 栈与队列的区别与联系
CHAPTER
应用场景