栈的定义

  • 栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。 它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。 栈具有记忆作用,对栈的插入与删除操作中,不需要改变栈底指针。

  • 简单的来讲,栈是一种具有 后进先出 特性的一种数据结构。只能从栈顶插入元素和拿出元素,有一个指针始终指向栈顶,也就是最后插入栈的元素。

  • image.png

  • 乒乓球大炮

  • 上图的大炮,每次只能发出最后一个放入的乒乓球。

静态栈

  • 通过静态数组模拟,能有效的提高效率。

  • 变量介绍

    • stk[N] -> 模拟栈空间
    • tt -> 指向栈顶,栈为空的时候为 -1
  • 栈的操作

    • 定义栈
      • 
        	const int N = 100005;
        	int stk[N], tt;
        	// 初始化栈为空
        	init() {
        		tt = -1;
        	}
        
    • 向栈中添加元素
      • image.png
      • 	push(int x) {
        		stk[++ tt] = x; // 将元素放入栈中,并更新栈顶为当前元素。
        	}
        
    • 从栈中弹出一个元素
      • image.png
      • 	int pop() {
        		return stk[tt --];
        	}
        
        
    • 判断栈是否为空
      • 	bool empty() {
        		return tt == -1? true:false;
        	}
        
    • 查看栈顶元素的值
      • 
        	int front() {
        		return stk[tt];
        	}
        

单调栈

  • 存储元素具有一定的单调性的栈。从小到大,或从大到小