• 数据结构之队列

    1. 什么是队列❓

    排队买票的队伍，就是一个队列。先来的先买，后来的只能站末尾，不能插队。
    特点：先进者先出
    同栈一样，是一种操作受限的线性表数据结构

    2. 何时使用队列❓

    例：当我们向一个固定大小的线程池请求一个线程时，此时线程池没有资源，但是我们又不想拒绝掉这次请求，这时候就会用到队列。
    具体策略：将请求排队，等到有空闲线程时，取出排队的请求继续处理。

    3. 队列的关键操作

    • 入队enqueue()：放一个数据到队列尾部
    • 出队dequeue()：从队列头部取一个元素

    4. 队列的种类

    • 按实现方式分为：顺序队列(用数组实现)和链式队列(用链表实现)
    • 按队列结构分为：一般队列、循环队列、阻塞队列、并发队列等

    5. 一般队列的实现

    5.1 顺序队列

    需要用到两个指针，一个是队头head，一个是队尾tail
    关键：数据搬移(为了重新利用起之前申请到的空间)

    Java代码：

    public class ArrayQueue {
    // 数组：items，数组大小：n
    private String[] items;
    private int n = 0;
    // head表示队头下标，tail表示队尾下标
    private int head = 0;
    private int tail = 0;
    // 申请一个大小为capacity的数组
    public ArrayQueue(int capacity){
        items = new String[capacity];
        n = capacity;
    }
    // 入队
    public boolean enqueue(String item){
        if (tail == n){
            if (head == 0) return false;
            // 数据搬运
            for (int i = head; i < tail; ++ i)
            {
                items[i - head] = items[i];
            }
            tail = tail - head;
            head = 0;
        }
        items[tail] = item;
        ++ tail;
        return true;
    }
    // 出队
    public String dequeue(){
        if (head == tail) return null; // 队头指针与队尾指针相等，表示队列为空
        String ret = items[head];
        ++ head;
        return ret;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    C++代码：

    #include <iostream>
#include <string>
using namespace std;
class ArrayQueue
{
	public:
		ArrayQueue(int capacity); // 申请数组 
		bool enqueue(string item); // 入队 
		string dequeue(); // 出队 
	private:
		int n;
		string* items;
		int head = 0;
		int tail = 0;
}; 
ArrayQueue::ArrayQueue(int capacity){
	items = new string[capacity];
	n = capacity;
}
bool ArrayQueue::enqueue(string item){
	if (tail == n) {
		if (head == 0) return false; // 队满
		for (int i = head; i < tail; ++ i){ // 数据搬运 
			items[i - head] = items[i]; 
		} 
		tail = tail - head;
		head = 0;
	} 
	items[tail] = item;
	++ tail;
	return true;
}
string ArrayQueue::dequeue(){
	if (head == tail) return "This queue is empty!";
	string ret = items[head];
	++ head;
	return ret;
} 
int main(void)
{
	ArrayQueue myQueue(3);
	myQueue.enqueue("zhangsan");
	myQueue.enqueue("lisi");
	myQueue.enqueue("wangwu");
	cout << "插入第四个元素结果：" <<myQueue.enqueue("add") << endl; // 多插一个测试失败结果
	for (int i = 0; i < 4; ++ i){
		cout << myQueue.dequeue() << endl;
	} 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    Python代码：

    from typing import Optional
class ArrayQueue:
    def __init__(self, capacity: int):
        self.__items = [0 for i in range(capacity)]
        self.__n = capacity
        self.__head = 0
        self.__tail = 0
    def enqueue(self, item: str) -> bool:
        if self.__tail == self.__n:
            if self.__head == 0: # 队列已满 
                return False
            # 充分利用空间，进行数据搬运
            for i in range(self.__head, self.__tail):
                self.__items[i - self.__head] = self.__items[i]
            self.__tail = self.__tail - self.__head
            self.__head = 0
        self.__items[self.__tail] = item
        self.__tail = self.__tail + 1
        return True
    def dequeue(self) -> Optional[str]:
        if (self.__head == self.__tail): 
            return None
        item = self.__items[self.__head]
        self.__head = self.__head + 1
        return item

q = ArrayQueue(3)
q.enqueue(3)
q.enqueue(2)
q.enqueue(1)
print(q.enqueue(0)) # 数量上限，故插入失败
print(q.dequeue()) # 将元素3弹出，给元素0腾位置
print(q.enqueue(0))
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue()) # 队列为空情况

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    5.2 链式队列

    两个指针：head指向链表的第一个结点，tail指向链表的最后一个结点
    关键：入队时tail->next = new_node, tail = tail->next；出队时head = head->next

    Java代码：

    public class LinkedListQueue {
    private Node head = null;
    private Node tail = null;
    private int n = 0;
    private int capacity = 0;

    public LinkedListQueue(int capacity){
        this.n = capacity;
    }
    // 入队
    public boolean enqueue(String item){
        if (capacity == n) return false;
        Node node = new Node(item, null);
        if (capacity == 0){
            tail = node;
            head = node;
        }
        else {
            tail.setNext(node);
            tail = tail.getNext();
        }
        ++capacity;
        return true;
    }
    // 出队
    public String dequeue(){
        if (head != null)
        {
            --capacity;
            String ret = head.getData();
            head = head.getNext();
            return ret;
        }else return null;
    }



    private class Node{
        private String data;
        private Node next;
        public Node(String data, Node next){
            this.data = data;
            this.next = next;
        }

        public void setNext(Node next){
            this.next = next;
        }

        public String getData(){
            return data;
        }
        public Node getNext(){
            return next;
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    C++代码：

    #include <iostream>
#include <string>
using namespace std;

struct Node
{
	Node* next;
	string data;
	Node(string data){
		this->data = data;
		this->next = NULL;
	}
};

struct LinkedListQueue
{
	Node* head;
	Node* tail;
	int n;
	int capacity;
	LinkedListQueue(int capacity)
	{
		this->n = capacity;
		this->capacity = 0; 
		head = NULL;
		tail = NULL;
	};
	bool enqueue(string item){
		if (capacity == n) return false;
		Node* node = new Node(item);
		if (capacity == 0){
			tail = node;
			head = node;
		}else{
			tail->next = node;
			tail = tail->next;
		}
		++capacity;
		return true;
	}; 
	string dequeue(){
		if (head == NULL)
		{
			return "This queue is empty!"; 
		}
		else
		{
			--capacity;
			string ret = head->data;
			head = head->next;
			return ret;
		}
	}
};


int main(void)
{
	LinkedListQueue* myQueue = new LinkedListQueue(3);
	myQueue->enqueue("zhangsan");
	myQueue->enqueue("lisi");
	myQueue->enqueue("wangwu");
	cout << myQueue->enqueue("add") << endl; // 多加一个 
	for (int i = 0; i < 3; ++ i) cout << myQueue->dequeue() << endl;
	cout << myQueue->dequeue() << endl;
	cout << myQueue->enqueue("add") << endl; 
	cout << myQueue->dequeue() << endl;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    Python代码：

    from typing import Optional
class Node:
    def __init__(self, data: str):
        self.__data = data
        self.__next = None
    def setNext(self, next):
        self.__next = next
    def getNext(self):
        return self.__next
    def setData(self, data: str):
        self.__data = data
    def getData(self) -> str:
        return self.__data

class LinkedListQueue:
    def __init__(self, capacity: int):
        self.__n = capacity
        self.__capacity = 0
        self.__head = None
        self.__tail = None
    def enqueue(self, item: str) -> bool:
        if self.__capacity == self.__n:
            return False
        node = Node(item)
        if self.__capacity == 0: # 队列为空
            self.__tail = node
            self.__head = node
        else:
            self.__tail.setNext(node)
            self.__tail = self.__tail.getNext()
        self.__capacity = self.__capacity + 1
        return True
    def dequeue(self) -> Optional[str]:
        if self.__capacity == 0:
            return None
        else:
            data = self.__head.getData()
            self.__head = self.__head.getNext()
            self.__capacity = self.__capacity - 1
            return data

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    6. 循环队列

    循环队列
    图源：王争 数据结构与算法之美

    好处：免去了在使用数组实现队列时，当tail==n时的数据搬移操作，提高了入队操作性能
    实现难点：队空(head = tail)和队满判断条件((tail+1)%n = head)
    小小缺点：当队列满时，tail指向的位置实际上没有存储数据，会浪费一个存储空间

    Java代码：

    public class CircularQueue {
    private String []items;
    private int n = 0;
    private int head = 0;
    private int tail = 0;
    public CircularQueue(int capacity){
        items = new String[capacity];
        n = capacity;
    }
    // 入队
    public boolean enqueue(String item){
        if ((tail + 1) % n == head) return false;
        items[tail] = item;
        tail = (tail + 1) % n;
        return true;
    }
    // 出队
    public String dequeue(){
        if (head == tail) return null; // 队列为空
        String ret = items[head];
        head = (head + 1) % n;
        return ret;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    C++代码：

    #include <iostream>
#include <string>

using namespace std;
class CircularQueue
{
	public:
		CircularQueue(int capacity);
		bool enqueue(string item);
		string dequeue();
	private:
		int n;
		string* items;
		int head = 0;
		int tail = 0;
}; 
CircularQueue::CircularQueue(int capacity){
	items = new string[capacity];
	n = capacity;
} 
bool CircularQueue::enqueue(string item){ 
	if ((tail + 1) % n == head) return false; // 队满
	items[tail] = item;
	tail = (tail + 1) % n;
	return true; 
}
string CircularQueue::dequeue(){
	if (head == tail) return "This queue is empty!";
	string ret = items[head];
	head = (head + 1) % n;
	return ret;
}



int main(void)
{
	CircularQueue myQueue(3);
 	myQueue.enqueue("zhangsan");
 	myQueue.enqueue("lisi");
 	cout << myQueue.enqueue("wangwu") << endl;
 	for (int i = 0; i < 3; ++ i){
 		cout << myQueue.dequeue() << endl;
 	} 
	cout << myQueue.enqueue("add") << endl;
	cout << myQueue.dequeue() << endl;
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    Python代码：

    from typing import Optional
class CircularQueue:
    def __init__(self, capacity: int):
        self.__items = [0 for i in range(capacity)]
        self.__n = capacity
        self.__head = 0
        self.__tail = 0
    def enqueue(self, item: str) -> bool:
        if (self.__tail + 1) % self.__n == self.__head:  # 队满
            return False
        self.__items[self.__tail] = item
        self.__tail = (self.__tail + 1) % self.__n
        return True
    def dequeue(self) -> Optional[str]:
        if self.__head == self.__tail:
            return None
        ret = self.__items[self.__head]
        self.__head = (self.__head + 1) % self.__n
        return ret

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    7. 其他

    • 阻塞队列：队列为空时，取数据的操作会被阻塞，队列满时，插入数据的操作会被阻塞。可以用于实现生产者-消费者模型
    • 并发队列：一种线程安全的队列

    8. END

    愿我们都有诗和远方 😀

    诗和远方

  • 相关阅读:
    stm32f103开发板入门到手进行开发
    代码随想录算法训练营第57天 | 647. 回文子串 516.最长回文子序列 dp总结
    《InnoDB引擎七》InnoDB关键特性-插入缓存
    java毕业生设计疫情防控医用品管理计算机源码+系统+mysql+调试部署+lw
    LLM大模型训练和预测如何计算算力需求？
    信号与进程间通信
    年产200万件的超级工厂投产！巨头「闭环」汽车电子全产业链
    SpringCloud微服务电商系统在Kubernetes集群中上线详细教程
    【最有效】解决anaconda的虚拟环境重复目录问题
    [python 刷题] 437 Path Sum III
  • 原文地址：https://blog.csdn.net/weixin_48842132/article/details/125450270