在我看到的所有队列数组实现中,当它们‘从前面弹出一个元素’时,它们基本上会将队列的前端标记更改为下一个元素。但是,从技术上讲,队列的容量减少了(因为使用了数组)。这怎么还没有引起问题,或者这怎么被认为是有效的?
编辑:https://www.softwaretestinghelp.com/queue-in-cpp/在这个链接中接受正在考虑的插图。在执行去队列操作时,我们将前面的指针更改为下一个元素。从这一点开始,我们所执行的任何操作都将针对数组作为前端元素的第二个位置进行。现在,如果我们继续在队列的全部容量中添加元素,我们就会,最大的no。在队列中可以容纳的元素将比数组的容量少一个(我们在前面已经定义了这个数组)。
发布于 2022-05-24 07:25:39
您对C++实现的关注是正确的,这是在文章https://www.softwaretestinghelp.com/queue-in-cpp/中给出的。使用该实现,基本上当您去队列元素时,指向队列“第一”的指针向右移动1单元(在基础数组中),这将降低队列的容量。
实现这样一个队列的正确方法应该类似于本文中提供的Java实现。如您所见,每个数组索引都是用% this.max_size进行预处理的.这使得数组访问变得“循环”,即当我们访问索引k >= this.max_size时,真正的数组索引返回到范围[0, this.max_size - 1]。因此,使用了基础数组中的所有插槽,这使得队列的容量在去队列或队列操作之后保持不变。
以下是C++实现的修正版本。
#include <iostream>
#define MAX_SIZE 5
using namespace std;
class Queue
{
private:
int myqueue[MAX_SIZE], front, rear;
public:
Queue ()
{
front = -1;
rear = -1;
}
bool isFull ()
{
if ((rear - front + MAX_SIZE) % MAX_SIZE == MAX_SIZE - 1)
{
return true;
}
return false;
}
bool isEmpty ()
{
if (front == -1)
return true;
else
return false;
}
void enQueue (int value)
{
if (isFull ())
{
cout << endl << "Queue is full!!";
}
else
{
if (front == -1)
front = 0;
rear++;
myqueue[rear % MAX_SIZE] = value;
cout << value << " ";
}
}
int deQueue ()
{
int value;
if (isEmpty ())
{
cout << "Queue is empty!!" << endl;
return (-1);
}
else
{
value = myqueue[front % MAX_SIZE];
if (front >= rear)
{ //only one element in queue
front = -1;
rear = -1;
}
else
{
front++;
}
cout << endl << "Deleted => " << value << " from myqueue";
return (value);
}
}
/* Function to display elements of Queue */
void displayQueue ()
{
int i;
if (isEmpty ())
{
cout << endl << "Queue is Empty!!" << endl;
}
else
{
cout << endl << "Front = " << front;
cout << endl << "Queue elements : ";
for (i = front; i <= rear; i++)
cout << myqueue[i % MAX_SIZE] << "\t";
cout << endl << "Rear = " << rear << endl;
}
}
};
int
main ()
{
Queue myq;
myq.deQueue (); //deQueue
cout << "Queue created:" << endl;
myq.enQueue (10);
myq.enQueue (20);
myq.enQueue (30);
myq.enQueue (40);
myq.enQueue (50); //enqueue 60 => queue is full
myq.enQueue (60);
myq.displayQueue ();
//deQueue =>removes 10, 20
myq.deQueue ();
myq.deQueue ();
//queue after dequeue
myq.displayQueue ();
myq.enQueue (70);
myq.enQueue (80);
myq.enQueue (90); //enqueue 90 => queue is full
myq.displayQueue ();
return 0;
}https://stackoverflow.com/questions/72348293
复制相似问题