队列也是一种特殊的 “表”,使用队列时插入是在一端操作,而删除则是在另外一端
队列的基本操作是enqueue(入队),它是在表的末端(称为队尾)插入--个元素;dequeue(出队),它是删除(并返回)表的开头(叫作队头)的元素。下图显示了一个队列的抽象模型。
- #include
- #include
- #include
- using namespace std;
-
- struct Node{
- int val;
- Node* next;
- Node(int v){
- val = v;
- next = NULL;
- }
- };
- class Queue{
- int size;
- Node* head; //pointer to the font node
- Node* back; //pointer to the least node
- public:
- Queue(){
- size = 0;
- head = back = NULL;
- }
- bool empty(){
- return size == 0;
- }
- Node* front(){
- return head;
- }
- Node* push_back(int v){
- if (size == 0){
- //note that head-next should give valuation after head
- head->next = head = back = new Node(v);
- }
- else if (size == 1){
- head->next = back = new Node(v);
- }
- else {
- back->next = new Node(v);
- back = back->next;
- }
- size++;
- return back;
- }
- //delete the font node
- void pop(){
- if (empty()) return;
- Node* temp = head;
- head = head->next ;
- delete temp;
- size--;
- }
- };
-
- void test_queue(){
- Queue queue;
- int n;
- cin >> n;
- for (int i = 0; i < n; i++){
- int temp;
- cin >> temp;
- queue.push_back(temp);
- }
- //you have to judge if queue is empty before using this font node
- while (queue.empty() == false){
- cout << queue.front()->val << endl;
- queue.pop();
- }
- return;
- }
-
- int main(){
- test_queue();
- return 0;
- }
2.用数组实现
对于每一个队列数据结构,我们保留一个数组theArray以及位置front和back,它们代表队列的两端。我们还要记录实际存在于队列中的元素的个数currentsize。下图表示处于某个中间状态的一个队列。
操作应该是清楚的。要enqueue元素x,可将currentsize和 back增1,然后置theArray[back]=x。要dequeue一个元素,可以置返回值为theArray[front],将currentsize减1,再将front增1。其他的方法也可以使用(将在后面讨论)。现在论述错误的检测。
这种实现存在一个潜在的问题。经过10次enqueue后,队列似乎是满了,因为back现在是数组的最后一个下标,而下一次执行enqueue就会是一个不存在的位置。然而,队列中也许只存在几个元素,因为若干元素可能已经出队了。像栈一样,即使在有许多操作的情况下队列也常常不是很大。
简单的解决方法是,只要front或back到达数组的尾端,就绕回到开头。下列图显示了在某些操作期间的队列情况。这称为循环数组(circular array)实现可以看成换环队列。
环形队列与普通队列的区别:
1.front头部指针
一般队列:front头部指针初始值为-1,从队列取数据时,该值依次递增,指向的元素即待取出的数据,而队列的头部数据所在的指针位置为front+1。当front=maxSize-1时,队列最后一个数据取出,此时队列为空。
环形队列:front头部指针初始值为0,指向的元素既是队列的头部数据也是待取出的数据。从队列取数据时,因逻辑上的闭环,指针可能再次回到前面的位置,不能单一递增处理,需通过取模来重新计算指针的值。
2.rear尾部指针
一般队列:rear尾部指针初始值为-1,队列添加数据时,该值依次递增,当rear=maxSize-1时,队列满,无法再添加数据。
环形队列:rear尾部指针初始值为0,指向待添加数据的位置,队列添加数据时,因逻辑上的闭环,指针可能再次回到前面的位置,不能单一递增处理,会出现角标越界异常,需通过取模来重新计算指针的值。
3.队列空的判断逻辑
一般队列:rear == front时,队列空。
环形队列:rear == front时,队列空。
4.队列满的判断逻辑
一般队列:rear = maxSize - 1时,队列满。
环形队列:(rear + 1) % maxSize == front时,队列满。
代码实现:
- #include
- #include
- #include
-
- class Ciclequeue
- {
- public:
- //队列最大容量
- int m_maxSize;
- //队列头指针
- int m_frontIdx;
- //队列尾指针
- int m_rearIdx;
- //队列数组
- int *m_queueArr;
- public:
- //构造函数
- Ciclequeue(int tmpSize)
- {
- m_maxSize = tmpSize;
- m_frontIdx = 0;
- m_rearIdx = 0;
- m_queueArr = new int[m_maxSize];
- memset(m_queueArr, 0 , sizeof(int)*m_maxSize);
- }
-
- //析构函数
- ~Ciclequeue()
- {
- delete m_queueArr;
- m_queueArr = NULL;
- }
-
- //入队
- void enqueue(int datavalue)
- {
- if(isfull())
- {
- std::cout<<"Queue is full!"<
- return;
- }
-
- m_queueArr[m_rearIdx] = datavalue;
- m_rearIdx = (m_rearIdx + 1)%m_maxSize;
- }
-
- //出队
- void dequeue()
- {
- if(isempty())
- {
- std::cout<<"Queue is empty!"<
- return;
- }
-
- m_queueArr[m_frontIdx] = -1; //模拟出队列动作
- m_frontIdx = (m_frontIdx + 1)%m_maxSize;
- }
-
- //检查队列是否已满
- bool isfull()
- {
- if(m_maxSize == -1)
- {
- std::cout<<"Create queue error!"<
- return false;
- }
- return (m_rearIdx + 1)%m_maxSize == m_frontIdx;
- }
-
- //检查队列是否为空
- bool isempty()
- {
- if(m_maxSize == -1)
- {
- std::cout<<"Create queue error!"<
- return false;
- }
- return m_rearIdx == m_frontIdx;
- }
-
- //当前队列元素各个数
- int size()
- {
- return (m_rearIdx - m_frontIdx + m_maxSize) % m_maxSize;
- }
-
- //显示队列
- void showqueue()
- {
- if(isempty())
- {
- return;
- }
-
- for(int i = m_frontIdx; i < m_frontIdx + size(); i++ )
- {
- std::cout<
" "< - }
- }
-
- //显示队列头
- void showqueuefront()
- {
- std::cout<
- }
- };
-
- int main(int argc, char **argv)
- {
- int tmpSize = std::atoi(argv[1]);
- if(tmpSize <= 0)
- {
- std::cout<<"Set MaxSize Error!"<
- return 0;
- }
-
- Ciclequeue *testqueue = new Ciclequeue(tmpSize);
- testqueue->enqueue(3);
- testqueue->enqueue(2);
- testqueue->dequeue();
- testqueue->enqueue(4);
- testqueue->dequeue();
- testqueue->enqueue(5);
- testqueue->enqueue(66);
- testqueue->enqueue(88);
- testqueue->enqueue(1204);
-
- testqueue->showqueue();
-
- delete testqueue;
- testqueue = NULL;
-
- return 0;
- }
3.队列的应用
关于计算机网络的。有许多种PC机的网络设置,其中磁盘是放一台叫作文件服务器(file server)的机器上的。使用其他计算机的用户是按照先到先使用的原则访问文件的,
因此其数据结构是一个队列
升级:
一个称为排队论(queuing theory)的数学分支用概率的方法处理--些诸如计算用户预计要排队等待的时间、等待的队伍能够排多长等类问题。问题的答案依赖于用户加入队列的频率以及-一旦用户得到服务时处理服务花费的时间。这两个参数作为概率分布函数给出。在一些简单的情况下,答案可以解析地算出。一种简单的例子是条电话线有一个接线员。如果接线员忙,打来的电话就被放到个等待队列中(这还与某个容许的最大限度有关)。这个问题在商业上很重要,因为研究表明,人们会很快挂上电话。如果有k个接线员,那么这个问题解决起来要困难得多。解析求解困难的问题往往使用模拟的方法求解。此时,需要使用一个队列来进行模拟。如果k很大,那么还需要其他一些数据结构来使得模拟更有效地进行。
关注我一起学!!!
-
相关阅读:
HAproxy+keepalived+nginx 实验部署
http https http2 http3
Verilog 延迟反标注
【C++天梯计划】1.9 回溯法(bark tracking method)
【 OpenGauss源码学习 —— 列存储(CUStorage)】
docker 启动镜像命令
2d关键点转bvh fbx
SpringMVC之全局异常拦截器
独立站shopify卖家如何玩转TikTok?
VS Code 在线运行:code-server部署(系列一)
-
原文地址:https://blog.csdn.net/qq_62309585/article/details/126772828