队列的一些说明
队列的定义
队列,一种特殊的线性表
特点:只允许在一端输入,在另一端输出。输入端称为队尾,输出端称为队头
因此,队列,又称为先进先出表(FIFO),类似于生活中的排队,先来的排在前头,后来的排在后头,一个一个办理业务。
队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。
这一篇讲的是链式队列,循环队列在另外一篇文章中
循环队列讲解与C语言实现
链式队列的实现
链式队列
链式队列与单链表是有些类似的,只是多了一个表头(front)和一个表尾(rear)。
front指向首结点,rear指向尾结点,如图所示:
具体实现
**具体实现的话,下面有两种。一种是用C++的类进行实现的,一种是直接调用C++的模板即可。**一般使用肯定是直接调用容器的,这里是为了熟悉队列。
C++代码实现
#include<iostream> using namespace std; //链式队列 struct Node{ int data; Node *next; Node(int x){ data = x; next = NULL; } }; class Queue{ //定义队列的类 private: Node *front; //首结点 Node *rear; //尾结点 public: Queue(){ front = rear = NULL; //初始化 } ~Queue(){ //析构函数做一个delete Node *tmp; while(front){ tmp = front; front = front->next; delete tmp; } } bool isEmpty(){ //判断是否为空 return front == NULL; } void enQueue(int x){ //入队操作 Node *tmp; tmp = new Node(x); if(isEmpty()){ front = rear = tmp; } else{ rear->next = tmp; rear = tmp; } } bool deQueue(int *px){ //出队操作 if(isEmpty()) return false; else{ *px = front->data; Node *tmp; tmp = front; front = front->next; delete tmp; if (front == NULL) rear == NULL; return true; } } }; int main() { Queue q; q.enQueue(11); q.enQueue(22); q.enQueue(33); q.enQueue(44); int x; q.deQueue(&x); cout << x <<endl; q.deQueue(&x); cout << x <<endl; q.deQueue(&x); cout << x <<endl; q.deQueue(&x); cout << x <<endl; q.deQueue(&x); cout << x <<endl; return 0;
直接使用队列模板
#include <queue> //头文件 queue <int> q; 入队 q.push(x); 将x 接到队列的末端。 出队 q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。 访问队首元素 q.front(),即最早被压入队列的元素。 访问队尾元素 q.back(),即最后被压入队列的元素。 判断队列是否空 q.empty(),当队列空时,返回true。
原文链接: https://www.cnblogs.com/CK8719/p/12967165.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/350909
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!