Rookie's blog

Chapter3 栈

Chapter3 栈

栈的定义

  • 后进先出(LIFO, Last In First Out)表
  • 先进后出(FILO, First In Last Out)表
  • 最先(晚)到达栈的结点将最晚(先)被删除
  • 只能在一端进行插入和删除的线性表
image-20240611011245305

栈的运算

  • 创建一个栈create()：创建一个空的栈；
  • 进栈push(x)：将x插入栈中，使之成为栈顶元素；
  • 出栈pop()：删除栈顶元素并返回栈顶元素值；
  • 读栈顶元素top()：返回栈顶元素值但不删除栈顶元素；
  • 判栈空isEmpty()：若栈为空，返回true，否则返回false。
1
2
3
4
5
6
7
8
9
10
template <class elemType>
class stack
 { 
    public: 
	  virtual bool isEmpty() const = 0; 
	  virtual void push(const elemType &x) = 0; 
	  virtual elemType  pop() = 0;              
      virtual elemType  top() const = 0;        
	  virtual ~stack() {}
 };

栈的顺序实现

  • 用连续的空间存储栈中的结点，即数组
  • 进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。
image-20240611012410233

栈的链接实现

  • 栈的操作都是在栈顶进行的，因此不需要双链表，用单链表就足够了，而且不需要头结点
  • 对栈来讲，只需要考虑栈顶元素的插入删除。从栈的基本运算的实现方便性考虑，可将单链表的头指针指向栈顶。
image-20240611012936319

栈的应用

递归的时间复杂度计算

数学归纳法

  1. 找到问题中含有的递推关系T(n)=g(T(n−1))T(n) = g(T(n-1))
  2. 找到初始条件T(1)T(1)
  3. 使用数学归纳法进行递推转通项，即可直接写出T(n)T(n)，自然也就很容易写出O(n)O(n)

递归方程+主定理

主定理 设a≥1a \geq 1和b≥1b \geq 1为常数，设f(n)f(n)为一函数，则递归方程T(n)=aT(nb)+f(n),n>1T(n) = a T(\dfrac{n}{b}) + f(n), n>1的解是

  1. 若f(n)<O(nlog⁡ba)f(n) < O(n^{\log_b{a}})，则T(n)=O(nlog⁡ba)T(n) = O(n^{\log_b{a}})
  2. 若f(n)=O(nlog⁡ba)f(n) = O(n^{\log_b{a}})，则T(n)=O(nlog⁡balog⁡2n)T(n) = O(n^{\log_b{a}} \log_2 n)
  3. 若f(n)>O(nlog⁡ba)f(n) > O(n^{\log_b{a}})，则T(n)=O(f(n))T(n) = O(f(n))

生成函数法

设u0,u1,u2,⋯ ,un,⋯u_0,u_1,u_2,\cdots,u_n,\cdots是一无穷序列，称形式幂级数

G(t)=∑i≥0uitiG(t) = \sum_{i \geq 0} u_i t^i

为其生成函数

利用生成函数求得序列通项的步骤：

  1. 求出生成函数G(t)G(t)的有限形式：按递归关系消去无限的部分，留下有限部分
  2. 把G(t)G(t)​的有限形式展开成t的幂级数形式，求得通项

递归函数的非递归实现

括号配对

简单的计算器

中缀式和后缀式

对于一个表达式a + b

  • 前缀式：+ab

  • 中缀式：a+b

  • 后缀式：ab+

后缀表达式计算

  1. 初始化一个栈。
  2. 依次读入后缀式的操作数和运算符。
    1. 若读到的是操作数，则将其进栈。
    2. 若读到的是运算符，则将栈顶的两个操作数出栈，后弹出的操作数为被操作数，先弹出的为操作数，将得到的操作数完成运算符所规定的运算，并将结果进栈。
  3. 回到2的读入操作，继续。
  4. 当栈中只剩有一个操作数时，弹出该操作数，它就是表达式的值。
image-20240611004137845

中缀转后缀

  1. 若读入的是操作数，立即输出。
  2. 若读入的是闭括号，则将栈中的运算符依次出栈，并将其放在操作数序列之后。出栈操作一直进行到遇到相应的开括号为止。将开括号出栈。
  3. 若读入的是开括号，则进栈。
  4. 若读入的是运算符，如果栈顶运算符优先级高或相等，则栈顶运算符出栈；出栈操作一直要进行到栈顶运算符优先级低为止，然后将新读入的运算符进栈保存。
  5. 在读入操作结束时，将栈中所有的剩余运算符依次出栈，并放在操作数序列之后，直至栈空为止。
image-20240611004833062

中缀表达式直接计算

建两个栈，一个运算符栈，一个运算数栈

把中缀转后缀中的运算符栈出栈操作，改成直接对运算数栈栈顶的两个操作数出栈，完成运算符所规定的运算，然后再将结果压入运算数栈，就可以实现直接计算中缀表达式了。具体例子如下：

image-20240611010846745
0%