数据结构-栈

发表于 更新于 分类于 ，

栈(Stack) 作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。 栈只能在一端进行操作，即遵循先进后出的原则。就如同在抽屉里存放书，先放入的书会被压倒最底下，后放入的书在上面，取书的时候先放入的书最后才能被取出来。

栈的基本操作

关于栈的操作有栈的建立(顺序栈和链式栈) ， 栈的初始化 ，栈的初始化 ，栈遍历 ，栈清空/销毁 ，判断栈是否为空 ，求栈的长度 ，入栈出栈等。其中 入栈和出栈 是最基本的操作。 * 入栈(push)：top指针上移，元素入栈。 * 出栈(pop)：top指针下移。
入栈时要判断是否满栈。出栈时要判断是否栈空。栈顶指针位置始终在栈顶元素加一处。

单调栈

单调栈是栈的扩展运用。单调栈就是栈内元素单调递增或者单调递减的栈，单调栈只能在栈顶操作。
对于单调栈来说，当新加入的元素如果加到栈顶后，如果栈里的元素不再是单调递增了（新元素破坏了栈的单调性），那么我们就删除加入前的栈顶元素。 * 使用单调栈可以找到元素向左遍历第一个比他小的元素，也可以找到元素向左遍历第一个比他大的元素。

栈的运用

消除字符串中相邻的重复项：

比如给定一个字符串：s='acddcyyrc'，删除后结果为'arc'.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String removeDuplicates(String S) {
       StringBuffer stack = new StringBuffer();
       int top = -1;
       for (int i = 0; i < S.length(); ++i) {
           char ch = S.charAt(i);
           if (top >= 0 && stack.charAt(top) == ch) {
               stack.deleteCharAt(top);
               --top;
           } else {
               stack.append(ch);
               ++top;
           }
       }
       return stack.toString();
   }