什么是队列
队列(queue), 是一种运算受限的线性表(即线性结构, 一种数据逻辑结构, 分为顺序存储和链式存储两种).
其受限在于, 它不像链表那样可以在两端进行插入、删除操作, 仅允许在一端进行插入操作, 在另一端进行删除操作.
常见概念
队头: 队列中允许删除的一端称为队头.
队尾: 队列中允许插入的一端称为队尾.
入队: 向队列中插入元素称为入队.
出队: 从队列中删除元素称为出队.
队列的基本原则
队列遵循先进先出(First In First Out, FIFO)原则.
队列的常用操作
create 创建队列
isEmpty 判断队列是否为空
enqueue 入队
dequeue 出队
peek 返回队头元素
destroy 销毁队列
队列的实现分为顺序队列(基于数组实现)和链式队列(基于链表实现)两种.
PHP
<?php
class QueueDemo
{
private $queue;
private $size;
public function __construct($size = 5)
{
$this->queue = [];
$this->size = $size;
}
// 判断队列是否为空
public function isEmpty()
{
return empty($this->queue);
}
// 入队
public function enqueue($data)
{
if (count($this->queue) < $this->size) {
array_push($this->queue, $data);
} else {
throw new OverflowException('queue is overflow');
}
}
// 出队
public function dequeue()
{
if ($this->isEmpty()) {
throw new UnderflowException('queue is empty');
} else {
return array_shift($this->queue);
}
}
// 返回队头元素
public function peek()
{
if ($this->isEmpty()) {
throw new UnderflowException('queue is empty');
} else {
return current($this->queue);
}
}
}
// Test
$queue = new QueueDemo(3);
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
// bool(false)
var_dump($queue->isEmpty());
// int(1)
var_dump($queue->dequeue());
// int(2)
var_dump($queue->peek());
// int(2)
var_dump($queue->dequeue());
// int(3)
var_dump($queue->dequeue());
// bool(true)
var_dump($queue->isEmpty());JAVA
public class QueueDemo {
private Integer[] queue;
private Integer size;
// 队头
private Integer head;
// 队尾
private Integer end;
public QueueDemo(int initSize) {
queue = new Integer[initSize];
size = 0;
head = 0;
end = 0;
}
// 判断队列是否为空
public boolean isEmpty() {
if (size == 0) {
return true;
}
return false;
}
// 入队
public void enqueue(int data) {
if (size == queue.length) {
throw new ArrayIndexOutOfBoundsException("queue is overflow");
}
size++;
queue[end] = data;
end = end == queue.length - 1 ? 0 : end + 1;
}
// 出队
public Integer dequeue() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("queue is empty");
}
size--;
int tmp = queue[head];
head = head == queue.length - 1 ? 0 : head + 1;
return tmp;
}
// 返回队头元素
public Integer peek() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("queue is empty");
}
return queue[head];
}
public static void main(String[] args) {
QueueDemo queue = new QueueDemo(3);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
// false
System.out.println(queue.isEmpty());
// 1
System.out.println(queue.dequeue());
// 2
System.out.println(queue.peek());
// 2
System.out.println(queue.dequeue());
// 3
System.out.println(queue.dequeue());
// true
System.out.println(queue.isEmpty());
}
}PHP
<?php
// 节点
class Node
{
public $data = null;
public $next = null;
public function __construct($data)
{
$this->data = $data;
}
}
// 链式队列
class LinkedQueue
{
// 队头
private $head = null;
// 队尾
private $end = null;
// 队列的大小
private $size = 0;
// 判断队列是否为空
public function isEmpty()
{
return $this->size == 0;
}
// 入队
public function enqueue($data)
{
$node = new Node($data);
if ($this->head == null && $this->end == null) {
$this->head = $node;
$this->end = $node;
} else {
$this->end->next = $node;
$this->end = $node;
}
$this->size++;
}
// 出队
public function dequeue()
{
if ($this->size == 0) {
throw new UnderflowException('queue is empty');
}
$this->size--;
$tmp = $this->head->data;
$this->head = $this->head->next;
return $tmp;
}
// 返回队头元素
public function peek()
{
if ($this->isEmpty()) {
throw new UnderflowException('queue is empty');
}
return $this->head->data;
}
}
// Test
$queue = new LinkedQueue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
// bool(false)
var_dump($queue->isEmpty());
// int(1)
var_dump($queue->dequeue());
// int(2)
var_dump($queue->peek());
// int(2)
var_dump($queue->dequeue());
// int(3)
var_dump($queue->dequeue());
// bool(true)
var_dump($queue->isEmpty()