| 【数据结构Java版】Queue队列的活用 | 您所在的位置：网站首页 › 循环队列是一种 › 【数据结构Java版】Queue队列的活用 |
【数据结构Java版】Queue队列的活用
|
目录 一、队列的定义 二、队列的使用 （1）主要方法 （2）实例演示 （3）注意事项 三、队列的模拟实现 四、循环队列 （1）循环队列定义 （2）循环队列的表示 1.数组循环的方法 2.区分空满的方法 （3）循环队列的实现 五、双端队列 六、队列相关练习题 一、队列的定义队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front） 查看队头元素：peek 队列：java中，队列的含义被淡化了，队列使用Queue接口来表示。 java.util.Queue继承Collection(接口) 接口与类关系示意图：
 （3）注意事项
1.入队列：基本不会报错，返回true（当队列满时，入队列会出错。当我们使用LinkedList链表实现队列时。原则上人为链表是无限长，不会满。基本遇不到入队列错误。） 2.出队列：当返回值是null时，代表队列中没有元素。 3.查看队首元素：当返回值是null时，代表队列中没有元素。 三、队列的模拟实现 /* 元素类型是 long 类型 */ public class Queue { static class Node { long value; Node next; Node(long value) { this.value = value; this.next = null; } } // 为了方便头删 + 尾插，记录头节点 + 尾结点 private Node head; private Node last; private int size; public Queue() { this.head = this.last = null; this.size = 0; } public void offer(long e) { // 放入队列 -> 尾插 Node node = new Node(e); if (this.last != null) { this.last.next = node; this.last = node; } else { this.head = this.last = node; } this.size++; } public long poll() { if (size == 0) { throw new RuntimeException("队列是空的"); } // 记录当前队首元素 long e = this.head.value; // 进行头删 this.head = this.head.next; if (this.head == null) { this.last = null; } size--; return e; } public long peek() { if (size == 0) { throw new RuntimeException("队列是空的"); } return this.head.value; } public int size() { return this.size; } public boolean isEmpty() { return size() != 0; } } 四、循环队列 （1）循环队列定义为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。 假溢出：系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为"假溢出"。  （2）循环队列的表示
1.数组循环的方法
a. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
理论上解决的办法： 1. 通过添加 size 属性记 2. 保留一个位置 3. 使用标记 队满：rear+1=front 队空：rear=front
622. 设计循环队列 设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作： MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。示例： MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4 class MyCircularQueue { private int []array; private int size=0; private int frontIndex; private int rearIndex; public MyCircularQueue(int k) { array=new int[k]; } public boolean enQueue(int value) { if(isFull()){ return false; } array[rearIndex]=value; rearIndex=(rearIndex+1)%array.length; size++; return true; } public boolean deQueue() { if(isEmpty()){ return false; } frontIndex+=1; if(frontIndex==array.length){ frontIndex=0; } size--; return true; } public int Front() { if(isEmpty()){ return -1; } return array[frontIndex]; } public int Rear() { if(isEmpty()){ return -1; } int index=rearIndex; index=(rearIndex-1+array.length)%array.length; return array[index]; } public boolean isEmpty() { return size==0; } public boolean isFull() { return size==array.length; } }
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。Deque是一个接口，使用时必须创建LinkedList的对象。
225. 用队列实现栈 难度简单632 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。注意： 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。示例： 输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False class MyStack { private final Queue queue1=new LinkedList(); private final Queue queue2=new LinkedList(); private Queue 存元素的队列=queue1; private Queue 辅助队列=queue2; public MyStack() { } public void push(int x) { 存元素的队列.offer(x); } public int pop() { int size=存元素的队列.size(); for(int i=0;i |
b. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
【本文地址】