队列的详细解读

队列的解读！

• 定义
• 底层实现原理

定义

定义：操作受限的线性表，添加在一端进行，删除在另一端进行。

特点：先进先出，其中的方法和栈有所类似

底层实现原理

非循环队列

front 指队头
rear 指队尾
队空条件：front == rear
队满条件：rear = Maxsize - 1

我们先写一个队列的泛型类，做一些初始化的操作

class SqQueueClass<E> {
    final int MaxSize = 100;
    private E[] data;
    private int front,rear;
    public SqQueueClass() {
        data = (E[]) new Object[MaxSize];
        front = -1;
        rear = -1;
    }
}

判断是否为空

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

进队

  public void push(E e) {
        if(rear == MaxSize - 1) {
            throw new IllegalArgumentException("队满");
        }
        rear++;
        data[rear] = e;
    }

出队

public E pop(E e) {
        if(empty()) {
            throw new IllegalArgumentException("队空");
        }
        front++;
        return (E)data[front];
    }

取队头元素

public E peek() {
        if(empty()) {
            throw new IllegalArgumentException("队空");
        }
        return data[front + 1];
    }

循环队列

为了克服假溢出，我们可以把队列看成一个环，也称为环形队列
循环队列是首尾相连
因为循环队列中，如果按非循环队列的思路来思考的话，则判断队满和队空都为front == rear
所以在这里我们特意留一个空位，这样子，牺牲一个空位，这样子就可以解决问题

队空：front == rear
队满：（rear + 1)%Maxsize == front
进队： rear = (rear + 1)% Maxsize
出队： front = (front + 1)% Maxsize

判断队列是否为空

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

判断是否满队列

public boolean isFull() {
        return (rear + 1) % MaxSize == front;
    }

进队

public void push(E e) {
        if(isFull()) {
            throw new IllegalArgumentException("队满");
        }
        rear = (rear + 1) % MaxSize;
        data[rear] = e;
    }

出队

public E pop(E e) {
        if(empty()) {
            throw new IllegalArgumentException("队空");
        }
        front = (front + 1) % MaxSize;
        return (E)data[front];
    }

取队头

 public E peek() {
        if(empty()) {
            throw new IllegalArgumentException("队空");
        }
        return (E)data[(front + 1) % MaxSize];
    }

返回元素个数

public int size() {
        return (rear - front + MaxSize) % MaxSize;  
    }

循环队列算法设计示例

对一个队列，利用队列基本运算，设计进队，出队第k（k >= 1)个元素算法

进队第k个元素，思路如下：
我们可以将前k - 1个元素直接出队再入队，当循环来到第k个元素的位置时，这时把进队元素进队，然后继续，边出队入队

public static boolean pushk (SqQueueClass<Integer> qu,int k ,Integer e) {
        int n = qu.size();
        if(k < 1 || k > n + 1) {
            return false;
        }
        if(k < n) {
            for(int i = 1;i <= n; i++) {
                if(i == k) {
                    qu.push(e);
                }
                //出队，入队
                qu.push(qu.pop());
            }
        } else {
            qu.push(e);
        }
        return true;
    }

同理，出队第k个元素，和以上思路相似，只是再第k个元素的时候，是将其pop（）

public static boolean pushk (SqQueueClass<Integer> qu,int k) {
        int n = qu.size();
        if(k < 1 || k > n + 1) {
            return false;
        }
        if(k < n) {
            for(int i = 1;i <= n; i++) {
                if(i == k) {
                    qu.pop();
                }
                //出队，入队
                qu.push(qu.pop());
            }
        } else {
            qu.push(e);
        }
        return true;
    }