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

基础知识

队列(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<Integer> qu1;private Queue<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()){int size = qu1.size();for(int i = 0;i<size-1;i++){int x = qu1.poll();qu2.offer(x);}return qu1.poll();}else{int size = qu2.size();for(int i = 0;i<size-1;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<size;i++){x = qu1.poll();qu2.offer(x);}return x;}else{int size = qu2.size();int x = -1;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/

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

代码

class MyQueue {private Stack<Integer> qu1;private Stack<Integer> 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();}
}