java详解队列
文章目录
- 一、队列是什么？
- 二、模拟实现队列
- 三、模拟实现循环队列
- 四、用队列实现栈
- 五、用栈实现队列
一、队列是什么？
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）
队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。
LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
二、模拟实现队列
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。同学们思考下：队列的实现使用顺序结构还是链式结构好？
因为队列是一种先进先出的数据结构，顺序表要想达到此目的，删除和取数据时间复杂度达到了O(n),那我们可不可以用单链表而且时间复杂度是O(1)呢？
public class MyQueue {
static class ListNode {
public int value;
public ListNode next;
public ListNode(int value) {
this.value = value;
}
}
public ListNode head;
public ListNode tail;
//入队列
public void offer(int data) {
ListNode node = new ListNode(data);
if(head == null) {
head = node;
tail = node;
return;
}
tail.next = node;
tail = node;
}
//出队列
public int poll() {
if(isEmpty()) {
return -1;
}
int ret = head.value;
head = head.next;
if(head == null) {
tail = null;
}
return ret;
}
//查看队列第一个元素
public int peek() {
if(isEmpty()) {
return -1;
}
int ret = head.value;
return ret;
}
//判断队列是否为空
public boolean isEmpty() {
return size() == 0;
}
//获取队列大小
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
}
三、模拟实现循环队列
循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。
在实现循环队列时，我们主要面临的问题是，什么情况下队列为空，什么情况下队列为满，在判断满时：我们有两种方案，定义一个size变量，如果等于0为空，等于队列容量为满，这种过于简单，我们采用浪费一个空间的办法，如果head == tail队列为空,如果tail的下一个位置为head为满。
class MyCircularQueue {
public int[] arr;
public MyCircularQueue(int k) {
arr = new int[k+1];
}
public int front;
public int rear;
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
arr[rear] = value;
rear = (rear + 1) % arr.length;
return true;
}
public boolean deQueue() {
if(isEmpty()) {
return false;
}
front = (front + 1) % arr.length;
return true;
}
public int Front() {
if(!isEmpty()) {
return arr[front];
}
return -1;
}
public int Rear() {
if(!isEmpty()) {
int ret = rear == 0 ? arr.length - 1 : rear - 1;
return arr[ret];
}
return -1;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % arr.length == front;
}
}
四、用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
public Queue<Integer> qu1;
public Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
if(empty()) {
qu1.offer(x);
return;
}
if(qu1.isEmpty()) {
qu2.offer(x);
}else {
qu1.offer(x);
}
}
public int pop() {
if(empty()) {
return -1;
}
if(qu1.isEmpty()) {
int x = qu2.size();
for (int i = 0; i < x - 1; i++) {
qu1.offer(qu2.poll());
}
return qu2.poll();
}else {
int x = qu1.size();
for (int i = 0; i < x - 1; i++) {
qu2.offer(qu1.poll());
}
return qu1.poll();
}
}
public int top() {
if(empty()) {
return -1;
}
if(qu1.isEmpty()) {
int x = qu2.size();
for (int i = 0; i < x - 1; i++) {
qu1.offer(qu2.poll());
}
int ret = qu2.poll();
qu1.offer(ret);
return ret;
}else {
int x = qu1.size();
for (int i = 0; i < x - 1; i++) {
qu2.offer(qu1.poll());
}
int ret = qu1.poll();
qu2.offer(ret);
return ret;
}
}
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}
五、用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
import java.util.Stack;
class MyQueue{
public Stack<Integer> s1;
public Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(empty()) {
return -1;
}
if(!s2.empty()) {
return s2.pop();
}else {
while(!s1.empty()) {
s2.push(s1.pop());
}
return s2.pop();
}
}
public int peek() {
if(empty()) {
return -1;
}
if(!s2.empty()) {
return s2.peek();
}else {
while(!s1.empty()) {
s2.push(s1.pop());
}
return s2.peek();
}
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}