Collection与数据结构 Stack与Queue(一): 栈与Stack

1. 栈

1.1 概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

栈在现实生活中的例子:
弹夹:

羽毛球筒:

1.2 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

import java.util.Stack;public class Main {public static void main(String[] args) {//使用Stack中自带的方法Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);stack.push(4);//压栈System.out.println(stack.peek());System.out.println(stack.peek());//没有弹出元素,只是返回了栈顶元素System.out.println(stack.pop());System.out.println(stack.pop());//出栈System.out.println(stack.size());//计算栈中元素的个数System.out.println(stack.empty());//判断栈是否为空//使用Stack从Collection继承下来的方法Stack<Integer> stack1 = new Stack<>();stack1.add(1);stack1.add(2);stack1.add(3);stack1.add(4);//添加元素System.out.println(stack1.isEmpty());//判断是否为空}
}

运行结果:

1.3 栈的模拟实现

import java.util.Arrays;public class MyStack {int[] array = new int[5];//默认容积为5int size;public void push(int x){ensureCapacity();array[size] = x;size++;}public int pop(){int e = peek();size--;return e;}public int peek(){if (!empty()){return array[size-1];}throw new EmptyExecption("Stack is empty.");}public boolean empty(){if (size == 0){return true;}return false;}public int size(){return this.size;}private void ensureCapacity(){if (this.array.length == size){this.array = Arrays.copyOf(array,array.length*2);}}
}
public class EmptyExecption extends RuntimeException{public EmptyExecption(String message) {super(message);}
}

2. 栈的相关面试题

2.1 括号匹配

OJ链接

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(' || c == '[' || c == '{') {stack.push(c);//左括号入栈}else {if (stack.empty()){return false;//如果在匹配的时候,栈为空,说明右括号赘余}char ch2 = stack.peek();if (ch2 == '(' && c == ')'||ch2 == '[' && c == ']'||ch2 == '{' && c == '}'){stack.pop();}else {return false;//括号不匹配}}}return stack.empty();//遍历完了,栈中还有元素,说明左括号赘余}}

上述代码逻辑较为复杂,我们通过一张图来理清楚:

2.2 逆波兰表达式求值

OJ链接

class Solution2 {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (int i = 0; i < tokens.length; i++) {String s = tokens[i];if (isOperation(s)){int x1 = stack.pop();int x2 = stack.pop();//把两个数字出栈int x = 0;if (s.equals("+")){x = x1+x2;} else if (s.equals("-")) {x = x2-x1;//注意逆波兰表达式,先从栈中弹出的放在后面} else if (s.equals("/")) {x = x2/x1;}else {x = x1*x2;}stack.push(x);//计算之后放回栈中}else {stack.push(Integer.parseInt(s));//将字符串转化为数字}}return stack.pop();//最后栈中的值就是最终的值}private boolean isOperation(String s){//判断是否为加减乘除if (s.equals("+") ||s.equals("-")||s.equals("*")||s.equals("/")){return true;}return false;}}

拓展: 中缀表达式转后缀表达式,现给出中缀表达式( 1 + 2 ) * ( 3 + 4 ),转为后缀(逆波兰)表达式过程如下.

其实我们在电脑中或者是手机上经常用到的计算器就是这样的原理.计算机中的计算器是无法直接识别中缀表达式的,都是先转为后缀表达式,再进行运算的.

2.3 入栈出栈顺序匹配

OJ链接

class Solution3 {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushed.length; i++) {stack.push(pushed[i]);while (!stack.empty() &&stack.peek() == popped[j]){//每放入栈中一个元素,就和popped比较是否相等stack.pop();//如果相等,出栈j++;//popped下标向后走}}while (j < popped.length){//i把push全部遍历完之后,Stack中可能还有元素没有与popped中的匹配完成if (stack.peek() == popped[j]){stack.pop();j++;//继续匹配操作}else {return false;//一旦有一个不匹配,说明popped的出栈顺序是错误的}}return true;//全部匹配完成,返回true}}

2.4 在常数时间复杂度的情况下寻找栈中最小元素

OJ链接

class MinStack {Stack<Integer> stack;Stack<Integer> stack1;public MinStack() {stack = new Stack<>();//放所有要入栈的元素stack1 = new Stack<>();//放较小元素,栈顶元素是入stack所有元素中最小的}public void push(int val) {stack.push(val);if (stack1.empty()){//如果最小栈中没有元素,就把第一个元素放入stack1.push(val);}else{if(stack1.peek() >= val){//和最小栈的栈顶元素比较大小,stack1的栈顶大于等于val的时候,入栈//等于的时候也要放入,否则pop的时候,最小栈和普通栈会不匹配stack1.push(val);}}}public void pop() {if (Objects.equals(stack.pop(), stack1.peek())){stack1.pop();//两栈元素相等的时候都弹出,否则只弹出普通栈中的元素}}public int top() {return stack.peek();//返回普通栈栈顶元素}public int getMin() {return stack1.peek();//直接返回最小栈的栈顶元素}}

2.5 逆序打印列表

方法一:递归法

void printList(Node head){if(null != head){//遇到null的时候往回递归printList(head.next);//没有遇到null的时候,向后递归System.out.print(head.val + " ");}
}

图解:

方法二:Stack法

 Stack<Node> s = new Stack<>();// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}
}

从上述代码,我们可以得到一个结论,栈可以替代递归思想,在我们后期学习二叉树的时候,在非递归遍历二叉树的时候,我们会频繁地用到栈.