数据结构之队列

旧城等待， 2022-05-25 02:42 167阅读 0赞

## 一、 队列的顺序存储结构及实现 ##

### 1.0 啥叫队列 ###

栈就相当往杯子里放东西，而队列就相当于往管子里放水，只能这头进，那头出

队列就是只允许在一段进行插入操作，另一端进行删除操作的线性表

### 2.0 队列的一个问题 ###

例如在a\[10\] 大小的数组中设计队列，那么假设我们入队3个 出队2个

也就是 入队顺序 a\[0\] a\[1\] a\[2\] 是有元素的，然后出队顺序是 a\[0\] a\[1\] 这时候对头元素是 a\[2\]

接着入队顺序就是 a\[3\] a\[4\] a\[5\] 出队顺序 a\[2\] a\[3\] 。。。。。。

可以看出来队头元素一直往后缩，那么最终接过就是a\[9\]有元素，于是不能入队了 因为数组的大小就是10

但是a\[9\]以前还有地方，这样就存在假溢出。

为了解决假溢出现象，我们提出另一种队列**循环队列**

### 3.0 循环队列 ###

循环队列就是加入a\[9\] 满了 ，那么下一个元素会存到数组的第一个位置即a\[0\] 然后a\[1\]

#### 1.0 队列的指针 ####

分为队头指针front 和队尾指针 rear

我习惯吧队头指针设为队头元素的前一个位置，队尾指针指向队尾元素，这样队尾减去队头正好是队列的长度

#### 2.0 队列的操作 ####

*  初始化 头指针和尾指针指向同一位置 位置任意给
 *  入队 尾指针+1
 *  出队 头指针+1
 *  读队头元素
 *  判空 头指针和尾指针在同一位置
 *  判满

#### 3.0 循环队列的两个重要问题 —– 队空和队满 ####

当队尾指针由指向a\[9\] 转为a\[0\] 的时候 队尾指针的值是 rear  
队空 ：头指针和尾指针在同一位置  
队列满： 理论上是头指针和尾指针在同一位置 但是这和判空冲突，所以我们浪费一个存储单元  
这样我们判断队满的操作就是 front = rear + 1;

### 4.0 代码才是王道 ###

#include <iostream>
    using namespace std;
    
    const int Max = 10;
    
    class Queue{
        private:
            int front;
            int rear;
            int Data[Max];
        public:
            //初始化队列 队尾和队头指针 
            Queue(){
                front = 0;
                rear = 0;
            }
            //入队操作 
            void EnQueue(int a){
                rear = (rear+1)%Max;
                Data[rear] = a;
            }
            //出队操作
            int  DeQueue(){
                int x = Data[front+1];
                front = (front+1)%Max;
                return x;
            } 
            //取队头元素 不删除 
            int getQueue(){
                return Data[front+1];
            }
            //判空操作
            int IsEmpty(){
                return front == rear?1:0;  
            } 
            //判定队列满了 
            int IsFull(){
                return rear+1 == front?1:0;
            }
    }; 
    
    int main(){
        Queue queue;
        queue.EnQueue(10);
        cout<<queue.getQueue()<<endl;
        cout<<queue.IsEmpty()<<endl;
        cout<<queue.IsFull()<<endl;
        cout<<"取队头元素"<<queue.DeQueue()<<endl;
        cout<<"结果是1 就对了"<<queue.IsEmpty();
    }

> 本人博客多少c语言程序都是在devc 平台编译通过，若是在vs2010等平台调试 需要修改一下。这个自己修改吧，一点难度没有。

## 二、队列的连接存储及实现 ##

说多了 没用 直接上代码

#include <iostream>
    using namespace std;
    
    struct Node{
        int data;
        Node* next;
    };
    class Queue{
        private:
            Node* front;
            Node* rear;
        public:
            //初始化队列 队尾和队头指针 
            Queue(){
                front = new Node;
                front->next = NULL;
                rear = front;
            }
            //入队操作 
            void EnQueue(int a){
                Node* s = new Node;
                s->data = a;
                s->next = front->next;
                rear->next = s;
                rear = s;
            }
            //出队操作
            int  DeQueue(){
                int x = front->next->data;
                Node* p = front->next; 
                front = front->next;
                delete p;
                return x;
            } 
            //取队头元素 不删除 
            int getQueue(){
                int x  = front->next->data;
                return x;
            }
            //判空操作
            int IsEmpty(){
                return front == rear?1:0;  
            } 
            //链队列不存在队列满的情况 只能说你电脑内存空间没了 
    
    }; 
    
    int main(){
        Queue q;
        q.EnQueue(10);
        cout<<"是不是空的？0不是 1是 :"<<q.IsEmpty()<<endl;
        cout<<"队头元素是: "<<q.getQueue()<<endl;
        cout<<q.DeQueue()<<endl;
        cout<<"这回肯动是空的 1 :"<<q.IsEmpty(); 
    }