链式队列Queue

男娘i 2022-05-26 20:10 181阅读 0赞

最近在学队列然后顺手写了这篇学习笔记

#### 队列的基本概念 ####

栈是先进后出 - 而队列是先进后出

--------------------

这里有一个队列:  
<1 , 2 , 3 , 4 , 5 , 6>  
通常我们对队列有两种操作

1.  出队
2.  入队

##### 出队 #####

对<1, 2, 3, 4, 5, 6>出队  
出队元素是1 然后 是 2, 然后是 3

##### 入队 #####

对<1, 2, 3, 4, 5, 6>入队  
将元素7入队 队列变成<1, 2, 3, 4, 5, 6, 7>

*  这里可以看出队列是从头部进行读取删除操作对尾部进行添加插入操作的
 *  就好像我们排队买票一样总是前面的买到票了离开 后面又加入要买票的人
 *      // 定义一个类
        #ifndef QUEUE_H
        #define QUEUE_H
        // 定义一个类 包含队列数据结构和操作队列的函数
        class Queue
        {
            private:// 队列数据
                struct ue{
             // 队列结构体
                    int num = 0;// 数据
                    struct ue *next;// 尾指针
                };
                struct ue *head, *last;// 头指针和尾指针
            public:
                Queue();
                ~Queue(); 
                // 显示所有信息 
                void show();
                // 查找某个值是否存在
                bool contains(int num); 
                // 访问第i个元素的值 
                int indexOf(int i);
                // 得到当前元素个数
                int size();  
                // 入队元素到末尾
                bool push(int num);
                // pop出队 - 但不删除 
                int pop();
                // popFrist - 出队并且删除
                int popFrist(); 
            protected:
        };
        #endif
    
        //队列类实现函数
        #include "Queue.h"
        #include <iostream>
        using namespace std;
        Queue::Queue()
        {
            head = nullptr;
        }
        // 访问第i个元素的值 
        int Queue::indexOf(int i){
            struct ue *p = this->head; 
            int x = 0;
            while(p && x != i){
                p = p->next; 
                x++;
            } 
            if(p)
                return p->num;
            return INT_MIN; 
        } 
        // 查找某个值是否存在
        bool Queue::contains(int num){
            struct ue *p = this->head; 
            while(p && p->num != num){
                p = p->next; 
            } 
            if(p)
                return true;
            return false; 
        } 
        // 得到当前元素个数
        int Queue::size(){
            int i = 0;
            struct ue *p;
            p = this->head;
            while(p){
                i++;
                p = p->next; 
            }
            return i;
        } 
        // 出队 不删除元素 
        int Queue::pop(){
            return this->head->num; 
        } 
        // 出队 并且删除元素
        int Queue::popFrist(){
            struct ue *p; 
            int num = this->head->num;
            p = this->head;
            this->head = this->head->next;
            delete p; 
            return num; 
        } 
        // 入队 
        bool Queue::push(int num){
            struct ue *p;
            p = new struct ue;
            p->num = num;
            p->next = nullptr;
            if( this->head == nullptr ){
                this->head = p;
            } else {
                this->last->next = p;
            }
            this->last = p;
        } 
        // 显示所有元素 
        void Queue::show(){
            struct ue *temp = this->head;
            while(temp){
                cout << temp->num << ", ";
                temp = temp->next;
            }
            cout << endl; 
        }
        // 释放空间 
        Queue::~Queue()
        {
            struct ue *p = this->head;
            while(p){
                this->head = p;
                p = p->next;
                delete head;
            }
        }
    
        // 在这里测试写的队列类
        #include <iostream>
        #include "Queue.h" 
        using namespace std; 
        int main(int argc, char** argv) {
            Queue queue;
            queue.push(10);// 入队
            queue.push(20);
            queue.push(101);
            queue.show();
            cout << "当前队列中有: " << queue.size() << endl; 
            cout << "队头元素为: " << queue.pop() << endl; 
            cout << "当前队列的元素个数: " << queue.size() << endl; 
            queue.show();
            cout << "队头元素为: (显示并删除): " << queue.popFrist() << endl; 
            cout << "当前队列的元素个数: " << queue.size() << endl; 
            queue.show();
            cout << "队列中是否包含该元素: " << queue.contains(20) << endl; 
            cout << "显示对应下标的元素值: " <<queue.indexOf(1) << endl; 
        
            return 0;
        }