队列的定义

  • 队列,又称为伫列(queue),计算机科学中的一种抽象资料型别,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。

数据队列

  • 通过数组实现队列可以,提高效率

  • 变量介绍

    • q[N] -> 模拟队列空间
    • hh -> 指向队列的头部
    • tt -> 指向队列的尾部
  • 队列的操作

    • 定义队列
      • image.png
      • 
        	const int N = 100005;
        	int q[N], hh, tt;
        	// 初始化队列为空
        	init() {
        		hh = 0;
        		tt = -1;
        	}
        
    • 向队尾中添加一个元素
      • image.png
      • 	push(int x) {
        		q[++ tt] = x; // 更新 队尾指针,向队尾插入一个元素
        	}
        
    • 从队头取出一个元素
      • image.png
      • 
        	int pop() {
        		return q[hh ++]; // 弹出队头,并更新 队头指针
        	}
        
    • 判断队列是否为空
      • 	bool empty() {
        		return hh < tt ? true:false;
        	}
        
    • 返回队列中元素个数
      • 	int size() {
        		return tt - hh + 1;
        	}
        

循环队列

  • 通过循环公式,将队列设置为逻辑上的环状队列, 浪费一个空间使得循环队列更好的判断,是否为空,和队列是否满了

  • image.png

循环队列的操作

  • 循环队列定义

    • 		const int N = 7;
      		int hh, tt;
      		int q[N];
      		// 初始化
      		init() {
      			hh = 0, tt = 0;
      		}
      
  • 向循环队列添加一个元素

    • 		push(int x) {
      			if ((tt + 1) % N != hh) {
      				q[tt] = x;
      				tt = (tt + 1) % N;
      			}
      
      		}
      
  • 从队头取出一个元素

    • 		int pop() {
      			if (tt != hh) {
      				int x = q[hh];
      				hh = (hh + 1) % N;
      				return x;
      			}
      			return -1;
      		}
      
      
  • 判断队列是否为空

    • 
      		bool empty() {
      			return tt == hh ? true:false;
      		}
      
  • 获得队列元素个数

    • 		int size() {
      			return (tt - hh + N) % N;
      		}
      
      
  • 综合

    • 	#include <iostream>
      	using namespace std;
      
      	const int N = 10;
      	int q[N], hh = 0, tt = 0;
      
      	void push(int x) {
      		if ((tt + 1) % N != hh) {
      			q[tt] = x;
      			tt = (tt + 1) % N;
      		}
      
      	}
      	int pop() {
      		if (tt != hh) {
      			int x = q[hh];
      			hh = (hh + 1) % N;
      			return x;
      		}
      		return -1;
      	}
      
      	bool empty() {
      		return tt == hh ? true:false;
      	}
      
      	int size() {
      		return (tt - hh + N) % N;
      	}
      
      	int main() {
      		for (int i = 0; i < 10; ++ i) {
        		push(i);
      		}
      
      		printf("size=%d\n", size());
      
      		while (!empty()) {
        		printf("%d ", pop());
      		}
      		return 0;
      
      	}