[数据结构与算法]【数据结构】栈和队列

栈

概念

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

其两种操作方式：
压栈：也就是数据的插入，插入位置在栈顶。
出栈：栈的删除，删除位置在栈顶。

栈的使用

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        /**
         * 压栈，在栈顶放入
         */
        stack.push(1);
        stack.push(2);
        stack.push(3);
        /**
         * 出栈，把栈顶元素弹出并返回
         */
        System.out.println(stack.pop());
        /**
         * 返回栈顶元素，不删除
         */
        System.out.println(stack.peek());
        /**
         * 获取当前栈中元素个数
         */
        System.out.println(stack.size());
        /**
         * 检查栈是否为空
         */
        System.out.println(stack.empty());
    }

栈的模拟实现

public class MyStack {
    private int[] elem;
    private int usedSize;

    public MyStack() {
        this.elem = new int[5];
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空！");
        }
        int oldVal = elem[usedSize - 1];
        usedSize--;
        return oldVal;
    }
    private boolean isFull() {
        return this.usedSize == elem.length;
    }
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空！");
        }
        return elem[usedSize - 1];
    }

    public int push(int item) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize++] = item;
        return item;
    }
}

栈的应用场景

1. 把递归转化为循环

例如递归打印链表

void printList(Node head){
	if(null != head){
		printList(head.next);
		System.out.print(head.val + " ");
	}
}

循环方式打印

void printList(Node head){
	if(null == head){
	return;
} 
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 + " ");
	}
}

2. 括号匹配

OJ链接

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

思路：每一个左括号都有其对应的右括号，所以我们所以栈来检查每一次的括号是否匹配，遇到左括号入栈，然后检查下一个括号是否和它匹配，匹配则出栈，继续检查。

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);
            }
            if (stack.empty()) {
                return false;
            } 
            if (c == ')' && stack.pop() != '(') {
                return false;
            } else if (c == '}' && stack.pop() != '{') {
                return false;
            } else if (c == ']' && stack.pop() != '[') {
                return false;
            } 
        }
        return stack.empty();

    }
}

可以优化，先根据本次左括号压入对应右括号，在检查下一次是否括号是否匹配

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

3. 逆波兰表达式求值

OJ链接

逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后。因此，逆波兰表达式也称后缀表达式。

思路：逆波兰表达式严格遵循「从左到右」的运算,所以我们可以用栈来存储数据，遇到运算符则弹出两个元素，注意第一个弹出的为右操作数，第二个弹出的为左操作数，然后把计算出的结果放入栈中，直到没有数据。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String val : tokens) {
            //如果不是运算符
            if (!isOperation(val)) {
                stack.push(Integer.parseInt(val));
            } else {
                //出栈并且计算
                //定义左右操作数,注意：第一个出栈的是右操作数
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(val) {
                    case "/" :
                        stack.push(num1 / num2);
                        break;
                    case "*" :
                        stack.push(num1 * num2);
                        break;
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String s) {
        if (s.equals("/") || s.equals("*") ||s.equals("-") ||s.equals("+")) {
            return true;
        }
        return false;
    }
}

4. 出栈入栈次序匹配

OJ链接

思路：由于压栈的时候也可以出栈，所以每一次我们先把压入序列的元素和弹出序列元素比较，如果不相同，则压入元素，否则弹出元素，最后我们只需要判断栈是否为空

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        for (;i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() &&stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

队列

概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

队列的使用

Queue是接口，底层是链表。

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        /**
         * 入队,从尾入
         */
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        /**
         * 出队，出队头元素
         */
        System.out.println(queue.poll());
        /**
         * 获取队头元素
         */
        System.out.println(queue.peek());
        /**
         *获取队列中元素个数
         */
        System.out.println(queue.size());
        /**
         * 检查队列是否为空
         */
        System.out.println(queue.isEmpty());
    }

队列的模拟实现

队列的模拟实现的底层逻辑可以用线性表和链表，我们分别使用二者实现：

1. 链表

我们使用单链表实现，如果把head作为头则offer为O(n)，poll为O(1),为了实现O(1)的时间复杂度，我们定义一个头，尾哨兵位，指向头和尾，这样可以达到O(1)。

public class MyStack {

    static class Node {
        private int val;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    private Node front;
    private Node rear;

    public int peek(){
        if (isEmpty()) {
            throw new RuntimeException("空");
        }
        return front.val;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public void offer(int e) {
        Node node = new Node(e);
        if (isEmpty()) {
            rear = node;
            front = node;
        }
        rear.next = node;
        rear = node;
    }

    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("空");
        }
        int oldVal = front.val;
        front = front.next;
        return oldVal;
    }
}

2. 线性表

循环队列并不是物理空间循环，而是逻辑上是一个环。

这里我们我们可以通过取余的操作来得到“循环”

index = (index + offset) % array.length

offset为偏移量，index为下标， array.length为数组长度。

开始时头指针和尾指针都指向同一位置，那么我们如何判断数组已满呢？

1. 添加size属性：添加元素size++，删除元素size–，当size == array.length时满
   2.留一位置：每次添加元素后检查front 是否等于rear + 1 如图：

3. 使用标记：定义一个flag初始为true，当二次相遇时，flag置为false，此时相遇。

设计循环队列

class MyCircularQueue {
    private  int[] elem;
    private  int front;
    private  int rear;


    public MyCircularQueue(int k) {
        this.elem = new int[k + 1];
        this.front = 0;
        this.rear = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            elem[rear] = value;
            rear = (rear + 1) % elem.length;
            return true;
        }
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }else {
            front = (front + 1 ) % elem.length;
            return true;
        }
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[front];
    }


    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return elem[(rear - 1 + elem.length) % elem.length];
    }

    public boolean isEmpty() {
        return this.rear == this.front;
    }


    public boolean isFull() {
        if ((rear + 1) % elem.length == front) {
            return true;
        } else {
            return false;
        }
    }
}

双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队.

    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        /**
         * 从队头入队
         */
        deque.offerFirst(1);
        deque.offerFirst(2);
        /**
         * 从队尾入队
         */
        deque.offerLast(3);
        deque.offerLast(4);
        /**
         * 队头元素出队
         */
        deque.pollFirst();
        /**
         * 队尾元素出队
         */
        deque.pollLast();
        /**
         * 返回队头元素
         */
        System.out.println(deque.peekFirst());
        /**
         * 返回队尾元素
         */
        System.out.println(deque.peekLast());
        /**
         * 检查队列是否为空
         */
        System.out.println(deque.isEmpty());
    }

面试题

1. 用队列实现栈。链接

思路：用两个队列，一个用来push，一个用来pop

class MyStack {
    private Queue<Integer> q;//pop
    private Queue<Integer> p;//push
    public MyStack() {
        q = new LinkedList<>();
        p = new LinkedList<>();
    }
    
    public void push(int x) {
        p.offer(x);
        //这里把q中的元素放入p中，完成倒置
        while (!q.isEmpty()) {
            p.offer(q.poll());
        }
        //然后交换q,p现在的q中元素序列就和栈一样
        Queue tmp = q;
        q = p;
        p = tmp;
    }
    
    public int pop() {
        return q.poll();
    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.isEmpty();
    }
}

思路：一个队列，每次push时把队列倒置

class MyStack {
    private Queue<Integer> q;

    public MyStack() {
        q = new LinkedList<>();
    }
    
    public void push(int x) {
        int m = q.size();
        q.offer(x);
        //倒置队列
        while (m-- > 0) {
            q.offer(q.poll());
        }
    }
    
    public int pop() {
        return q.poll();

    }
    
    public int top() {
        return q.peek();
    }
    
    public boolean empty() {
        return q.isEmpty();
    }
}

2. 用栈实现队列 链接

思路：用两个栈一个接受数据，另一个输出数据，

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if (!stack2.empty()) {
            return stack2.pop();
        } else {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if (!stack2.empty()) {
            return stack2.peek();
        } else {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack2.empty() && stack1.empty();
    }
}

3. 最小栈 链接

思路：一个普通栈接受数据，另一个记录当前元素中的最小值栈

class MinStack {
        //普通栈
        private Stack<Integer> stack; 
        //最小栈
        private Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        //判断该值是否为最小值
        if (minStack.empty() || val <= minStack.peek()) {
                minStack.push(val);
        }
    }
    
    public void pop() {
        //删除元素为最小值时，minStack也要删除
        if (!stack.empty()) {
            int popVal = stack.pop();
            if (minStack.peek() == popVal) {
            minStack.pop();
            }          
        }

    }
    
    public int top() {
        if (!stack.empty()) {
            return stack.peek();
        }
        throw new RuntimeException("栈为空");
    }
    
    public int getMin() {
        if (!minStack.empty()) {
            return minStack.peek();
        }
        throw new RuntimeException("栈为空！");
    }

}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖