队列、栈与循环队列实现

队列基本特性

• 队列 (Queue)：先进先出（FIFO）

  • 加入元素 → 放到尾部 R++

  • 弹出元素 → 从头部 L++

  • 判空条件：当 L == R 时为空；当 L < R 时队列中有数。

队列实现

// 普通队列：数组实现
public static class Queue1 {
    public int[] queue;
    public int l;
    public int r;

    public Queue1(int n){
        queue = new int[n];
        l = 0;
        r = 0;
    }

    // 判空
    public boolean isEmpty(){
        return l == r;
    }

    // 入队
    public void offer(int num){
        queue[r++] = num;
    }

    // 出队
    public int poll(){
        return queue[l++];
    }

    // 查看队头
    public int peek(){
        return queue[l];
    }

    // 查看队尾
    public int tail(){
        return queue[r-1];
    }

    // 当前大小
    public int size(){
        return r - l;
    }
}

栈实现

• 栈：后进先出 (LIFO)
• 入栈：放在 stack[size]，size++
• 出栈：取 stack[size-1]，size–

public static class MyStack {
    private int[] stack;
    private int size;

    public MyStack(int n){
        stack = new int[n];
        size = 0;
    }

    public void push(int x){
        stack[size++] = x;
    }

    public int pop(){
        return stack[--size];
    }

    public int peek(){
        return stack[size-1];
    }

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

    public int size(){
        return size;
    }
}

循坏队列

• 循环队列：解决普通数组队列无法复用空间的问题
• 利用 取模运算 或 条件判断 实现首尾相连
• 关键思想：头尾指针可回绕

// 循环队列实现
class MyCircularQueue {
    public int[] queue;   // 存储数组
    public int l, r;      // 头、尾指针
    public int size;      // 当前元素个数
    public int limit;     // 容量上限

    public MyCircularQueue(int k) {
        queue = new int[k];
        l = r = size = 0;
        limit = k;
    }

    // 入队
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        } else {
            queue[r] = value;
            r = (r == limit-1 ? 0 : (r+1)); // 尾指针环形移动
            size++;
            return true;
        }
    }

    // 出队
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        } else {
            l = (l == limit-1 ? 0 : (l+1)); // 头指针环形移动
            size--;
            return true;
        }
    }

    // 查看队头
    public int Front() {
        return isEmpty() ? -1 : queue[l];
    }

    // 查看队尾
    public int Rear() {
        if (isEmpty()) {
            return -1;
        } else {
            int last = (r == 0 ? (limit-1) : (r-1));
            return queue[last];
        }
    }

    // 判空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判满
    public boolean isFull() {
        return size == limit;
    }
}