【数据结构与算法】7.详解队列的基本操作

2024-05-07 17:32:17 浏览数 (1)

1. 队列

1.1 队列的概念

像栈一样，队列也是表。然而，使用队列是插入在一端进行而删除则在另一端进行。

队列的基本操作的是入队，它是在表的末端（队尾）插入一个元素，和出队，它是删除（并返回）表的开头元素。

1.2 队列的使用

方法

功能

boolean offer(E e)

入队列

E poll()

出队列

peek()

获取队头元素

int size()

获取队列中有效元素个数

boolean isEmpty()

检测队列是否为空

2. 模拟实现

定义双向链表类

代码语言：javascript复制
	static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

定义两个指针，分别指向头节点和尾节点

代码语言：javascript复制
    public ListNode head;
    public ListNode last;

入队（offer）

判断队列是否为空，如果为空，将新节点设置为头节点，将新节点设置为尾节点

代码语言：javascript复制
head = last = node;

如果队列不为空，将最后一个节点last的next域指向新节点，新节点的prev域指向最后一个节点，更新尾节点为新节点

代码语言：javascript复制
last.next = node;
node.prev = last;
last = node;

代码：

代码语言：javascript复制
    /**
     * 入队
     * @param val
     */
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

出队（poll）

判断队列是否为空，如果为空则抛出异常

代码语言：javascript复制
if (head == null) {
	throw new RuntimeException("队列为空");
}

如果队列只有一个元素，则移除该元素并返回该元素，同时将head和last置为空，返回移除元素的值

代码语言：javascript复制
// 链表中只有一个元素
int val = head.val;
if (head == last) {
    head = null;
    last = null;
    return val;
}

如果队列有多个元素，则移除头元素并返回该元素的值，将头节点指向头节点的下一个节点，将头节点的prev置为空，返回移除元素的值

代码语言：javascript复制
head = head.next;
head.prev = null;
return val;

代码：

代码语言：javascript复制
    /**
     * 出队
     */
    public int poll() {
        // 判断链表中是否有元素
        if (head == null) {
            throw new RuntimeException("队列为空");
        }
        // 链表中只有一个元素
        int val = head.val;
        if (head == last) {
            head = null;
            last = null;
            return val;
        }
        head = head.next;
        head.prev = null;
        return val;
    }

获取队头元素（peek）

判断队列是否为空，如果为空，则抛出异常

代码语言：javascript复制
if (head == null) {
	throw new RuntimeException("队列为空");
}

如果不为空，则返回队头元素的值

代码语言：javascript复制
return head.val;

代码：

代码语言：javascript复制
    /**
     * 获取队头元素
     * @return
     */
    public int peek() {
        if (head == null) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }

获取队列中有效元素个数

遍历队列计算元素个数并返回

代码：

代码语言：javascript复制
    /**
     * 获取队列有效元素个数
     * @return
     */
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count  ;
            cur = cur.next;
        }
        return count;
    }

检测队列是否为空

判断队列的头节点是否为空，如果为空，则队列为空

代码语言：javascript复制
    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return head == null;
    }

3.完整代码

MyQueue类：

代码语言：javascript复制
public class MyQueue {

    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;

    /**
     * 入队
     * @param val
     */
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

    /**
     * 出队
     */
    public int poll() {
        // 判断链表中是否有元素
        if (head == null) {
            throw new RuntimeException("队列为空");
        }
        // 链表中只有一个元素
        int val = head.val;
        if (head == last) {
            head = null;
            last = null;
            return val;
        }
        head = head.next;
        head.prev = null;
        return val;
    }

    /**
     * 获取队头元素
     * @return
     */
    public int peek() {
        if (head == null) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }

    /**
     * 获取队列有效元素个数
     * @return
     */
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count  ;
            cur = cur.next;
        }
        return count;
    }
    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return head == null;
    }
}

异常类：

代码语言：javascript复制
public class EmptyQueueException extends RuntimeException{
    public EmptyQueueException() {
    }

    public EmptyQueueException(String message) {
        super(message);
    }
}
异常 public 队列 链表 数据结构与算法

0 人点赞