删除队列的数组实现会降低容量？

Question

在我见过的所有队列数组实现中，当它们'pop an element from front'时，它们基本上是将队列的前面标记更改为下一个元素。但随后队列的容量在技术上减少了（因为使用了数组）。这怎么还没有引起问题，或者这怎么被认为有效？

编辑：https://www.softwaretestinghelp.com/queue-in-cpp/ 以这个link中的例子为例。当我们执行出队操作时，我们将front的指针更改为下一个元素。从这一点开始，我们执行的任何操作都将以数组的第 2 个位置作为前面的元素来完成。现在，如果我们继续将元素添加到队列的全部容量中，我们将得到最大数量。我们可以放入队列的元素的数量将比数组的容量（我们之前定义的）少 1。

Answer 1

您对文章 https://www.softwaretestinghelp.com/queue-in-cpp/ 中给出的 C++ 实现的关注是正确的。通过该实现，基本上当您使元素出列时，指向队列“第一个”的指针向右移动 1 个单位（在底层数组中），从而减少队列的容量。

实现这种队列的正确方法应该类似于那篇文章中提供的 Java 实现。如您所见，每个数组索引都是 pre-processed 和 % 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;
}

删除队列的数组实现会降低容量？

Deletion in array implementation of queues reduces capacity?

c++

queue

data-structures