什么是队列?
2020-02-13 16:02:15来源:博客园 阅读 ()
什么是队列?
与前面提到的数据结构相同,队列中的数据也呈线性排列。虽然与栈有些相似,但队列中添加和删除数据的操作分别是在两端进行的,就和队列这个名字一样,把它想象成排成一队的人更容易理解。在队列中,处理总是从第一名开始往后进行,而新来的人只能排在队尾。
队列是什么?
如上就是队列的概念图,现在队列中只有数据 Blue。往队列中添加数据时,数据被加在最上面。
然后,队列中添加了数据 Green。往队列中添加数据的操作叫作入队。
紧接着,数据 Red 也入队了。
从队列中取出(删除)数据时,是从最下面,也就是最早入队的数据开始的,即 Blue。从队列中删除数据的操作叫作出队。
如果再进行一次出队操作,取出的就是 Green 了。
像队列这种最先进去的数据最先被取来,即先进先出的结构,我们称为 First In First Out,简称 FIFO。
与栈类似,队列中可以操作数据的位置也有一定的限制。在栈中,数据的添加和删除都在同一端进行,而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据,必须通过出队操作将目标数据变成首位后才能访问。
介绍完队列的基本知识后,接下来举一个例子,比如生活中常见的排队买票。
如何理解队列?
队列这个概念非常好理解,你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队,先进者先出,这就是典型的队列。
上一篇讲到栈只支持两个基本操作:入栈和出栈。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队,放一个数据到队列尾部;出队,从队列头部取一个元素。
所以,队列跟栈一样,也是一种操作受限的线性表数据结构,队列的概念很好理解,基本操作也很容易掌握。作为一种非常基础的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。
队列的实现
看到这里,相信你已经对队列有了初步的理解,队列主要包含两个操作,入队和出队。光理解还不够,我们还要动手去实现队列,接下来让我们来看一看如何用代码实现一个队列。
跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。
首先来看下用数组实现的队列是怎么样的,其实现如下图所示:
那么我先用 Java 语言来实现下顺序队列,代码如下:
/**
* 基于数组实现的顺序队列
*
* @author wupx
* @date 2020/02/13
*/
public class ArrayQueue {
private String[] items;
/**
* 数组大小
*/
private int n = 0;
/**
* 队头下标
*/
private int head = 0;
/**
* 队尾下标
*/
private int tail = 0;
/**
* 申请一个大小为 capacity 的数组
*
* @param capacity
*/
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
/**
* 入队
*
* @param item
* @return
*/
public boolean enqueue(String item) {
// 如果 tail == n 表示队列已经满了
if (tail == n) {
return false;
}
items[tail] = item;
++tail;
return true;
}
/**
* 出队
*
* @return
*/
public String dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) {
return null;
}
String ret = items[head];
++head;
return ret;
}
}
另外一种就是链式队列,它的实现如下图所示:
再用链表去实现队列,代码如下:
/**
* 基于链表实现的链式队列
*
* @author wupx
* @date 2020/02/13
*/
public class LinkedListQueue {
/**
* 队头
*/
private Node head = null;
/**
* 队尾
*/
private Node tail = null;
/**
* 入队
*
* @param value
*/
public void enqueue(String value) {
if (tail == null) {
Node newNode = new Node(value, null);
head = newNode;
tail = newNode;
} else {
tail.next = new Node(value, null);
tail = tail.next;
}
}
/**
* 出队
*
* @return
*/
public String dequeue() {
if (head == null) {
return null;
}
String value = head.data;
head = head.next;
if (head == null) {
tail = null;
}
return value;
}
public void printAll() {
Node p = head;
while (p != null) {
System.out.print(p.data + " ");
p = p.next;
}
System.out.println();
}
private static class Node {
private String data;
private Node next;
public Node(String data, Node next) {
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
}
}
到此,我们就分别实现了基于数组和链表的队列,大家可以自己实现下。
队列还有很多扩展,比如循环队列、阻塞队列、并发队列等,将在以后的文章中进行介绍。
总结
这篇主要讲了一种跟栈很相似的数据结构-队列,也是一种线性逻辑结构。
队列遵循先进先出(FIFO)的原则,主要的两个操作是入队和出队。队列既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。
参考
《我的第一本算法书》
原文链接:https://www.cnblogs.com/wupeixuan/p/12302040.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 5月到6月程序员到底经历了和什么,工资狂跌***元,你是否也 2020-06-10
- 为什么阿里巴巴Java开发手册中不允许魔法值出现在代码中? 2020-06-09
- 一口气说出 6种 延时队列的实现方案,面试稳稳的 2020-06-08
- 计算机基础到底是哪些基础?为什么很重要! 2020-06-08
- 为什么阿里巴巴Java开发手册中强制要求接口返回值不允许使用 2020-06-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash