栈和队列是有操作限制的线性表。
1、队列的概念、特点、存储结构。
2、栈队列的 java 实现。
队列是一种在一端进行插入,而在另一端进行删除的线性表。
1、队列的插入端称为队尾;队列的删除端称为队头。(好比火车进隧道)
2、队列的插入操作称为入队(push),删除操作称为出队(pop)。
队列就像一列进入隧道的火车,隧道就是队列,火车车厢就是元素,进入隧道就是从隧道的这头(队尾)插入元素,出隧道就是从隧道的另一头(队头)删除元素。所以是 "先进先出" 的特点。
类似栈有顺序队和链式队两种。
2 状态:是否队空;是否队满。
2 操作:进队 push; 出队 pop。
顺序队列的实现也可以使用数组来完成,同栈的实现一样,只是栈是在同一端进行压栈和进栈操作,而队列是在一端做 push,另一端做 pop 操作。
可以看一下下面的队列操作示意图:
我们在实现顺序栈时使用头指针 "front" 和尾指针 "rear" 分别进行出队和入队操作,但普通的队列如上图所示,会发生 "假溢出" 现象,所以我们通常将数组弄成一个环状,即队头和队尾相连,这样就形成了 "循环队列",同时也解决了 "假溢出" 现象。循环队列是改进版的顺序队列。
如图:
对于普通队列的 push 或 pop 我们只需要对尾指针或头指针进行自增操作即可,但是循环队列我们就不能单纯的进行自增,当 front 或 rear=maxSize-1 时我们就不能进行自增操作了,比如一个队列尾长度为 4 的数组 datas[4],那么当 front 或 rear 需要在 0,1,2,3 之间进行循环 "推进",以此达到循环队列的效果。所以我们可以使用 rear = (rear+1)%maxSize ;front = (front+1)%maxSize ;公式进行指针计算。
需要注意的是:队空状态的条件为:front = rear。而如果整个队列全部存满数据那么,队满的条件也是 front = rear;所以循环队列需要损失一个存储空间,如下图:
如图所示:
链队的实现很简单,只要理解了链表的操作和队列的特点即可。
- package test;
- public class LinkQueue < T > {
- private QNode < T > front; //队头指针
- private QNode < T > rear; //队尾指针
- private int maxSize; //为了便于操作,使用这个变量表示链队的数据容量
- //初始化
- public LinkQueue() {
- this.front = new QNode < T > ();
- this.rear = new QNode < T > ();
- this.maxSize = 0;
- }
- //初始化队列
- public void initQueue() {
- front.next = null;
- rear.next = null;
- maxSize = 0;
- }
- //队空判断
- public boolean isNull() {
- if (front.next == null || rear.next == null) return true;
- else return false;
- }
- //进队
- public void push(QNode < T > node) {
- if (isNull()) {
- //第一次
- front.next = node;
- rear.next = node;
- maxSize++;
- } else {
- node.next = front.next;
- front.next = node;
- maxSize++;
- }
- }
- //出队
- public QNode < T > pop() {
- if (isNull()) return null; //队为空时,无法出队
- else if (maxSize == 1) {
- //队只有一个元素时直接初始化即可
- QNode < T > node = front.next;
- initQueue();
- return node;
- } else {
- //准备工作
- QNode < T > p = front; //使用p指针来遍历队列
- for (int i = 1; i < maxSize - 1; i++) p = p.next;
- //pop
- QNode < T > node = rear.next;
- rear.next = p.next;
- maxSize--;
- return node;
- }
- }
- }
- //链队结点
- class QNode < T > {
- private T data; //数据域
- public QNode < T > next; //指针域
- //初始化1
- public QNode() {
- this.data = null;
- this.next = null;
- }
- //初始化2
- public QNode(T data) {
- this.data = data;
- this.next = null;
- }
- public T getData() {
- return data;
- }
- public void setData(T data) {
- this.data = data;
- }
- }
测试:
- package test;
- import org.junit.Test;
- public class testQueue {
- @Test public void fun() {
- LinkQueue < Integer > lq = new LinkQueue < Integer > ();
- System.out.println("队列是否为空:" + lq.isNull());
- //依次插入1、2、3、4
- lq.push(new QNode < Integer > (1));
- lq.push(new QNode < Integer > (2));
- lq.push(new QNode < Integer > (3));
- lq.push(new QNode < Integer > (4));
- //依次出队
- System.out.println("依次出队:");
- while (!lq.isNull()) {
- System.out.println(lq.pop().getData());
- }
- }
- }
来源: https://www.cnblogs.com/fzz9/p/8159679.html