队列类(C++)

骑猪看日落 2024-04-01 15:58 43阅读 0赞

## 用C++实现队列 ##

请设计通用队列类。

首先定义数据元素类型

`typedef double ELEMENT;`  
然后定义队列

class QUEUE
    {
        
    public:
        QUEUE();
        ~QUEUE();
        bool Enqueue(const ELEMENT &value);
        bool Dequeue(ELEMENT &value);
        bool Clear();
        bool Empty() const;
        int Length() const;
    
        const static int queueSize;
    
    private:
        int size, front, rear;
        ELEMENT *element;
    };
    
    const int QUEUE::queueSize = 5;

说明：

size 为动态数组的尺寸，front 为队首元素的下标，rear 为队尾元素下一位置的下标，element 为动态数组的起始地址。  
queueSize 为动态数组的尺寸，初始值为 5。  
构造函数：初始化队列：将初始尺寸保存到 size，将队首 front 和队尾 rear 均置为 0，为动态数组分配内存并将起始地址保存到 element。  
析构函数：清理队列：释放动态数组的内存。  
Enqueue 函数：若队列未满，则将元素 value 保存到队列中，函数值为 true；否则报告上溢错误，函数值为 false。  
Dequeue 函数：若队列不空，则从队列中取出元素并保存到 value中，函数值为 true；否则报告下溢错误，函数值为 false。  
Clear 函数：清空队列，将 front 和 rear 重置为 0，操作成功，函数值为 true。  
Empty 函数：若队列空，则函数值为 true，否则为 false。  
Length 函数：函数值为队列中元素的数量。  
提示：循环队列最多装 queueSize - 1 个元素。

**裁判程序**

#include <iostream>
    #include <iomanip>
    using namespace std;
    #include <cctype>
    
    typedef double ELEMENT;
    
    class QUEUE
    {
        
    public:
        QUEUE();
        ~QUEUE();
        bool Enqueue(const ELEMENT &value);
        bool Dequeue(ELEMENT &value);
        bool Clear();
        bool Empty() const;
        int Length() const;
    
        const static int queueSize;
    
    private:
        int size, front, rear;
        ELEMENT *element;
    };
    
    const int QUEUE::queueSize = 5;
    
    /* 你提交的代码将被嵌在这里 */
    
    int main()
    {
        
        QUEUE queue;
        ELEMENT value;
        char choice;
        do
        {
        
            cout << "eNqueue Dequeue Clear Empty Length Quit > ";
            cin >> choice;
            choice = toupper(choice);
            
            switch (choice)
            {
        
            case 'N':
                cout << "Value: ";
                cin >> value;
                if (queue.Enqueue(value))
                {
        
                    cout << "Enqueue successfully!\n";
                }
                else
                {
        
                    cout << "Enqueue failed!\n";
                }
                break;
            case 'D':
                if (queue.Dequeue(value))
                {
        
                    cout << "Dequeue successfully!\n";
                    cout << "Value: " << value << endl;
                }
                else
                {
        
                    cout << "Dequeue failed!\n";
                }
                break;
            case 'C':
                if (queue.Clear())
                {
        
                    cout << "Clear successfully!\n";
                }
                else
                {
        
                    cout << "Clear failed!\n";
                }
                break;
            case 'E':
                if (queue.Empty())
                {
        
                    cout << "Queue is empty!\n";
                }
                else
                {
        
                    cout << "Queue is not empty!\n";
                }
                break;
            case 'L':
                cout << "Queue length: " << queue.Length() << endl;
                break;
            case 'Q':
                break;
            default:
                cout << "Incorrect choice!\n";
            }
        }
        while (choice != 'Q');
    }

**测试样例1**

eNqueue Dequeue Clear Empty Length Quit > t
    Incorrect choice!
    eNqueue Dequeue Clear Empty Length Quit > K
    Incorrect choice!
    eNqueue Dequeue Clear Empty Length Quit > Q

**测试样例2**

eNqueue Dequeue Clear Empty Length Quit > L
    Queue length: 0
    eNqueue Dequeue Clear Empty Length Quit > e
    Queue is empty!
    eNqueue Dequeue Clear Empty Length Quit > N
    Value: 4.5
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > n
    Value: 1.6
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > l
    Queue length: 2
    eNqueue Dequeue Clear Empty Length Quit > E
    Queue is not empty!
    eNqueue Dequeue Clear Empty Length Quit > d
    Dequeue successfully!
    Value: 4.5
    eNqueue Dequeue Clear Empty Length Quit > D
    Dequeue successfully!
    Value: 1.6
    eNqueue Dequeue Clear Empty Length Quit > D
    Queue underflow!
    Dequeue failed!
    eNqueue Dequeue Clear Empty Length Quit > q

**测试样例3**

eNqueue Dequeue Clear Empty Length Quit > n
    Value: 1.7
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > n
    Value: 2.8
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > n
    Value: 3.6
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > n
    Value: 4.9
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > n
    Value: 9.9
    Queue overflow!
    Enqueue failed!
    eNqueue Dequeue Clear Empty Length Quit > L
    Queue length: 4
    eNqueue Dequeue Clear Empty Length Quit > e
    Queue is not empty!
    eNqueue Dequeue Clear Empty Length Quit > C
    Clear successfully!
    eNqueue Dequeue Clear Empty Length Quit > l
    Queue length: 0
    eNqueue Dequeue Clear Empty Length Quit > E
    Queue is empty!
    eNqueue Dequeue Clear Empty Length Quit > n
    Value: 8.5
    Enqueue successfully!
    eNqueue Dequeue Clear Empty Length Quit > D
    Dequeue successfully!
    Value: 8.5
    eNqueue Dequeue Clear Empty Length Quit > q

输出样例

eNqueue Dequeue Clear Empty Length Quit >

输入样例  
`q`

**提交代码**：

QUEUE::QUEUE()
    {
        
        this->front = this->rear = 0;
        this->size = queueSize;
        element = new ELEMENT[this->size];
    }
    QUEUE::~QUEUE()
    {
        
        front = rear = 0;
        delete []element;
    }
    bool QUEUE::Enqueue(const ELEMENT &value)
    {
        
        if ((this->rear + 1) % this->size == this->front || QUEUE::Length() >= this->size || this->rear >= this->size)
        {
        
            cout << "Queue overflow!\n";
            return false;
        }
        this->element[this->rear % this->size] = value;
        this->rear = (this->rear + 1) % this->size;
        return true;
    }
    bool QUEUE::Dequeue(ELEMENT &value)
    {
        
        if (this->front % this->size == this->rear % this->size)
        {
        
            cout << "Queue underflow!\n";
            return false;
        }
        value = element[this->front % this->size];
        this->front = (this->front + 1) % this->size;
        return true;
    }
    bool QUEUE::Clear()
    {
        
        this->front = this->rear = 0;
        return true;
    }
    bool QUEUE::Empty() const
    {
        
        return this->rear == this->front;
    }
    int QUEUE::Length() const
    {
        
        return (this->rear - this->front + this->size) % this->size;
    }