队列 -- 顺序队列和链式队列类的实现

曾经终败给现在 2022-08-22 13:27 255阅读 0赞

## 队列的C++ ADT ##

#ifndef ADT_H
    #define ADT_H
    
    template <typename E>
    class Queue{
    private:
        void operator = (const Queue&){}
        Queue(const Queue&){}
    
    public:
        Queue(){}
        virtual ~Queue(){}
    
        //重置队列至最初状态
        virtual void clear() = 0;
    
        //入队
        virtual void enqueue(const E&) = 0;
    
        //出队并返回队首元素
        virtual E dequeue() = 0;
    
        //获取队首元素
        virtual const E& frontValue() const = 0;
    
        //元素数量
        virtual int length() const = 0;
    };
    
    #endif

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

## 链表节点定义： ##

#ifndef LINKNODE_H
    #define LINKNODE_H
    //单链表结点定义
    template <typename E>
    class Link{
    public:
        E element;                          //节点的值
        Link* next;                         //next
        Link(const E& elemval, Link* nextval = NULL){
            element = elemval;
            next = nextval;
        }
        Link(Link* nextval = NULL){
            next = nextval;
        }
    };
    #endif

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

## 顺序队列类的实现 ##

template <typename E>
    class AQueue : public Queue<E>{
    private:
        int maxSize;
        int front;
        int rear;
        E* listArray;
    
    public:
        AQueue(int size = defaultSize){
            //为了便于区分空队列和满队列，设置maxSize要比实际size大1
            maxSize = size + 1;
            rear = 0;
            front = 1;
            listArray = new E[maxSize];
        }
        ~AQueue(){
            delete[] listArray;
        }
    
        void clear(){
            rear = 0;
            front = 1;
        }
    
        void enqueue(const E& it){
            Assert(((rear + 2) % maxSize) != front, "Queue is full");
            rear = (rear + 1) % maxSize;
            listArray[rear] = it;
        }
    
        E dequeue(){
            Assert(length() != 0, "Queue is empty");
            E it = listArray[front];
            front = (front + 1) % maxSize;
            return it;
        }
    
        const E& frontValue() const{
            Assert(length() != 0, "Queue is empty");
            return listArray[front];
        }
    
        virtual int length() const{
            return ((rear + maxSize) - front + 1) % maxSize;
        }
    };

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

## 链式队列类的实现 ##

template <typename E>
    class LQueue :public Queue<E>{
    private:
        Link<E>* front;
        Link<E>* rear;
        int size;
    
    public:
        LQueue(int sz = defaultSize){
            front = rear = new Link<E>();
            size = 0;
        }
        ~LQueue();
    
        void clear(){
            while (front->next != NULL){
                rear = front;
                delete rear;
            }
            rear = front;
            size = 0;
        }
    
        void enqueue(const E& it){
            rear->next = new Link<E>(it, NULL);
            rear = rear->next;
            size++;
        }
    
        E dequeue(){
            Assert(size != 0, "Queue is empty");
            E it = front->next->element;
            link<E>* ltemp = front->next;
            front->next = ltemp->next;
            if (rear = ltemp)
                rear = front;
            delete ltemp;
            size--;
            return it;
        }
    
        const E& frontValue() const{
            Assert(size != 0, "Queue is empty");
            return front->next->element;
        }
    
        virtual int length() const{
            return size;
        }
    };

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