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];//默认容积为5
    int 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 + " ");
   }
}