21xrx.com
2024-12-22 21:08:37 Sunday
登录
文章检索 我的文章 写文章
C++实现双端队列
2023-07-11 07:50:03 深夜i     --     --
C++ 双端队列 实现

双端队列是一种特殊的队列，允许在队列的两端进行插入和删除操作。而C++作为一种高性能、可移植的编程语言，提供了方便的数据结构和算法支持，可以轻松实现这种数据结构。在本文中，我们将介绍如何使用C++实现双端队列。

首先，我们需要定义一个双端队列类。该类需要维护队列元素、队列大小、队首、队尾等成员变量。同时，类需要提供插入、删除、获取队首、获取队尾等成员函数。以下是一个简单的双端队列类定义：

#include

using namespace std;

const int MAX_SIZE = 100;

class Deque {

private:

  int items[MAX_SIZE];

  int size;

  int front;

  int rear;

public:

  Deque();

  bool isEmpty();

  bool isFull();

  int getFront();

  int getRear();

  void insertFront(int value);

  void insertRear(int value);

  void deleteFront();

  void deleteRear();

  void print();

};

接下来，我们需要定义类成员函数的具体实现。首先是构造函数，它将默认队列大小为0，队首和队尾都初始化为-1，表示队列为空：

Deque::Deque()

  size = 0;

  front = -1;

  rear = -1;

接着是isEmpty()和isFull()函数，它们分别用于判断队列是否为空和是否已满：

bool Deque::isEmpty()

  return size == 0;

bool Deque::isFull()

  return size == MAX_SIZE;

然后是获取队首和队尾元素的函数getFront()和getRear()：

int Deque::getFront() {

  if (isEmpty())

    cout << "Error: Queue is empty!" << endl;

    return -1;

  return items[front];

}

int Deque::getRear() {

  if (isEmpty())

    cout << "Error: Queue is empty!" << endl;

    return -1;

  return items[rear];

}

接着是双端队列的插入操作。insertFront()函数将一个元素插入到队列的前端，而insertRear()函数将一个元素插入到队列的后端：

void Deque::insertFront(int value) {

  if (isFull())

    cout << "Error: Queue is full!" << endl;

    return;

  if (front == -1) {

    front = 0;

    rear = 0;

    items[front] = value;

  } else if (front == 0) {

    front = MAX_SIZE - 1;

    items[front] = value;

  } else {

    front--;

    items[front] = value;

  }

  size++;

}

void Deque::insertRear(int value) {

  if (isFull())

    cout << "Error: Queue is full!" << endl;

    return;

  if (front == -1) {

    front = 0;

    rear = 0;

    items[rear] = value;

  } else if (rear == MAX_SIZE - 1) {

    rear = 0;

    items[rear] = value;

  } else {

    rear++;

    items[rear] = value;

  }

  size++;

}

其中，插入操作需要先进行队列是否已满的判断，如果已满则不允许继续插入。在插入元素时，需要进行特殊处理，如果队列满了，则需要将队列头或队列尾移动到队列另一端循环。

最后是双端队列的删除操作。deleteFront()函数将队列前端的元素删除，而deleteRear()函数将队列后端的元素删除：

void Deque::deleteFront() {

  if (isEmpty())

    cout << "Error: Queue is empty!" << endl;

    return;

  if (front == rear)

    front = -1;

    rear = -1;

   else if (front == MAX_SIZE - 1)

    front = 0;

   else {

    front++;

  }

  size--;

}

void Deque::deleteRear() {

  if (isEmpty())

    cout << "Error: Queue is empty!" << endl;

    return;

  if (rear == front)

    rear = -1;

    front = -1;

   else if (rear == 0)

    rear = MAX_SIZE - 1;

   else

    rear--;

  size--;

}

删除操作也需要进行队列是否为空的判断，如果为空则不允许进行删除。在删除元素时，同样需要进行特殊处理，如果队列中只有一个元素，则需要将队列头和队列尾都置为-1，表示队列为空。

最后是打印队列元素的函数print()：

void Deque::print() {

  if (isEmpty())

    cout << "Queue is empty!" << endl;

    return;

  int count = 0;

  for (int i = front; count < size; i = (i + 1) % MAX_SIZE) {

    cout << items[i] << " ";

    count++;

  }

  cout << endl;

}

该函数中，首先判断队列是否为空，然后使用循环打印队列元素。由于队列元素可能是循环的，因此需要使用i=(i+1)%MAX_SIZE的方式来获取队列元素。

到此为止，我们已经实现了一个双端队列基本功能的C++类。通过调用类的成员函数，我们可以轻松地对双端队列进行插入、删除和打印等操作。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复