Java 栈与队列数据结构及代码实现

Java 栈和队列

栈的概念（Stack）

栈是常见的线性数据结构，栈的特点是以先进后出的形式，后进先出，分为栈底和栈顶。栈应用于内存的分配，表达式求值，存储临时的数据和方法的调用等。 例如这把枪，第一发子弹是最后发射的，第一发子弹在栈底，而最新安装上去的子弹在栈的顶部，只有将上面的子弹打完（栈顶的数据走完），最后一发子弹才会射出。

栈的实现

栈的实现是基于简单的数组形成的，我们可以将它想象成连续的数组，而栈的顺序是由后放到前放。

模拟实现栈的方法：push（放入一个元素到栈中）、pop（提取栈顶的一个元素，并将在其栈中消除）、peek（查看栈顶的元素）、size（查看栈中的大小）、empty（栈中是否为空）、full（栈是否满了）。

import java.util.Arrays;

public class MyStack implements IStack {
    private int[] elem;
    private int top; // 数组的栈顶，以及数组栈中存放元素的数量
    private static final int DEFAULT_CAPACITY = 10; // 这里是初始容量

    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
        top = -1; // 数组下标从 0 开始
    }

    @Override
    public void push(int item) {
        if (full()) { // 如果满了就扩容
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[++top] = item;
    }

    @Override
    public int pop() throws RuntimeException {
        try {
            if (empty()) {
                throw new RuntimeException("栈为空");
            }
        } catch (RuntimeException e) {
            e.printStackTrace();
        }
        return elem[top--]; // return 返回后删除栈顶的元素
    }

    @Override
    public int peek() {
        if (empty()) {
            throw new RuntimeException("栈为空");
        }
        return elem[top]; // 返回栈顶元素
    }

    @Override
    public int size() {
        return top + 1; // 去除数组 0
    }

    @Override
    public boolean empty() {
        return top == -1;
    }

    @Override
    public boolean full() {
        return top == elem.length; // count==当前的 elem 的总长度为 true
    }
}

队列（Queue）

队列是由先进先出的线性数据结构，采用的是先进先出，后进后出。如果要插入元素的话就是从入队尾巴方向插入，而删除作为出队要在头尾删除。

队列的方法包括 offer、poll、peek、size 等。

模拟实现队列 (双链表实现)

public class MyQueue implements IQueue {
    static class QueueNode {
        public int elem;
        public QueueNode next;
        public QueueNode prev;

        public QueueNode(int elem) {
            this.elem = elem;
        }
    }

    public QueueNode head;
    public QueueNode last;
    public int size = 0;

    @Override
    public void offer(int val) {
        QueueNode queue = new QueueNode(val);
        if (this.head == null) {
            this.head = queue;
            this.last = queue;
            ++size;
            return;
        }
        this.last.next = queue;
        queue.prev = this.last;
        this.last = queue;
        ++size;
    }

    @Override
    public int poll() {
        if (this.head == null) {
            throw new RuntimeException("没有要丢掉的队列");
        }
        QueueNode cur = this.head;
        if (this.head.next == null) {
            this.head = null;
            this.last = null;
            size--;
            return cur.elem;
        }
        this.head = this.head.next;
        this.head.prev = null;
        size--;
        return cur.elem;
    }

    @Override
    public int peek() {
        if (this.head != null) {
            return this.head.elem;
        }
        return 0;
    }

    @Override
    public int size() {
        return size;
    }
}

循环队列（循环数组实现）

数组实现队列的循环需要引入一个公式（目前的下标值 +1）% 当前数组的长度 (index+1)%array.length。下标值从 0 开始少一个数，当 index+1 就是当前的总长度时，公式后的值一定为下标 0。

private int[] array;
private int front;
private int rear;

public MyCircularQueue(int k) {
    array = new int[k + 1];
    front = 0; // 初始位置
    rear = 0;
}

public boolean enQueue(int value) {
    // 入列
    if (isFull()) { // 这里如果容量已经满了，需要先删除后在进行插入
        return false;
    }
    array[rear] = value; // rear 下标获取元素
    rear = (rear + 1) % array.length; // rear 最终循环为 0 下标
    return true;
}

public boolean deQueue() {
    // 出列
    if (isEmpty()) { // 为空返回 false
        return false;
    }
    front = (front + 1) % array.length; // front 只需要往后走
    return true;
}

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

public int Rear() {
    if (isEmpty()) {
        return -1;
    }
    // 这里三目操作符判断是否为 0 如果为 0，将 rear 回退到最后一个位置，不为 0 则 -1
    int temp = (rear == 0) ? array.length - 1 : rear - 1;
    return array[temp];
}

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

public boolean isFull() {
    return (rear + 1) % array.length == front;
}

用队列实现栈

因为队列是先进先出的，而我们的栈是先进后出的，两种线性结构的关系是颠倒的，一个队列是不能完成的，我们需要两个队列互相工作来完成。 辅助队列先获取数值，保证辅助队列是最后一个拿到值的，然后将主队列的值给到辅助队列，在交换两个队列的数值。因为队列关系先进先出，每一次最后一个值就是队列先出的数值。 主队列不为空，将主队列的元素都 poll 出放到辅助栈中，使用一个 tmp 来将主队列（这里主队列已经遍历完）和辅助队列交换。

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    Queue<Integer> q1; // 主队列
    Queue<Integer> q2; // 辅助队列

    public MyStack() {
        q1 = new LinkedList<>(); // 构造方法
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) { // 主队列不为空，则将主队列出列给到辅助队列
            q2.offer(q1.poll());
        }
        // 走到这里主队列是为空
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp; // 将两个队列交换
    }

    public int pop() {
        return q1.poll();
    }

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

    public boolean empty() {
        return q1.isEmpty();
    }
}

用栈来实现队列

栈来实现队列，栈是先进后出的顺序，而队列是先进先出的顺序。将 push 都放到 a 栈中，当我们 peek 或者是要删除的时候，我们都将 a 栈的元素 pop 给 b 栈，这样 b 栈已经有了我们的元素。

但是我们还需要考虑的是丢掉元素后如果在一起添加元素到 a 栈呢，这里我们给一个条件，如果 b 的栈不为空时，我们仍然用 b 栈的队列。如果 a 为空，这两个栈都是空的说明没有元素直接返回 -1，如果 a 不为空的话且 b 没有新的元素 b 继续捕获新的 a 栈中所有的元素。

import java.util.Stack;

class MyQueue {
    Stack<Integer> A;
    Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

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

    public int pop() {
        int check = peek();
        B.pop();
        return check;
    }

    public int peek() {
        // 先判断 b 是否是空的，如果不是空的直接返回，是空才可以往下走
        if (!B.isEmpty()) return B.peek();
        // 因为 b 还不是空的，所以不需要将 a 栈放到 b 中
        if (A.isEmpty()) return -1;
        while (!A.isEmpty()) {
            B.push(A.pop()); // 将所有的 a 放到 b 中
        }
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty(); // a 和 b 都为空才为空
    }
}

总结

栈分为栈顶和栈底，最先进的为栈底，最后进的为栈顶。 队列分为队头和队尾，最先进的为队头，最后进的为队尾。