队列(循环数组队列,用队列实现栈,用栈实现队列)

基础知识

队列(Queue):先进先出的数据结果,底层由双向链表实现

入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为对头

常用方法

boolean offer(E e)  入队

E(弹出元素的类型) poll() 出队

peek() 获取队头

int size 获取队列元素个数

boolean isEmpty() 判定队列是否为空

设计循环队列

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

思路:创建一个数组,useSize记录这个数组有效元素个数,rear记录这个数组(队列)下一个要插入的位置,front记录这个队列的对头,也就是要删除元素的位置.

插入元素:如果这个数组已经满了(useSize等于数组的长度),则插入失败返回false,没满就是往rear指向的位置放入一个元素,然后rear++,useSize++,值得注意的是这是一个循环队列,当rear指向的是数组的最后一个下标也就是(array.length-1),此时再如果让rear++,它就指向了array.length.数组是越界的,我们可以给一个判断条件,如果rear等于array.length,就让它重新等于0

删除元素:如果这个队列是空,则删除失败,不为空,就让front++,useSize--,这样就可以删除了,同理front也可能指向array.lenth,让他重新指向0就好了

获取队头元素:当队列为空获取失败,不为空就返回front下标指向的元素

获取队尾元素:当队列为空获取失败,不为空,因为rear指向的是下一个要插入的元素的位置,所以我们返回rear-1下标的元素就是当前的队尾元素,注意的是,当rear指向的是0时,也不为空说明它刚刚循环过来的,此时队尾元素就是数组最后的下标元素,返回即可

是否为空:useSize为0就为空,是否为满:useSize等于数组长度队列就满了

代码

class MyCircularQueue {
    private int[] array;
    private int front;
    private int rear;
    private int useSize;
    private int size;
    public MyCircularQueue(int k) {
       array = new int[k];
       size = k;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        array[rear] = value;
        rear++;
        if(rear==size){
            rear=0;
        }
        useSize++;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front++;
        if(front==size){
            front=0;
        }
        useSize--;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(rear-1<0){
            return array[size-1];
        }
        return array[rear-1];
    }
    
    public boolean isEmpty() {
        return useSize==0;
    }
    
    public boolean isFull() {
        return useSize==size;
    }
}

用队列实现栈

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

思路
创建俩个队列,qu1 和 qu2
入栈,如果qu1和qu2都为空(第一次入栈),就放入到qu1队列中,否则就入到不为空的队列中
出栈:找到不为空的队列,把useSize-1个元素移动到另一个队列当中去,如果俩个队列都为空,则出栈失败
查看栈顶元素:如果俩个队列都为空,查看失败,找到不为空的队列,把useSIze个元素移动到另一个队列中,每次入队列都用一个值来接收,这样入队列完成后,这个值就是栈顶元素,把它返回即可

class MyStack {
    private Queue qu1;
    private Queue 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()){
            int size = qu1.size();
            for(int i = 0;i1;i++){
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();
        }else{
            int size = qu2.size();
            for(int i = 0;i1;i++){
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();
        }
    }
    
    public int top() {
         if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size = qu1.size();
            int x = -1;
            for(int i = 0;i
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;
        }else{
            int size = qu2.size();
            int x = -1;
            for(int i = 0;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/

思路:
创建俩个栈,
入队:直接放到第一个栈中,
出队:出第二个队列中的数据,如果第二个队列中没有,就把第一个栈中的所有元素弹入到第二个栈中,
(第二个栈的顺序就是队列的顺序) 

代码

class MyQueue {
    private Stack qu1;
    private Stack qu2;
    public MyQueue() {
        qu1 = new Stack();
        qu2 = new Stack();
    }
    
    public void push(int x) {
        qu1.push(x);
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        if(qu2.isEmpty()){
            int size = qu1.size();
            while(size != 0){
                int x = qu1.pop();
                qu2.push(x);
                size--;
            }
        }
        return qu2.pop();
    }
    
    public int peek() {
          if(empty()){
            return -1;
        }
        if(qu2.isEmpty()){
            int size = qu1.size();
            while(size != 0){
                int x = qu1.pop();
                qu2.push(x);
                size--;
            }
        }
        return qu2.peek();
    }
    
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}