赞
踩
、
•栈:受限制的线性表,只允许从表的一端操作。这端称为栈顶,另一端为栈底
•压入元素(push):往栈顶新增一个元素,新元素成为新栈顶。
•弹出元素(pop):移除栈顶元素,原栈顶的元素成为新栈顶/或栈变成空栈
•图片表示进出栈结果:
*key1:栈是一种先进后出的数据结构,pop和push操作仅在栈顶进行
•队列:受限制的线性表,只允许从表的两端操作,一端是队首,一端是队尾。
•入队(enqueue):往队尾新增一个元素,新元素成为新队尾
•出队(dequeue):移出队首元素,下一个元素成为新队首/或队列变为空
•图文演示过程:
•栈后进先出的特点天然地和程序中函数调用关系相吻合
•程序执行时,在函数A中执行到调用另一个函数B的语句时,会发生什么?
立刻进入被调函数B执行其代码,完成后返回到A的下一行继续执行A的剩余代码
•因此在操作系统执行代码时,函数间的调用-返回关系正是通过调用栈来维护
•函数的递归调用本质也是一个栈型调用,因此可以利用栈将一个递归函数改写为完全等价的非递归函数,避免了操作系统层面的调用栈开销。
、
栈的应用:括号匹配
•目的:判断一个字符串你中括号是否——匹配
•
•为什么可以用栈来解决这个问题?
•当遇到左括号时,我希望能立刻遇到它的另一半,但如果接着又遇到了一个左括号,那它的需求比我更紧迫,我需要先处理后来的这个左括号
•后来的需要先满足->后进先出问题->用栈解决
•表达式求值,如1+2*3
•进制转换
•非递归的深度优先遍历(DFS)
•你会怎样实现一个顺序序列?
•'假溢出'现象:底层顺序表前部的可用空间无法再利用上了
•解决方法:循环队列
顺序栈实现
•顺序栈的底层是一个数组,低地址为栈底,高地址为栈顶,只能在栈顶操作
- /*(顺序)栈*/
- //栈数据结构定义
- #define MAX_SIZE 10
- typedef struct{
- Student *data;
- int size;
- }Stack;
- //往栈顶压入一个元素
- bool Push(Stack &stk,const Student &s){
- if (stk.size==MAX_SIZE){
- return false;
- }
- int newTop=stk.size;
- stk.data[newTop]=s;
- stk.size++;
- return true;
- }
- //弹出栈顶元素
- bool Pop(Stack &stk){
- if(stk.size==0){
- return false;}
- stk.size--;
- return true;
- }
*key1:顺序栈的底层是一个数组空间,并通过维护当前栈大小实现栈
*key2:顺序栈的当前栈顶元素下标和栈大小是top=size-1的关系
1.设Stack是顺序栈的一种实现,在(a)处应填入的代码为:___________.(stk.size--)
struct Stack{
Elem data[MAX_SIZE];
int size=0;
};
bool Pop(Stack &s){
if (stk.size==0)return false;
___(a)____;
return true;
}
循环队列实现
•循环队列的底层是一个数组,通过维护队头和队尾在此数组中的下标来实现
- /*循环队列*/
- //循环队列数据结构
- #define M 10
- typedef struct{
- Student data[M];
- int front;
- int back;//bcak表示队尾的下一个空位
- }CQueue;//c=Circulative
- //求循环队列元素个数
- int GetSize(CQueue &queue){
- int size=(queue.back-queue.front+M)%M;
- return size;
- }
*key1:循环队列的容量是MAX_SIZE-1
*key2:循环队列当前元素数量计算
1.假设一循环队列的底层数组为array[M],我们约定f表示为当前队首元素,b为当前队尾元素的后
一个元素,则当前队列内元素个数为()
A.b-f B.(b-f+M)%M
C.b-f+M D.(f-b+M)%M
分析:做循环队列题一定要把底层数组画出来模拟!
第一种情况:
第二种情况:
M=8,蓝色表示队列元素。
分析:对于第一种情况直接=b-f,第二种情况等于b-f+M
统一一下答案:由于b-f>0,所以加上M再对M取余正好消去M。第二个由于b-f<0,b-f+M<M
所以对M取余不起作用。总结答案选择为B选项
循环队列实现
•循环队列的底层是一个数组,通过维护队头和队尾在此数组中的下标来实现
- //循环队列入列
- bool Enqueue_CQ(CQueue &queue,const Student &s){
- int newBack=(queue.back+1)%M;
- if(newBack==queue.front){
- return false;//头尾相接表示队列满了}
- queue.data[queue.back]=s;//放入队尾
- queue.back=newBack;
- return true;
- }
- //循环队列出列
- bool Dequeue_CQ(CQueue &queue){
- if (queue.front==queue.back){
- return false;//头尾重合表示队列为空
- } queue.front=(queue.front+1)%M;
- return true;
-
- }
*key3:循环队列判满条件为(back+1)%MAX_SIZE==front ''首尾相接''
*key4:循环队列判空条件为back==front ''首尾重合''
1.(a)处应填入的代码为:______________.(queue.front ==queue.back)
bool Dequeue_CQ(CQueue &queue){
if (___(a)____){
return false;//头尾重合表示队列为空
}queue.front=(queue.front +1)%queue.capacity;
return true;
}
- /*
- Ch3 栈和队列
- */
- // 实例数据元素:学生
- typedef struct {
- char id[10];
- int age;
- double score;
- } Student;
- /* (顺序)栈 */
- // 栈数据结构定义
- #define MAX_SIZE 10
- typedef struct {
- Student *data;
- int size;
- } Stack;
- // 初始化栈
- Stack Create() {
- Stack stk;
- stk.data = new Student[MAX_SIZE];
- stk.size = 0;
- return stk;
- }
- // 获取栈顶元素
- bool Top(Stack &stk, Student &res) {
- if (stk.size == 0) {
- return false;
- }
- int top = stk.size - 1;
- res = stk.data[top];
- return true;
- }
- // 弹出栈顶元素
- bool Pop(Stack &stk) {
- if (stk.size == 0) {
- return false;
- }
- stk.size--;
- return true;
- }
- // 往栈顶压入一个元素
- bool Push(Stack &stk, const Student &s) {
- if (stk.size == MAX_SIZE) {
- return false;
- }
- int newTop = stk.size;
- stk.data[newTop] = s;
- stk.size++;
- return true;
- }
- /* 栈的应用:括号匹配 */
- #include <stack>
- #include <string>
- bool IsParenthesesMatch(std::string s) {
- std::stack<char> stk;
- for (int i = 0; i < s.length(); ++i) {
- switch (s[i]) {
- case '(':
- case '[':
- case '{':
- stk.push(s[i]);
- break;
- case ')':
- if (stk.empty() || stk.top() != '(') {
- return false;
- }
- stk.pop();
- break;
- case ']':
- if (stk.empty() || stk.top() != '[') {
- return false;
- }
- stk.pop();
- break;
- case '}':
- if (stk.empty() || stk.top() != '}') {
- return false;
- }
- stk.pop();
- break;
- }
- }
- return stk.empty();
- }
- /* 循环队列 */
- // 循环队列数据结构
- #define M 10
- typedef struct {
- Student data[M];
- int front;
- int back; // back表示队尾的下一个空位
- } CQueue; // C = Circulative
- // 循环队列入队
- bool Enqueue_CQ(CQueue &queue, const Student &s) {
- int newBack = (queue.back + 1) % M;
- if (newBack == queue.front) {
- return false; // 头尾相接表示队列满了
- }
- queue.data[queue.back] = s; // 放入队尾
- queue.back = newBack; // 移动back
- return true;
- }
- // 循环队列出队
- bool Dequeue_CQ(CQueue &queue) {
- if (queue.front == queue.back) {
- return false; // 头尾重合表示队列为空
- }
- queue.front = (queue.front + 1) % M;
- return true;
- }
- // 求循环队列元素个数
- int GetSize(CQueue &queue) {
- int size = (queue.back - queue.front + M) % M;
- return size;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。