数据结构(七)队列

比眉伴天荒 2022-05-31 01:46 90阅读 0赞

**1、队列需要具备的特性**

队列和栈的底层实现数据结构可以是：数组、链表，只不过在此基础上，队列和栈需要重载两个函数：节点的插入与删除函数。队列只能从链表头删除节点，从链表末尾插入节点；

**2、示例代码**

#ifndef DATA_STRUCT_QUEUE_H
    #define DATA_STRUCT_QUEUE_H
    
    #include <iostream>
    using namespace std;
    class Queue{
        class node{//链表节点
        public:
            node(int tvalue)
            {
                value=tvalue;
                next=NULL;
            };
            ~node(){};
            node* next;
            int value;
    
        };
    public:
        Queue(){
            qhead=NULL;
            qrear=NULL;
        };
        ~Queue(){};
    
        //队列四大元素
        node* qhead;//队头
        node* qrear;//队尾
    
    
        void push(int value)//插入队列元素的时候，主要是更新队尾
        {
            node * n1=new node(value);
            if(!qhead){
                qhead=n1;
                qrear=n1;
                return;
            }
    
            qrear->next=n1;
            qrear=n1;
        }
        node * pop(){//出队列的时候，主要是更新队列头部
            if (!qhead)
            {
                return NULL;
            }
    
            node* temp=qhead;
            qhead=qhead->next;
    
            return temp;
        }
    
        bool empty(){//队列弹出，要判断是否队列已经为空
            return !qhead;
        }
    
        void main(){//用于测试
            int data[10]={1,2,3,4,5,6,7,8,9,10};
            for (int i = 0; i <10 ; ++i) {
                push(data[i]);
            }
    
            while(!empty())
            {
                node* n=pop();
                std::cout<<n->value<<std::endl;
                delete n;
            }
    
    
        }
    
    };
    #endif //DATA_STRUCT_QUEUE_H