目录
一、队列的定义
二、列表的实现
三、LeetCode
1、Num225
2、Num225加强版
3、Num232
四、循环队列
五、双端队列
六、相关代码
一、队列的定义
队列是先进先出的数据结构(FIFO)，元素从队尾添加到队列，元素从队首出列（就类似于现实生活中的排队）
二、列表的实现
基于数组实现的队列-顺序队列，基于链表实现的队列-链式队列
对于队列来说，出队 *** 作只能在队列的头部 *** 作，如果是基于数组的话，那么每次出队一个元素就要搬移其他元素，就会比较麻烦，而基于链表的队列就不会这么麻烦
package queue.impl;
import queue.Queue;
import java.util.NoSuchElementException;
class Node{
E val;
Node next;
public Node(E val) {
this.val = val;
}
}
public class LinkedQueue implements Queue {
//当前队列的元素个数
private int size;
//头节点
private Node head;
//队尾元素
private Node tail;
/**
* 添加元素
* @param val
*/
@Override
public void offer(E val) {
Node node=new Node<>(val);
if (head==null){
head=tail=node;
}else {
tail.next=node;
tail=node;
}
size++;
}
/**
* d出队首元素
* @return
*/
@Override
public E poll() {
if (isEmptty()){
throw new NoSuchElementException("Queue is Empty!cannot is poll!");
}
E val= head.val;
Node node=head;
head=head.next;
node.next=node=null;
size--;
return val;
}
/**
* 查看队首元素
* @return
*/
@Override
public E peek() {
if (isEmptty()){
throw new NoSuchElementException("Queue is Empty!cannot is peek!");
}
return head.val;
}
/**
* 判断队列是否为空
* @return
*/
@Override
public boolean isEmptty() {
return size==0;
}
@Override
public String toString() {
StringBuilder sb=new StringBuilder();
sb.append("front [");
for (Node x=head;x!=null;x=x.next) {
sb.append(x.val);
if (x.next!=null){
sb.append(", ");
}
}
sb.append("] tail");
return sb.toString();
}
}
package queue.Leetcode;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
/**
* 双队列实现栈。q1和q2
* 其中q1永远是保存元素，栈的pop就是q1的poll，栈的peek就是q1的peek，栈的push就是q1的offer
* 当添加元素时，新元素入q2，然后让q1的元素一次d出入q2，最后交换q1和q2
*/
public class Num225 {
// q1永远是保存元素的队列
private Queue q1 = new LinkedList<>();
// q2作为辅助队列，新元素直接入q2
private Queue q2 = new LinkedList<>();
public void push(int x) {
// 新元素直接入q2
q2.offer(x);
// 将老元素依次出队1，入队2
while (!q1.isEmpty()) {
q2.offer(q1.poll());
}
// 交换q1和q2的名称
Queue temp = q1;
q1 = q2;
q2 = temp;
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
} 使用一个队列实现栈
package queue.Leetcode;
import java.util.LinkedList;
import java.util.Queue;
/**
* 使用一个队列实现栈
* 先记录当前的元素个数
* 将新元素入队
* 为了让新元素变为队首元素，就让新元素之前的左右元素都出列，此时新元素就是队首元素，再依次入队
*/
public class Num225Plus {
private Queue queue=new LinkedList<>();
public void push(int x) {
//记录当前队列的元素个数
int size=queue.size();
queue.offer(x);
for (int i = 0; i package queue.Leetcode;
import java.util.Stack;
public class Num232 {
// s1永远是保存元素的栈，就对应队列
private Stack s1 = new Stack<>();
// s2作为辅助，s1的栈顶元素就会d出压入s2的栈底 => 交换顺序
private Stack s2 = new Stack<>();
public void push(int x) {
// 1.先让s1的所有元素d出压入s2中，交换先后顺序
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
// 2.s1为空，新元素直接入s1，就变为了栈底元素，就是队尾
s1.push(x);
// 3.再把s2中的所有元素依次d回s1
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
public int pop() {
return s1.pop();
}
public int peek() {
return s1.peek();
}
public boolean empty() {
return s1.isEmpty();
}
}
循环队列基本是使用长度固定的数组来实现，数组在实现队列时，若从数组头部删除元素需要频繁的移动到后面的元素带来的效率很低
出队和入队 *** 作，使用head和tail引用，添加元素在尾部添加，删除元素就只需要移动head引用指向的地址（逻辑上删除），数组优先元素是[head,tail)
package queue.impl;
import queue.Queue;
import java.util.NoSuchElementException;
/**
* 基于整型循环队列
*/
public class LoopQueue implements Queue {
//长度固定的数组
private Integer[] data;
//队首元素
private int head;
//指向队尾元素的下一个索引
private int tail;
/**
* 保存最大元素个数size个，那么数组长度就要再加1
* @param size
*/
public LoopQueue(int size){
//因为循环队列需要浪费一个空间来判断队列是否已满
data=new Integer[size+1];
}
@Override
public void offer(Integer val) {
if (isFull()){
throw new ArrayIndexOutOfBoundsException("LoopQueue is full!cannot offer");
}
data[tail]=val;
tail=(tail+1)% data.length;
}
@Override
public Integer poll() {
if (isEmptty()){
throw new NoSuchElementException("LoopQueue is empty!cannot poll!");
}
//移动队首元素
Integer val=data[head];
head=(head+1)% data.length;
return val;
}
@Override
public Integer peek() {
if (isEmptty()){
throw new NoSuchElementException("LoopQueue is empty!cannot peek!");
}
return data[head];
}
/**
* 判断数组是否为空
* @return
*/
@Override
public boolean isEmptty() {
return head==tail;
}
/**
* 判断队列是否已满
* @return
*/
public boolean isFull(){
return (tail+1)% data.length==head;
}
/**
* 注意判断最后一个元素的索引
* 当tail==0时，就是data.length-1
* 当tail在其他位置时，就是tail-1
* 此时使用三目运算符来实现
* @return
*/
@Override
public String toString() {
StringBuilder sb=new StringBuilder();
sb.append("front [");
int lastIndex=tail==0? data.length -1:tail-1;
for (int i = head; i < tail;) {
sb.append(data[i]);
if(i !=lastIndex){
sb.append("， ");
}
i=(i+1)% data.length;
}
sb.append("] tail");
return sb.toString();
}
}
Deque->时 Queue的子接口
这个队列既可以尾插，头出
也可以头插，尾出
在以后的使用中，如果需要栈或者队列，统一使用双端队列，效率高
//此时需要的是栈
Deque stack=new LinkedList<>();
stack.add(1);
stack.add(2);
stack.add(3);
stack.add(4);
System.out.println(stack);
stack.poll();
System.out.println(stack);
//此时需要的是队列
Deque queue=new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
System.out.println(queue);
queue.poll();
System.out.println(queue); 任枭雄/rocket_class_ds - Gitee.comhttps://gitee.com/ren-xiaoxiong/rocket_class_ds/tree/master/src/queue
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）