首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >队列数组实现中的删除会降低容量?

问队列数组实现中的删除会降低容量?
EN

Stack Overflow用户
提问于 2022-05-23 12:09:03
回答 1查看 64关注 0票数 0

在我看到的所有队列数组实现中,当它们‘从前面弹出一个元素’时,它们基本上会将队列的前端标记更改为下一个元素。但是,从技术上讲,队列的容量减少了(因为使用了数组)。这怎么还没有引起问题,或者这怎么被认为是有效的?

编辑:https://www.softwaretestinghelp.com/queue-in-cpp/在这个链接中接受正在考虑的插图。在执行去队列操作时,我们将前面的指针更改为下一个元素。从这一点开始,我们所执行的任何操作都将针对数组作为前端元素的第二个位置进行。现在,如果我们继续在队列的全部容量中添加元素,我们就会,最大的no。在队列中可以容纳的元素将比数组的容量少一个(我们在前面已经定义了这个数组)。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 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++实现的修正版本。

代码语言:javascript
复制
#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;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/72348293

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档