搜索
写经验 领红包

数据结构栈和队列笔记(数据结构栈和队列知识点总结)

导语:数据结构栈与队列之作死攻略

先看个漫画放松下

目录

1 栈是啥?

2 栈的实现方式

2.1 顺序栈(Array-based Stack)

2.2 链式栈(Linked Stack)

2.3 共享栈

2.4 栈的应用-四则运算表达式求值

2.3.1 后缀表达式

后缀表达式:运算符号位于两个运算数之后。

用堆栈实现后缀表达式求值:

运算数:入栈运算符:从栈中弹出最前的两个数,计算并将结果入栈栈顶上的元素就是表达式的结果值

例:

漫画乱入,纯属娱乐。

2.3.2 中缀表达式

中缀表达式:运算符号位于两个运算数之间。

中缀表达式求值:将中缀表达式转换为后缀表达式,然后求值。

中缀表达式转换为后缀表达式:

从头到尾读取中缀表达式的每个对象运算数:直接输出左括号:压入堆栈右括号:将栈顶的运算符弹出并输出,知道遇到左括号(出栈,括号不输出)运算符:

若优先级大于栈顶运算符时,把它压栈若优先级小于栈顶运算符时,将栈顶运算符弹出并输出,而它进栈若各对象处理完毕,则把堆栈中存留的运算符一并输出

2 队列

2.1 队列是啥?

2.2 队列的实现方式

2.2.1 顺序队列

例子:假设现在顺序队列Q分配了6个空间

(1) 开始时为空队,Q.front=Q.rear

(2) 元素a1进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位

(3) 元素a2进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位

(4) 元素a3,a4,a5分别按顺序进队,尾指针Q.rear依次后移

(5) 元素a1出队,头指针Q.front(整型下标)后移一位

(6) 元素a2出队,头指针Q.front(整型下标)后移一位

(7) 元素a6进队,放入尾指针rear(整型下标)的位置,rear后移一位

(8) 元素a7进队,此时尾指针Q.rear已经超过了数组的下标,无法再存储进队,但是我们发现前面明明有2个空间,却出现了队满的情况,这种情况称为。

2.2.2 循环队列

上面第(7)步元素a6进队之后,尾指针Q.rear要后移一个位置,此时已经超过了数组的下标,即Q.rear+1=Maxsize(最大空间数6),那么如果前面有空闲,Q.rear可以转向前面0的位置

然后元素a7进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位

元素a8进队,放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位

这时候虽然队列空间存满了,但是出现了一个大问题,队满时Q.front=Q.rear,这和队空的条件一模一样,无法区分队空还是队满,如何解决呢?有两种办法:一是设置一个标志,标记队空和队满;另一种办法是浪费一个空间,当尾指针Q.rear的下一个位置Q.front是时,就认为是队满。如图所示:

上述到达尾部又向前存储的队列称为循环队列,为了避免,我们通常采用循环队列。

循环队列无论入队还是出队,队尾、队头加1后都要取模运算,例如入队后队尾后移一位:Q.rear =(Q.rear+1)%Maxsize。

为什么要%Maxsize呢?

主要是为了处理临界状态,即Q.rear向后移动一个位置Q.rear+1后,很有可能超出了数组的下标,这时它的下一个位置其实是0,如果将一维数组画成环形图,如图所示:

上图中最大空间Maxsize,当Q.rear=Maxsize-1时,(Q.rear+1)%Maxsize=0,而且Q.front=0,正好满足队满的条件:(Q.rear+1) %Maxsize= Q.front,此时为队满。

因此无论是front还是rear向后移动一个位置时,都要加1与最大空间Maxsize取模运算,处理临界问题。

总结:

队空:Q.front=Q.rear; // Q.rear和Q.front指向同一个位置

队满: (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front

入队:

Q.base[Q.rear]=x; //将元素放入Q.rear所指空间

Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位

出队:

e= Q.base[Q.front]; //用变量记录Q.front所指元素

Q.front=(Q.front+1) %Maxsize // Q. front向后移一位

循环队列中包含的元素个数:

2.2.3 链式队列

2.2.4 双端队列

双端队列可以在队列任意一端入队出队。将队列的两端分别称为前端和后端。

(1)输出受限的双端队列

允许在一端进行入队和出队,在另一端只允许入队。

(2)输入受限的双端队列

允许在一端进行入队和出队,在另一端只允许出队

​漫画乱入,甭管我。

2.3 队列的应用

2.3.1 队列在计算机系统中的应用

参考自:

张铭《数据结构与算法》

陈越,何钦铭《数据结构》

程杰《大话数据结构》

邓俊辉《数据结构》

本文内容由小薇整理编辑!