数据结构和算法（四）——栈及其相关算法

简介

栈是一种运算受限的线性表，只允许在一端（栈顶）插入和删除数据。栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据，其时间复杂度为O(1)。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈

常见算法思路 实现一个栈

示例1： 顺序栈

代码如下(如果之前没写过，最好自己写一次)：

 class SequentialStack{

          int capacity = 20;

          int[] stack = new int[capacity];

          int size = -1;

          public int pop(){
              if (size = stack.length){
                  capacity *= 2;
                  int[] temp = new int[capacity];
                  for (int i = 0; i