【数据结构】_6.队列

目录

1.概念

2.队列的使用

3.队列模拟实现

4.循环队列

5.双端队列

6.OJ题

6.1 用队列实现栈

6.2 用栈实现队列

---

1.概念

（1）队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；

（2）队列具有先进先出，后进后出的特点；

（3）入队列：进行插入操作的一端称为队尾；

         出队列：进行删除操作的一端称为队头；

2.队列的使用

在java中，Queue是个接口，底层是通过链表实现的，其常用方法如下：

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素的个数
boolean isEmpty()	检测队列是否为空

3.队列模拟实现

（1）包类关系：

（2）TestMyQueue：

package TestMyQueue;import TestMyStack.EmptyException;public class MyQueue {// 使用单链表实现队列static class Node{public int val;public Node next;public Node(int val){this.val = val;}}public Node head;public Node last;public int usedSize;public void offer(int val){Node newNode = new Node(val);if(head == null){head = newNode;last = newNode;}else{last.next = newNode;last = newNode;usedSize++;}}public int poll(){if(isEmpty()){throw new EmptyException();}int ret = head.val;head = head.next;return ret;}public boolean isEmpty(){return usedSize == 0;}public int peek(){if(isEmpty()){throw new EmptyException();}int ret = head.val;return ret;}public int getUseSize(){return usedSize;}
}

 （3）EmptyException：

package TestMyQueue;public class EmptyException extends RuntimeException{public EmptyException(){}
}

4.循环队列

题目链接：622. 设计循环队列 - 力扣（LeetCode）

 代码：

class MyCircularQueue {private int[] elem;private int front;   // 表示队列的头private int rear;    // 表示队列的尾public MyCircularQueue(int k) {this.elem = new int[k+1];}public boolean enQueue(int value) {// 入队列判满if(isFull()){return false;}elem[rear] = value;rear = (rear+1)% elem.length;return true;}public boolean deQueue() {// 判空if(isEmpty()){return false;}front = (front+1)% elem.length;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index = (rear==0)?elem.length-1:rear-1;return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {// 写法1：
//        if( (rear+1) % elem.length == front){
//            return true;
//        }
//        return false;// 写法2：return (rear+1)% elem.length == front;}
}

5.双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列；

Deque是一个接口，使用时必须创建其实现类类的对象：

常用的实现类为ArrayDeque（由数组实现的双端队列）和LinkedList（由双向链表实现的双端队列），故而实例化Deque的方式有以下两种： 

        // 链式双端队列Deque<Integer> deque = new LinkedList<>();// 数组双端队列Deque<Integer> deque2 = new ArrayDeque<>();

注：也可以使用Deque实现顺序栈：

实际上，以下写法：

Stack<Integer> stack = new Stack<>(); 

即：直接使用Stack类实例化栈对象是很少用的，可以使用ArrayDeque创建顺序栈对象：

Deque<Integer> stack2 = new ArrayDeque<>();

6.OJ题

6.1 用队列实现栈

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

解题思路：使用两个队列实现栈，元素入栈至不为空的队列，元素出栈在不为空的队列出栈size-1个元素，最后余下的元素就是要出栈的元素；如果两个队列均为空，则入第一个队列；

代码：

public class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if(!queue1.isEmpty()){queue1.offer(x);}else if(!queue2.isEmpty()){queue2.offer(x);}else{queue1.offer(x);}}public int pop() {if(empty()){// 当前栈为空return -1;}if(!queue1.isEmpty()){int size = queue1.size();for(int i=0;i<size-1;i++){//for(int i=0;i<queue1.size()-1;i++){  //写法错误,poll会导致size变化int ret = queue1.poll();queue2.offer(ret);}return queue1.poll();}else{int size = queue2.size();for(int i=0;i<size-1;i++){int ret = queue2.poll();queue1.offer(ret);}return queue2.poll();}}public int top() {if(empty()){return -1;}if(!queue1.isEmpty()){int size = queue1.size();int ret = -1;for(int i=0;i<size;i++){ret = queue1.poll();queue2.offer(ret);}return ret;}else{int size = queue2.size();int ret = -1;for(int i=0;i<size;i++){ret = queue2.poll();queue1.offer(ret);}return ret;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

6.2 用栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

解题思路：使用两个栈实现队列，stack1用于入栈元素，当需要出栈元素时，若stack2不为空，直接出栈stack2栈顶元素，如果stack2为空，就将stack1的所有元素入栈到stack2中，再出栈stack2顶元素即可；

代码：

class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}