数据结构 模拟实现Queue队列（双链表模拟）
目录
一、队列的概念
类似我们现实生活中的在食堂排队打饭，排队靠前的先打饭，他为什么排队靠前呢，就是因为他先进行排队，名次靠前，才轮到他打饭，如图：
而队列是先进先出的数据结构，先放进去队列里的元素先出来，和栈的先进后出不同，类似上面的食堂排队打饭的例子。
我们自定义一个MyQueue类，里面有双向链表ListNode类，链表里面有存放数据的val变量，next域和prev域，记录头结点的head和尾节点的last，还有记录链表元素个数的usedSize，代码如下：
public class MyQueue implements IQueue{
class ListNode {
public int value;
public ListNode prev;
public ListNode next;
public ListNode(int value) {
this.value = value;
}
}
ListNode head;
ListNode last;
int usedSize;
}二、队列的接口
代码如下：
public interface IQueue {
public boolean offer(int x);
public int poll();
public int peek();
public int size();
public boolean isEmpty();
}三、队列的方法实现
（1）offer方法
此方法是入队列方法，首先要创建一个链表node，判断链表中为不为空，如果是空，就把head和last定义成node，usedSize++；如果不为空，就要尾差，把last.next变成node，node.prev变成last，最后再把last = node，usedSize++，代码如下：
public boolean offer(int x) {
ListNode node = new ListNode(x);
if(head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = last.next;
}
usedSize++;
return true;
}执行效果如下：
队列个数usedSize = 2，链表有两个节点。
（2）poll方法
此方法是出队列方法，首先判断链表是不是空，如果是空就出不了队列，抛异常；如果不为空，就判断head.next为不为空，也就是判断队列是不是只有一个元素，如果只有一个元素，就取出头结点的val值，再把head和last置为空，usedSize--；如果有多个元素，就取出头结点的val值，把头结点的next置为空，头结点往后走一步，头结点的prev置空，usedSize--。代码如下：
public int poll() {
if(head == null) {
//队列为空，出不了队列，抛异常
throw new EmptyException("队列为空");
}
if(head.next == null) {
int retValue = head.value;
last = null;
head = null;
usedSize--;
return retValue;
}
int retValue = head.value;
ListNode nodeNext = this.head.next;
head.next = null;
nodeNext.prev = null;
head = nodeNext;
usedSize--;
return retValue;
}
//自定义异常类
public class EmptyException extends RuntimeException{
public EmptyException(String msg) {
super(msg);
}
}执行效果如下：
出队列三次，把队列出完，如果里面没元素了，就会抛异常。
（3）peek方法
此方法是取出队列的首元素，但不删除。首先要判断队列是不是空的，是空的就抛异常，不为空就返回队首元素val值，代码如下：
public int peek() {
if(head == null) {
//队列为空，出不了队列，抛异常
throw new EmptyException("队列为空");
} else {
int retValue = head.value;
return retValue;
}
}
//自定义异常类
public class EmptyException extends RuntimeException{
public EmptyException(String msg) {
super(msg);
}
}执行效果如下：
只拿队列首元素，不出队列。
（4）size方法
直接返回usedSize，代码如下：
public int size() {
return usedSize;
}执行效果如下：
返回队列元素的个数。
（5）isEmpty方法
直接返回head == null，代码如下：
public boolean isEmpty() {
return this.head == null;
}执行效果如下：
判断队列是否为空。
四、最终代码
//自定义接口
public interface IQueue {
public boolean offer(int x);
public int poll();
public int peek();
public int size();
public boolean isEmpty();
}
//MyQueue类
public class MyQueue implements IQueue{
class ListNode {
public int value;
public ListNode prev;
public ListNode next;
public ListNode(int value) {
this.value = value;
}
}
ListNode head;
ListNode last;
int usedSize;
@Override
public boolean offer(int x) {
ListNode node = new ListNode(x);
if(head == null) {
head = node;
last = node;
} else {
last.next = node;
node.prev = last;
last = last.next;
}
usedSize++;
return true;
}
@Override
public int poll() {
if(head == null) {
//队列为空，出不了队列，抛异常
throw new EmptyException("队列为空");
}
if(head.next == null) {
int retValue = head.value;
last = null;
head = null;
usedSize--;
return retValue;
}
int retValue = head.value;
ListNode nodeNext = this.head.next;
head.next = null;
nodeNext.prev = null;
head = nodeNext;
usedSize--;
return retValue;
}
@Override
public int peek() {
if(head == null) {
//队列为空，出不了队列，抛异常
throw new EmptyException("队列为空");
} else {
int retValue = head.value;
return retValue;
}
}
@Override
public int size() {
return usedSize;
}
@Override
public boolean isEmpty() {
return this.head == null;
}
}
//自定义异常类
public class EmptyException extends RuntimeException{
public EmptyException(String msg) {
super(msg);
}
}都看到这了，点个赞再走吧，谢谢谢谢谢！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！