c++ - 使用C++循环实现队列数据结构

Question

我编写了以下 C++ 代码来实现队列数据结构。但是，我有两个问题:

1. 每当我删除前面的元素时，它都能正常工作。但是，当我按 2 删除前面的元素时，即使队列为空，我也会收到一条消息“Queue empty”后跟下一行的 5。我怎样才能防止 5 出现，它为什么会出现？

2. 当我完全填满队列并想要显示内容时，队列正在不停地无限打印。我认为显示函数中的for循环有问题。当队列未满时，显示功能可以正常工作。我该如何解决这个问题？

我的代码:

#include<iostream>
using namespace std;
int data;
class queue {

    private:
        int front,rear,capacity,a[100];

    public:
        queue(int n)
        {
            rear=front=-1;
            capacity=n;
        }

        void enqueue(int n)
        {
            if(front==-1)
            {
                front++;
                rear=front;
                a[front]=n;     
                return; 
            }
            if(rear%capacity==(front-1)%capacity)
            {
                cout<<"Queue is full\n";
                return;
            }
            rear=(rear+1)%capacity;
            a[rear]=n;

        }

        int dequeue()
        {
            if(front==rear&&front==-1)
            {
                cout<<"Queue is empty";
                return 0;
            }   
            if(front==rear&&front!=-1)
            {
                data=a[front];
                front=rear=-1;
                return data;
            }

            data=a[front];
            front=(front+1)%capacity;
            return data;
        }

        void display()
        {
            int i;
            for(i=front;i!=rear+1;i=(i+1)%capacity)
            cout<<a[i]<<endl;
        }

};

main()
{
    int x,y,c;
    cout<<"Enter capacity\n";
    cin>>c;
    queue q(c);

    while(1)
    {
        cout<<"Select option 1.insert 2.delete 3.display 4.exit\n";
        cin>>x;
        switch(x)
        {
            case 1: cout<<"Enter the element\n";
                    cin>>y;
                    q.enqueue(y);
                    break;
            case 2: q.dequeue();
                    break;
            case 3: q.display();
                    break;
            case 4: exit(0);                    
        }
    }
    return 0;
}

谢谢!!

Answer 1

1.空队列显示

删除空队列中的元素效果很好。但是空队列的显示有问题:

当队列为空时，front和rear都是-1。

for 循环以 i=front 开始，所以 i 是 -1

条件是 i != rear + 1; ，第一次为真(如 -1 != 0)，所以循环执行一次打印a[-1]，这是未定义的行为。因此是垃圾输出。

2.已满队列

当队列满时，front为0，rear为capactity-1。

因此，您以 i 为 0 开始 for 循环，然后循环并打印出每个元素。 i 的最后一个元素是 rear，即 capacity-1

当进一步迭代时，您执行 i = (i + 1) % capacity 使用 i 的当前值，这相当于 i= (capacity-1 + 1) % capacity 这将是 0，在这里你又开始循环了!

随着您的增量，您将永远不会到达循环结束条件。

如何解决？

这里是一个工作版本

void display()
{
    int i;
    if (front == -1)  // This is a special case
        cout << "No elements" <<endl;
    else              // now the general case: do the module in the loop body (i.e. uppon increment and success
        for (i = front; i != rear + 1; i++) 
            cout << a[i% capacity] << endl;
}