java 数据结构栈和队列

栈(Stack)

栈的使用

栈的模拟实现

栈的应用场景

队列(Queue)

队列的使用

队列模拟实现

循环队列

双端队列

用队列实现栈

用栈实现队列

栈(Stack)

什么是栈？

栈：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操

作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO （ Last In First Out ）的原则。

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。

出栈：栈的删除操作叫做出栈。 出数据在栈顶。

栈的使用

方法例子：

public static void main(String[] args) {
Stack<Integer> s = new Stack();
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
System.out.println(s.size()); // 获取栈中有效元素个数---> 4
System.out.println(s.peek()); // 获取栈顶元素---> 4
    s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
    if(s.empty()){
        System.out.println("栈空");
    }else{
        System.out.println(s.size());
}
}

栈的模拟实现

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是

Vector是线程安全的。

模拟实现代码：

public class MyStack {
    int[] array;
    int size;

    public MyStack() {
        array = new int[3];
    }

    public int push(int e) {
        ensureCapacity();
        array[size++] = e;
        return e;
    }

    public int pop() {
        int e = peek();
        size--;
        return e;
    }

    public int peek() {
        if (empty()) {
            throw new RuntimeException("栈为空，无法获取栈顶元素");
        }
        return array[size - 1];
    }

    public int size() {
        return size;
    }

    public boolean empty() {
        return 0 == size;
    }

    private void ensureCapacity() {
        if (size == array.length) {
            array = Arrays.copyOf(array, size * 2);
        }
    }
}

栈的应用场景

1.逆波兰表达式(中缀转后缀)：

https://leetcode.cn/problems/evaluate-reverse-polish-notation/

代码：

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for(String x:tokens){
            if(!isCase(x)){
            stack.push(Integer.parseInt(x));
            }else{
        int nums2=stack.pop();
        int nums1=stack.pop();
        switch(x){
            case "+":
                stack.push(nums1+nums2);
            break;
            case "-":
                stack.push(nums1-nums2);
            break;
            case "*":
                stack.push(nums1*nums2);
            break;
            case "/":
                stack.push(nums1/nums2);
            break;
        }
        }  
    }
    return stack.pop();
}
    public boolean isCase(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }
        return false;
    }

}

2.括号匹配：

https://leetcode.cn/problems/valid-parentheses/description/

代码：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //遍历
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);//取出字符
            //判断是不是左括号
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                //遇到右括号,判断栈是不是空
                if (stack.empty()) {
                    return false;
                }
                //看看括号匹不匹配
                char ch2 = stack.peek();
                if ((ch2 == '(' && ch == ')') || (ch2 == '{' && ch == '}') || (ch2 == '[' && ch == ']')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        //如果栈不空,并且遍历完了
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

3.出栈入栈次序匹配：

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

代码：

    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            //每进栈一个数字,peek一下判断一不一样,并且判断越没越界
            while (!stack.empty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        //循环走完了,判断是不是空,是的话就匹配了,不是的话就不匹配
        return stack.empty();
}

4.最小栈：

https://leetcode.cn/problems/min-stack/

代码：

class MinStack {

    public Stack<Integer> stack;
    public Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.empty()) {
            minStack.push(val);
        } else {
            int minVal = minStack.peek();
            //判断最小栈的栈顶是不是小于等于要存入的值
            if (val <= minVal) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if (stack.peek().equals(minStack.peek())) {
            // 弹出的元素是全栈最小的
            minStack.pop();
        }
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        if (!minStack.empty()) {
            return minStack.peek();
        }
        return -1;
}
}

队列(Queue)

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进

先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾（ Tail/Rear ）出队列：进行删

除操作的一端称为队头（ Head/Front ）

队列的使用

在 Java 中， Queue 是个接口，底层是通过链表实现 的。

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了

Queue接口。

用法例子：

public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
    q.offer(1);
    q.offer(2);
    q.offer(3);
    q.offer(4);
    q.offer(5); // 从队尾入队列
System.out.println(q.size());
System.out.println(q.peek()); // 获取队头元素
    q.poll();
System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
    if(q.isEmpty()){
        System.out.println("队列空");
    }else{
        System.out.println(q.size());
}
}

队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常

见的空间类型有两种：顺序结构和链式结构 。同学们思考下： 队列的实现使用顺序结构还是链式

结构好？

模拟实现代码：

public class Queue {
    // 双向链表节点
    public static class ListNode {
        ListNode next;
        ListNode prev;
        int value;

        ListNode(int value) {
            this.value = value;
        }
    }

    ListNode first; // 队头
    ListNode last; // 队尾
    int size = 0;

    // 入队列---向双向链表位置插入新节点
    public void offer(int e) {
        ListNode newNode = new ListNode(e);
        if (first == null) {
            first = newNode;
// last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
// last = newNode;
        }
        last = newNode;
        size++;
    }

    // 出队列---将双向链表第一个节点删除掉
    public int poll() {
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int value = 0;
        if (first == null) {
            return null;
        } else if (first == last) {
            last = null;
            first = null;
        } else {
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }

    // 获取队头元素---获取链表中第一个节点的值域
    public int peek() {
        if (first == null) {
            return null;
        }
        return first.value;
    }

    public int size() {
        return size;
    }

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

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会

使用循环队列。环形队列通常使用数组实现。

https://leetcode.cn/problems/design-circular-queue/description/

代码：

public class MyCircularQueue {
    public int[] elem;
    public int front; // 队头
    public int rear; // 队尾
    public int usedSize; // 记录队列中元素数量

    public MyCircularQueue(int k) {
        elem = new int[k];
        usedSize = 0; // 初始化为 0
    }

    // 入队
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        usedSize++; // 每次入队增加 usedSize
        return true;
    }

    // 出队
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % elem.length;
        usedSize--; // 每次出队减少 usedSize
        return true;
    }

    // 得到队头元素
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    // 得到队尾元素
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        //如果是0下标就返回数组长度-1不是就rear-1
        int index = (rear == 0) ? elem.length - 1 : rear - 1;
        return elem[index];
    }

    public boolean isEmpty() {
        return usedSize == 0; // 使用 usedSize 判断是否为空
    }

    public boolean isFull() {
        return usedSize == elem.length; // 使用 usedSize 判断是否为满
    }
}

双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended

queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

Deque是一个接口，使用时必须创建LinkedList的对象

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

代码：

class MyStack {// 用队列实现栈
    //用两个队列实现
    public Deque<Integer> qu1;
    public Deque<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if (!qu1.isEmpty()) {
            qu1.offer(x);
        } else if (!qu2.isEmpty()) {
            qu2.offer(x);
        } else {
            //都空的,指定存
            qu1.offer(x);
        }
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (!qu1.isEmpty()) {
            //这样记录不会因为poll改变
            int size = qu1.size();
            for (int i = 0; i < size - 1; i++) {//取到长度减1个就是要的了
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();
        } else {
            int size = qu2.size();
            for (int i = 0; i < size - 1; i++) {//取到长度减1个就是要的了
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();
        }
    }

    public int top() {
        if (empty()) {
            return -1;
        }
        if (!qu1.isEmpty()) {
            //这样记录不会因为poll改变
            int size = qu1.size();
            int x = 0;//用来记录拿出来的值,循环结束后就拿到最后一个
            for (int i = 0; i < size; i++) {
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;
        } else {
            int size = qu2.size();
            int x = 0;//用来记录拿出来的值,循环结束后就拿到最后一个
            for (int i = 0; i < size ; i++) {
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;
        }
    }

    public boolean empty() {
        //判断两个队列是不是都空的
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/

代码：

public class MyQueue {

    public Stack<Integer> s1;
    public Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }


    public int peek() {
        if (empty()) {
            return -1;
        }
        if (s2.isEmpty()) {
            int size = s1.size();
            for (int i = 0; i < size; i++) {
                int x = s1.pop();
                s2.push(x);
            }
        }
        return s2.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}