文章目录
- 一、队列是什么？
- 二、模拟实现队列
- 三、模拟实现循环队列
- 四、用队列实现栈
- 五、用栈实现队列
一、队列是什么？
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出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 " /> 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(); }}