栈
概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
一道关于集合的小练习(美团面试题)
答案：c
集合中的栈
可以看到集合中的栈继承于Vector类：
我们的Vector类继承于AbstractList类，实现了List接口：
我们再来看下集合中的栈都有哪些方法：
ALT+7我们可以看到Stack类中的方法
下面我们来对其中的一些方法进行实现:
push&peek方法
概念
push方法：将项目推送到此堆栈的顶部 peek方法：是拿到栈顶元素，并不是删除，是查看
代码示例
public class TestDemo5 { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); //push是入栈操作,输出结果为【1，2，3】 System.out.println(stack); //stack.peek()是拿到栈顶元素，并不是删除 //输出结果为3 System.out.println(stack.peek()); } }
pop方法
概念
pop方法：删除此堆栈顶部的对象
代码示例
public class TestDemo5 { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); //打印我们所弹出的元素3，并将3出栈 //输出结果为3 System.out.println(stack.pop()); //因为使用了pop方法，所以输出结果为2 System.out.println(stack.peek()); } }
注意事项(EmptyStackException异常)
在上面的代码中，栈有三个元素，当我们使用pop方法三次后，此时栈中就已经没有元素了，假设此时我们再使用一次pop方法，会发生什么样的情况呢？我们来看代码:
public class TestDemo5 { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.pop(); stack.pop(); stack.pop(); //第四次使用，会发生EmptyStackException异常 stack.pop(); } }
输出结果:
empty方法
概念
empty方法；测试此堆栈是否为空,为空返回true,不为空返回false.返回值类型为boolean
代码示例
public class TestDemo5 { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.pop(); stack.pop(); stack.pop(); //因为使用了三次pop方法，所以输出结果为true System.out.println(stack.empty()); } }
isEmpty方法
概念
这个方法在Stack类中是没有被定义的，它是继承于我们的Vector类，但是效果跟我们的empty方法是一样的，判断我们的栈是否为空，为空返回true,不为空返回false
代码示例
public class TestDemo5 { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.pop(); stack.pop(); stack.pop(); //因为使用了三次pop方法，所以输出结果为true System.out.println(stack.isEmpty()); } }
中缀表达式转后缀表达式(面试笔试常考选择题)
后缀表达式也就是我们常说的逆波兰表达式
我们先通过一道练习题再来说明什么是前缀，什么是中缀，什么是后缀
练习题1
这道题目的做法如下：
为了方便区分括号，我们把括号都换成不同的颜色：
1：首先对已有的括号进行换色：
2：然后依照从左到右，先乘除，后加减的原则来对运算加上括号：
3：然后将每个运算符移动到自己所对应的括号的外面：
4:最后将所有括号去掉，得到的就是我们的后缀表达式
所以这道题目最终答案为A.
总结
一般的题目就是考察中缀转后缀，中缀表达式一般题目中会直接给出的
前缀表达式就是在我们加完括号移动的过程中将运算符移动到自己对应的括号的前面
后缀表达式是在我们加完括号后移动的过程中将运算符移动到自己对应的括号的后面
前缀表达式和后缀表达式都是没有括号的表达式
计算机一般对于计算前缀和后缀表达式比较容易
为什么这么说呢？我们来举个例子
对于题目中的中缀表达式来说我们把它换成数字的形式，如下图所示：
转换成后缀表达式的形式为：
那么计算机是如何对这个后缀表达式进行运算的呢？来看：
1:首先初始化一个空栈，当遇到数字的时候就将数字压栈，如下所示
2:这时候遇到第一个符号是+号，此时把栈顶元素作为右操作数，把栈顶元素的下一个元素作为左操作数，那么此处的式子就变成了1+2=3
3:然后将3这个元素压栈：如下所示：
4：此时又碰到了减号，那就将3作为右操作数，4作为左操作数，得到4-3=1.，然后将1压栈，如下所示：
5:此时又碰到了乘号，那就将1作为右操作数，2作为左操作数，得到2*1=2.，然后将2压栈，如下所示：
6：此时碰到了数字2，就将其压栈即可：
7：此时又碰到了除号，那就将2作为右操作数，下一个2作为左操作数，得到2/2=1.，然后将1压栈，如下所示：
8：最后碰到了加号，那就将1作为右操作数，下一个1作为左操作数，得到1+1=2,而这个2与我们中缀表达式算出来的结果一摸一样，这也是计算机在处理中缀表达式时的时候会先将其转变为后缀表达式，然后将其按照上述方式进行运算，最终得出结果
练习题2
答案：
自己动手实现一个栈(数组实现)
栈的底层其实就是一个数组：来看代码实现：
public class MyStack { //栈的底层其实也是数组 private int[] elem; // top可以代表下标，表达的意思是当前栈中可以插入的元素的位置的下标 // top还可以代表当前栈中元素的个数 private int top; public MyStack() { this.elem = new int[10]; } //判断栈是否满 public boolean isFull() { return this.top == this.elem.length; } //将元素压栈 public int push(int item) { if (isFull()) { throw new RuntimeException("栈已经满了"); } this.elem[this.top] = item; this.top++; //注意压栈的时候的下标为this.top-1 return this.elem[this.top - 1]; } /** * 弹出栈顶元素 并且删除 * @return */ public int pop() { if (isEmpty()) { throw new RuntimeException("栈是空的，不能进行删除"); } this.top--; //注意此处删除元素的时候下标应该是this.top //这个下标相当于下次插入的时候将元素进行替换 return this.elem[this.top]; } /** * 拿到栈顶元素不删除 * @return */ public int peek() { if (isEmpty()) { throw new RuntimeException("栈为空"); } return this.elem[this.top - 1]; } //判断栈是否为空 public boolean isEmpty() { return this.top == 0; } //得到栈的长度 public int size() { return this.top; } }
测试类：
public class TestDemo { public static void main(String[] args) { MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.push(3); stack.push(1); stack.push(2); stack.push(3); //stack.peek() 拿到栈顶元素，但是不是删除 System.out.println(stack.peek());//3 //弹出栈顶元素 3 System.out.println(stack.pop());//3 System.out.println(stack.peek());//2 System.out.println(stack.pop());//2 System.out.println(stack.pop());//1 System.out.println(stack.empty()); System.out.println(stack.pop());//3 } }
使用链表来实现栈
如果此时用链表实现栈，那么入栈用头插法好还是尾插法好呢？
答：头插法好，不管是出栈还是入栈时间复杂度都会达到O(1).
如果使用尾插法的话，此时我们需要找到链表的尾节点，就需要我们去遍历整个链表，那么不管是出栈还是入栈时间复杂度都会达到O(N),
