博客

目录

一、认识队列

二、队列的基本操作

1. 定义基本的队列并初始化队列

2. 入队列

3. 出队列

4. 获取队头元素

一、认识队列

队列是一种从一边插入数据另一边删除数据的线性数据结构，在我们生活中队列十分常见，比如在学校排队买饭，这就是一个基本队列，第一个排队的人排在队头先买到饭并且先离开排队队列，所以队列具有先进先出（FIFO）的特性。

与栈不同的是，队列的底层没有数组，而是通过链表实现的。下面我们通过代码来了解队列的基本实现。

二、队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给X。

1. 定义基本的队列并初始化队列

public class MyQueue {
    public static class Queue{
        public LinkedList.ListNode prev;
        public LinkedList.ListNode next;
        int val;
        void ListNode(int val){
            this.val = val;
        }
    }
    LinkedList.ListNode first;
    LinkedList.ListNode last;
}

2. 入队列

public void offer(int e){
        LinkedList.ListNode newNode = new LinkedList.ListNode(e);
        if(first == null){
            first = newNode;
            // last = newNode;
        }else{
            last.next = newNode;
            newNode.prev = last;
            // last = newNode;
        }
        last = newNode;
        size++;
    }

3. 出队列

public int poll(){

        int value = 0;
        if(first == null){
            return -1;
        }else if(first == last){
            last = null;
            first = null;
        }else{
            value = first.val;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }

4. 获取队头元素

public int peek(){
        if(first == null){
            return -1;
        }
        return first.val;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }

public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5); // 从队尾入队列
        System.out.println(q.size());
        System.out.println(q.peek()); // 获取队头元素
        q.poll();
        System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
        if(q.isEmpty()){
            System.out.println("队列空");
        }else{
            System.out.println(q.size());
        }
    }