队列介绍
队列（Queue）是计算机中常见的数据结构，是一种操作受限的线性表。队列遵循 FIFO （先进先出） 原则，队列元素的增加在队尾，队列元素的读、取在队首。可以通过数组、链表两种基本的数据结构来实现。
在 操作系统 中常见的应用有：CPU 进程的调度、内存的分配、磁盘的管理。
队列的基本操作有：
1、入队。首先应检测队列中是否能插入元素，不能则不执行插入，能则在队尾插入一个元素。
2、出队。首先应当检测队列中是否有元素，无元素则无法读取，有元素则读取栈顶元素，并将其从队列中删除。
3、读取栈顶元素。同出队不同，该元素依旧保存在队首。
4、判断队列是否为空。
5、返回数组中的元素个数。
基于以上 5 个基本操作，分别用数组和链表来实现队列。
数组实现：
用 head、tail、count 分别代表队首、队尾、队列中的元素个数，在 QueueStudy 实例对象构造时将数组大小初始化。
class QueueStudy
{
private int[] queue ; // 数组队列
private int head; // 队首
private int tail; // 队尾
private int count; // 队列元素
public QueueStudy(int len)
{
queue = new int[len];
head = 0;
tail = 0;
count = 0;
}
public void push(int element)
{
if(tail== queue.length)
System.out.println("队列已满，无法入队");
else{
queue[tail++] = element;
count++;
}
}
public int pop()
{
if(tail== 0)
return -1 ; // 这里用 -1 代表无元素可出队
int num = queue[head++];
count--;
return num;
}
public int peek()
{
if(count == 0)
return -1 ; // 这里用 -1 代表队首无元素
return queue[head];
}
public Boolean isEmpty()
{
return count==0;
}
public int size()
{
return count;
}
}
链表实现
解释：链表队列的实现比数组链表稍微复杂，需要先定义一个链表，每次让 node 指向下一节点，head 始终指向首结点
class Node // 实现一个链表
{
private int element;
Node next;
public Node(int val,Node node)
{
this.element = val;
this.next = node;
}
public int getElement() // 读取链表结点数据
{
return element;
}
public void setElement(int val) // 修改链表结点数据
{
this.element = val;
}
}
public class ListQueue
{
Node node;
private Node head ;
private int count ;
public ListQueue(int value) // 初始化链表队列
{
count = 1;
node = new Node(value,null);
head = node;
}
public void push(int value)
{
node.next= new Node(value, null);
node = node.next;
count++;
}
public int pop()
{
if(head==null)
return -1;
int num = head.getElement();
head = head.next;
count--;
return num;
}
public int peek()
{
if(count==0)
return -1;
return head.getElement();
}
public Boolean isEmpty()
{
return count==0;
}
public int size()
{
return count;
}
}
循环队列
循环队列 是队列的特殊形式，队尾连着队首，在队列空间允许存、取的情况下，入队和出队的位置不固定。实际上就是用 count （队列元素个数）来判断队列是否允许入队、出队。
循环队列的进阶就是循环双端队列，队列的操作不再局限于在队首读取、在队尾插入。增加了队首插入、队尾读取 的操作。
可以尝试做一下 LeetCode 641. 设计循环双端队列
以下为实现代码参考
class MyCircularDeque {
private int[] nums; // 定义一个顺序队列，用数组来存储队列元素
private int count = 0; // count 来表示队列中当前存在的元素个数
private int head = 0; // head 表示队列的头
private int tail =0; // tail 表示队列的尾
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
nums = new int[k]; // 根据 k 来初始化数组的长度
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
if(count>=nums.length) return false; // 队列元素个数超出数组长度则无法再入队
if(head==0)
head=nums.length-1;
else
head-=1;
nums[head] = value; // 队列未满则将元素入队，尾指针以及数组元素 +1
count++;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
if(count>=nums.length) return false; // 队列元素个数超出数组长度则无法再入队
nums[tail++] = value; // 队列未满则将元素入队，尾指针以及数组元素 +1
count++;
tail = tail % nums.length;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
if(count==0) return false; // 队列为空则无法删除元素
head++;
head = head % nums.length; // 减少数组搬运操作直接将队列头移向下一元素
count--;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
if(count==0) return false; // 队列为空则无法删除元素
if(tail==0)
tail=nums.length-1; // 减少数组搬运操作直接将队列尾移向上一元素
else
tail-=1;
count--;
return true;
}
/** Get the front item from the deque. */
public int getFront() {
if(count==0) return -1;
return nums[head];
}
/** Get the last item from the deque. */
public int getRear() {
if(count==0) return -1;
if(tail==0) return nums[nums.length-1];
return nums[tail-1];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
return count==0;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
return count == nums.length;
}
}
用队列实现栈
需要用到两个 队列 或是一个 双端队列 实现。
入栈用 1 个队列来存储，出栈将队列 1 中的元素都出队到队列 2，此时队列 2 首的就是应该出栈的元素，将队列 2 队首出队并返回，剩下元素再出队回队列 2 则队列实现栈完成。
Java 代码实现如下
class MyStack {
private Deque <Integer> deque;
private Deque <Integer> tempDeque;
/** Initialize your data structure here. */
public MyStack() {
deque = new ArrayDeque<>();
}
/** Push element x onto stack. */
public void push(int x) {
deque.offer(x);
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
tempDeque = new ArrayDeque<>();
while(deque.size()!=0)
tempDeque.push(deque.pop());
int num = tempDeque.poll();
while(tempDeque.size()!=0)
deque.push(tempDeque.poll());
return num;
}
/** Get the top element. */
public int top() {
tempDeque = new ArrayDeque<>();
while(deque.size()!=0)
tempDeque.push(deque.poll());
int num = tempDeque.peek();
while(tempDeque.size()!=0)
deque.push(tempDeque.poll());
return num;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return deque.size()==0;
}
}
发表于 2019-3-17 20:11
|
发表于 2019-3-18 09:06
