面试算法大全-栈总结

￡神魔★判官ぃ 2022-10-17 13:50 146阅读 0赞

## 4、栈 ##

### 4.1 栈的定义和特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1OTY0NTU_size_16_color_FFFFFF_t_70_pic_center]

（1）栈的存储结构

栈既然是一种线性结构，就能够以数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。

（2）栈的操作

栈的常用操作为：

弹栈，通常命名为pop

压栈，通常命名为push

求栈的大小

判断栈是否为空

获取栈顶元素的值

### 4.2 栈的的实现 ###

#### 4.2.1 用数组实现栈 ####

//定义一个 ArrayStack 表示栈
    class ArrayStack {
        
    	private int maxSize; // 栈的大小
    	private int[] stack; // 数组，数组模拟栈，数据就放在该数组
    	private int top = -1;// top表示栈顶，初始化为-1
    	//构造器
    	public ArrayStack(int maxSize) {
        
    		this.maxSize = maxSize;
    		stack = new int[this.maxSize];
    	}
    	//栈满
    	public boolean isFull() {
        
    		return top == maxSize - 1;
    	}
    	//栈空
    	public boolean isEmpty() {
        
    		return top == -1;
    	}
    	//入栈-push
    	public void push(int value) {
        
    		//先判断栈是否满
    		if(isFull()) {
        
    			System.out.println("栈满");
    			return;
    		}
    		top++;
    		stack[top] = value;
    	}
    	//出栈-pop, 将栈顶的数据返回
    	public int pop() {
        
    		//先判断栈是否空
    		if(isEmpty()) {
        
    			//抛出异常
    			throw new RuntimeException("栈空，没有数据~");
    		}
    		int value = stack[top];
    		top--;
    		return value;
    	}
    	//显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
    	public void list() {
        
    		if(isEmpty()) {
        
    			System.out.println("栈空，没有数据~~");
    			return;
    		}
    		//需要从栈顶开始显示数据
    		for(int i = top; i >= 0 ; i--) {
        
    			System.out.printf("stack[%d]=%d\n", i, stack[i]);
    		}
    	}
    /// 数组实现栈
    import java.lang.reflect.Array;
    interface Stack1<E>{
        
        boolean isEmpty();
        boolean isFull();
        void push(E item);
        E pop();
        E peek();
        void clear();
    }
    public class ArrayStack<E> implements Stack1<E>{
        
        private int top;
        private int stackSize;
        private Object stackArr[];
        public ArrayStack (int stackSize){
        
            top=-1;
            this.stackSize=stackSize;
            stackArr=new Object[stackSize];
        }
    
        @Override
        public boolean isEmpty() {
        
            return (top==-1);
        }
    
        @Override
        public boolean isFull() {
        
            return (top==this.stackSize-1);
        }
    
       @Override
        public void push(E item) {
        
            if(isFull()){
        
                System.out.println("Stack is full!");
            }else {
        
                stackArr[++top]=item;
                System.out.println("Inserted Item: "+item);
            }
        }
    
        @Override
        public E pop() {
        
            if(isEmpty()){
        
                System.out.println("Deleting fail! Stack is empty!");
                return null;
            }else {
        
                System.out.println("Deleted Item : "+stackArr[top]);
                return (E)stackArr[top--];
            }
        }
    
        @Override
        public E peek() {
        
            if(isEmpty()){
        
                System.out.println("Peeking fail! Stack is empty!");
                return null;
            }else {
        
                System.out.println("Peeking Item : "+stackArr[top]);
                return (E)stackArr[top];
            }
        }
    
        @Override
        public void clear() {
        
            if(isEmpty()){
        
                System.out.println("Stack is already empty!");
            }else {
        
                top=-1;
                stackArr=new Object[this.stackSize];
                System.out.println("Stack is clear!");
            }
        }
    
        public int size(){
        
            return top+1;
        }
        public void printStack(){
        
            if(isEmpty()){
        
                System.out.println("Stack is empty");
            }else {
        
                System.out.print("Stack elements : ");
                for(int i=0;i<=top;i++) {
        
                    System.out.print(stackArr[i] + " ");
                }
            }
            System.out.println();
        }
    }

#### 4.2.2 用链表实现栈 ####

public class LinkStack<E> {
        
    	// 链栈的节点
    	private class Node<E> {
        
    		E e;
    		Node<E> next;
    		public Node() {
        
    		}
    		public Node(E e, Node next) {
        
    			this.e = e;
    			this.next = next;
    		}
    	}
    	private Node<E> top; // 栈顶元素
    	private int size; // 当前栈大小
    	public LinkStack() {
        
    		top = null;
    	}
    	// 当前栈大小
    	public int length() {
        
    		return size;
    	}
    	// 判空
    	public boolean empty() {
        
    		return size == 0;
    	}
    	// 入栈：让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
    	public boolean push(E e) {
        
    		top = new Node(e, top);
    		size++;
    		return true;
    	}
    	// 查看栈顶元素但不删除
    	public Node<E> peek() {
        
    		if (empty()) {
        
    			throw new RuntimeException("空栈异常！");
    		} else {
        
    			return top;
    		}
    	}
    	// 出栈
    	public Node<E> pop() {
        
    		if (empty()) {
        
    			throw new RuntimeException("空栈异常！");
    		} else {
        
    			Node<E> value = top; // 得到栈顶元素
    			top = top.next; // 让top引用指向原栈顶元素的下一个元素
    			value.next = null; // 释放原栈顶元素的next引用
    			size--;
    			return value;
    		}
    	}
    }

#### 4.2.3 用两个队列实现栈 ####

import java.util.LinkedList;
    import java.util.Queue;
    /**
     * 两个队列实现一个栈
     *  
     * 一个队列加入元素，弹出元素时，需要把队列中的 元素放到另外一个队列中，删除最后一个元素
     * 两个队列始终保持只有一个队列是有数据的
     *
     */
    public class StackByQueue<T> {
        
    	private Queue<T> queue1 = new LinkedList<>();
    	private Queue<T> queue2 = new LinkedList<>();
    	/**
      	 * 压栈 
      	 * 
      	 * 入栈非空的队列
    	 */
    	public boolean push(T t) {
        
    		if (!queue1.isEmpty()) {
        
    			return queue1.offer(t);
    		} else {
        
    			return queue2.offer(t);
    		}
    	}
    	/**
    	 * 弹出并删除元素 
    	 */
    	public T pop() {
        
    		if (queue1.isEmpty() && queue2.isEmpty()) {
        
    			throw new RuntimeException("queue is empty");
    		}
    		if (!queue1.isEmpty() && queue2.isEmpty()) {
        
    			while (queue1.size() > 1) {
        
    				queue2.offer(queue1.poll());
    			}
    			return queue1.poll();
    		}
    		if (queue1.isEmpty() && !queue2.isEmpty()) {
        
    			while (queue2.size() > 1) {
        
    				queue1.offer(queue2.poll());
    			}
    			return queue2.poll();
    		}
    		return null;
    	}
    	
    	@Override
    	public String toString() {
        
    		return this.queue1.toString() + ", " +this.queue2.toString();
    	}
    	
    	public static void main(String[] args) {
        
    		StackByQueue<Integer> s = new StackByQueue<>();
    		s.push(1);
    		s.push(3);
    		s.pop();
    		System.out.println(s);
    		s.push(5);
    		s.pop();
    		System.out.println(s);
    	}
     
    }

#### 4.2.4 一个队列实现栈 ####

class MyStack {
        
        public Queue<Integer> queue;
        /** Initialize your data structure here. */
        public MyStack() {
        
            queue = new LinkedList<>();
        }
        /** Push element x onto stack. */
        public void push(int x) {
        
            queue.add(x);
            int size = queue.size();
            while(size-- > 1){
        
                queue.add(queue.poll());
            }
        }
        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
        
            return queue.poll();
        }
        /** Get the top element. */
        public int top() {
        
            return queue.peek();
        }
        /** Returns whether the stack is empty. */
        public boolean empty() {
        
            return queue.size()==0;
        }
    }

### 4.3 经典题目源码 ###

#### [最小栈][Link 1] ####

class MinStack {
        
        Deque<Integer> xStack;
        Deque<Integer> minStack;
    
        public MinStack() {
        
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }
        
        public void push(int x) {
        
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }
        
        public void pop() {
        
            xStack.pop();
            minStack.pop();
        }
        
        public int top() {
        
            return xStack.peek();
        }
        
        public int getMin() {
        
            return minStack.peek();
        }
    }

#### [包含min函数的栈][min] ####

第一种：链表实现

class MinStack {
        
        //链表头，相当于栈顶
        private ListNode head;
        //压栈，需要判断栈是否为空
        public void push(int x) {
        
            if (empty())
                head = new ListNode(x, x, null);
            else
                head = new ListNode(x, Math.min(x, head.min), head);
        }
        //出栈，相当于把链表头删除
        public void pop() {
        
            if (empty())
                throw new IllegalStateException("栈为空……");
            head = head.next;
        }
        //栈顶的值也就是链表头的值
        public int top() {
        
            if (empty())
                throw new IllegalStateException("栈为空……");
            return head.val;
        }
        //链表中头结点保存的是整个链表最小的值，所以返回head.min也就是
        //相当于返回栈中最小的值
        public int min() {
        
            if (empty())
                throw new IllegalStateException("栈为空……");
            return head.min;
        }
        //判断栈是否为空
        private boolean empty() {
        
            return head == null;
        }
    }
    class ListNode {
        
        public int val;
        public int min;//最小值
        public ListNode next;
    
        public ListNode(int val, int min, ListNode next) {
        
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }

第二种：使用栈

class MinStack {
        
        private Stack<StackNode> stack = new Stack<>();
        //压栈
        public void push(int x) {
        
            if (empty()) {
        
                stack.push(new StackNode(x, x));
            } else {
        
                stack.push(new StackNode(x, Math.min(x, min())));
            }
        }
        //出栈
        public void pop() {
        
            if (empty())
                throw new IllegalStateException("栈为空……");
            stack.pop();
        }
        public int top() {
        
            if (empty())
                throw new IllegalStateException("栈为空……");
            return stack.peek().val;
        }
        public int min() {
        
            if (empty())
                throw new IllegalStateException("栈为空……");
            return stack.peek().min;
        }
        //判断栈是否为空
        private boolean empty() {
        
            return stack.isEmpty();
        }
    }
    class StackNode {
        
        public int val;
        public int min;
        public StackNode(int val, int min) {
        
            this.val = val;
            this.min = min;
        }
    }

class MinStack {
        //push方法可能会加入很多min
        int min = Integer.MAX_VALUE;
        Stack<Integer> stack = new Stack<>();
        public void push(int x) {
        
            //如果加入的值小于最小值，要更新最小值
            if (x <= min) {
        
                stack.push(min);
                min = x;
            }
            stack.push(x);
        }
        public void pop() {
        
            //如果把最小值出栈了，就更新最小值
            if (stack.pop() == min)
                min = stack.pop();
        }
        public int top() {
        
            return stack.peek();
        }
        public int min() {
        
            return min;
        }
    }

public class MinStack {
        
        long min;
        Stack<Long> stack = new Stack<>();
        public void push(int x) {
        
            if (stack.isEmpty()) {
        
                stack.push(0L);
                min = x;
            } else {
        
                //这里入栈的是入栈的值和最小值的差值，有可能为负，也有可能为正。
                stack.push(x - min);
                if (x < min)
                    min = x;
            }
        }
        public void pop() {
        
            if (stack.isEmpty())
                return;
            long pop = stack.pop();
            //因为入栈的是差值，当出栈的为负数的时候，说明栈中最小值已经出栈了，
            //这里要重新更新最小值
            if (pop < 0)
                min -= pop;
        }
        public int top() {
        
            long top = stack.peek();
            if (top > 0) {
        
                //栈顶元素如果是正的，说明栈顶元素压栈的时候是比栈中最小值大的，根据
                //top=x - min，可以计算x=top+min
                return (int) (top + min);
            } else {
        
                //当栈顶元素是负数的时候，说明栈顶元素压栈的时候是比栈中最小值小的，
                //而压栈完之后他会更新最小值min，所以如果在使用上面公式肯定是不行
                //的。如果栈顶元素压栈的时候比最小值小，他会更新最小值，这个最小值
                //就是我们要压栈的值，所以这里直接返回min就行了。
                return (int) (min);
            }
        }
        public int min() {
        
            return (int) min;
        }
    }

第三种：使用双栈

class MinStack {
        
        //栈1存放的是需要压栈的值
        Stack<Integer> stack1 = new Stack<>();
        //栈2存放的是最小值
        Stack<Integer> stack2 = new Stack<>();
        public void push(int x) {
        
            stack1.push(x);
            if (stack2.empty() || x <= min())
                stack2.push(x);
        }
        public void pop() {
        
            //如果出栈的值等于最小值，说明栈中的最小值
            //已经出栈了，因为stack2中的栈顶元素存放的
            //就是最小值，所以stack2栈顶元素也要出栈
            if (stack1.pop() == min())
                stack2.pop();
        }
        public int top() {
        
            return stack1.peek();
        }
        public int min() {
        
            return stack2.peek();
        }
    }

#### [有效的括号][Link 2] ####

class Solution {
        
        public boolean isValid(String s) {
        
            int n = s.length();
            if (n % 2 == 1) {
        
                return false;
            }
    
            Map<Character, Character> pairs = new HashMap<Character, Character>() {
        {
        
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }};
            Deque<Character> stack = new LinkedList<Character>();
            for (int i = 0; i < n; i++) {
        
                char ch = s.charAt(i);
                if (pairs.containsKey(ch)) {
        
                    if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
        
                        return false;
                    }
                    stack.pop();
                } else {
        
                    stack.push(ch);
                }
            }
            return stack.isEmpty();
        }
    }

#### [逆波兰表达式求值][Link 3] ####

class Solution {
        
    	// 栈实现   8 ms	36.7 MB	
    	public static int evalRPN(String[] tokens) {
        
    		Stack<Integer> numStack = new Stack<>();
    		Integer op1, op2;
    		for (String s : tokens) {
        
    			switch (s) {
        
    			case "+":
    				op2 = numStack.pop();
    				op1 = numStack.pop();
    				numStack.push(op1 + op2);
    				break;
    			case "-":
    				op2 = numStack.pop();
    				op1 = numStack.pop();
    				numStack.push(op1 - op2);
    				break;
    			case "*":
    				op2 = numStack.pop();
    				op1 = numStack.pop();
    				numStack.push(op1 * op2);
    				break;
    			case "/":
    				op2 = numStack.pop();
    				op1 = numStack.pop();
    				numStack.push(op1 / op2);
    				break;
    			default:
    				numStack.push(Integer.valueOf(s));
    				break;
    			}
    		}
    		return numStack.pop();
    	}
    }

#### [比较含退格的字符串][Link 4] ####

class Solution {
        
        public boolean backspaceCompare(String S, String T) {
        
            return build(S).equals(build(T));
        }
    
        public String build(String str) {
        
            StringBuffer ret = new StringBuffer();
            int length = str.length();
            for (int i = 0; i < length; ++i) {
        
                char ch = str.charAt(i);
                if (ch != '#') {
        
                    ret.append(ch);
                } else {
        
                    if (ret.length() > 0) {
        
                        ret.deleteCharAt(ret.length() - 1);
                    }
                }
            }
            return ret.toString();
        }
    }

方法二：双指针

class Solution {
        
        public boolean backspaceCompare(String S, String T) {
        
            int i = S.length() - 1, j = T.length() - 1;
            int skipS = 0, skipT = 0;
    
            while (i >= 0 || j >= 0) {
        
                while (i >= 0) {
        
                    if (S.charAt(i) == '#') {
        
                        skipS++;
                        i--;
                    } else if (skipS > 0) {
        
                        skipS--;
                        i--;
                    } else {
        
                        break;
                    }
                }
                while (j >= 0) {
        
                    if (T.charAt(j) == '#') {
        
                        skipT++;
                        j--;
                    } else if (skipT > 0) {
        
                        skipT--;
                        j--;
                    } else {
        
                        break;
                    }
                }
                if (i >= 0 && j >= 0) {
        
                    if (S.charAt(i) != T.charAt(j)) {
        
                        return false;
                    }
                } else {
        
                    if (i >= 0 || j >= 0) {
        
                        return false;
                    }
                }
                i--;
                j--;
            }
            return true;
        }
    }

#### [基本计算器][Link 5] ####

方法一：栈和反转字符串

class Solution {
        
        public int evaluateExpr(Stack<Object> stack) {
        
            int res = 0;
            if (!stack.empty()) {
        
                res = (int) stack.pop();
            }
            // Evaluate the expression till we get corresponding ')'
            while (!stack.empty() && !((char) stack.peek() == ')')) {
        
                char sign = (char) stack.pop();
                if (sign == '+') {
        
                    res += (int) stack.pop();
                } else {
        
                    res -= (int) stack.pop();
                }
            }
            return res;
        }
        public int calculate(String s) {
        
            int operand = 0;
            int n = 0;
            Stack<Object> stack = new Stack<Object>();
            for (int i = s.length() - 1; i >= 0; i--) {
        
                char ch = s.charAt(i);
                if (Character.isDigit(ch)) {
        
                    // Forming the operand - in reverse order.
                    operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
                    n += 1;
                } else if (ch != ' ') {
        
                    if (n != 0) {
        
                        // Save the operand on the stack
                        // As we encounter some non-digit.
                        stack.push(operand);
                        n = 0;
                        operand = 0;
                    }
                    if (ch == '(') {
        
                        int res = evaluateExpr(stack);
                        stack.pop();
                        // Append the evaluated result to the stack.
                        // This result could be of a sub-expression within the parenthesis.
                        stack.push(res);
                    } else {
        
                        // For other non-digits just push onto the stack.
                        stack.push(ch);
                    }
                }
            }
            //Push the last operand to stack, if any.
            if (n != 0) {
        
                stack.push(operand);
            }
            // Evaluate any left overs in the stack.
            return evaluateExpr(stack);
        }
    }

方法二：栈和不反转字符串

class Solution {
        
        public int calculate(String s) {
        
            Stack<Integer> stack = new Stack<Integer>();
            int operand = 0;
            int result = 0; // For the on-going result
            int sign = 1;  // 1 means positive, -1 means negative
            for (int i = 0; i < s.length(); i++) {
        
                char ch = s.charAt(i);
                if (Character.isDigit(ch)) {
        
                    // Forming operand, since it could be more than one digit
                    operand = 10 * operand + (int) (ch - '0');
    
                } else if (ch == '+') {
        
                    // Evaluate the expression to the left,
                    // with result, sign, operand
                    result += sign * operand;
                    // Save the recently encountered '+' sign
                    sign = 1;
                    // Reset operand
                    operand = 0;
                } else if (ch == '-') {
        
                    result += sign * operand;
                    sign = -1;
                    operand = 0;
                } else if (ch == '(') {
        
                    // Push the result and sign on to the stack, for later
                    // We push the result first, then sign
                    stack.push(result);
                    stack.push(sign);
                    // Reset operand and result, as if new evaluation begins for the new sub-expression
                    sign = 1;
                    result = 0;
                } else if (ch == ')') {
        
                    // Evaluate the expression to the left
                    // with result, sign and operand
                    result += sign * operand;
                    // ')' marks end of expression within a set of parenthesis
                    // Its result is multiplied with sign on top of stack
                    // as stack.pop() is the sign before the parenthesis
                    result *= stack.pop();
                    // Then add to the next operand on the top.
                    // as stack.pop() is the result calculated before this parenthesis
                    // (operand on stack) + (sign on stack * (result from parenthesis))
                    result += stack.pop();
                    // Reset the operand
                    operand = 0;
                }
            }
            return result + (sign * operand);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1OTY0NTU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/6da6b277f72e40ff8a1b1eb320abdd0e.png
[Link 1]: https://leetcode-cn.com/problems/min-stack/
[min]: https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
[Link 2]: https://leetcode-cn.com/problems/valid-parentheses/
[Link 3]: https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
[Link 4]: https://leetcode-cn.com/problems/backspace-string-compare/
[Link 5]: https://leetcode-cn.com/problems/basic-calculator/