跳到主要内容

双端队列数据结构

提示
  1. 定义和特点：双端队列 (Deque) 是一种两端都可进行插入和删除操作的队列，不严格遵循先进先出 (FIFO) 原则。
  2. 两种类型：双端队列分为输入受限 Deque（只能在一端插入）和输出受限 Deque（只能在一端删除）。
  3. 主要操作：双端队列支持在前端和后端进行插入和删除操作，具有检查空或满状态的功能，通常使用循环数组实现。

Deque 或双端队列是一种队列，在这种队列中，元素的插入和删除既可以从前端进行也可以从后端进行。因此，它不遵循 FIFO 规则（先进先出）。

双端队列数据结构的表示

Deque 的类型​

  • 输入受限 Deque 在这种 deque 中，输入只能在一个端进行，但允许在两端进行删除。
  • 输出受限 Deque 在这种 deque 中，输出只能在一个端进行，但允许在两端进行插入。

对 Deque 的操作​

以下是 deque 的循环数组实现。在循环数组中，如果数组已满，我们从头开始。

但在线性数组实现中，如果数组已满，则不能再插入更多元素。在下面的每个操作中，如果数组已满，会抛出“溢出消息”。

在执行以下操作之前，会先进行这些步骤。

  1. 取一个大小为 n 的数组（deque）。
  2. 在第一个位置设置两个指针，设置 front = -1 和 rear = 0。

初始化数组和指针以进行 deque 操作

1. 在前端插入​

此操作在前端添加一个元素。

  1. 检查前端的位置。 检查前端的位置

  2. 如果 front < 1，重新初始化 front = n-1（最后一个索引）。 如果前端小于 1，则将前端移到末尾

  3. 否则，将 front 减少 1。

  4. 将新键 5 添加到 array[front] 中。 在前端位置插入元素

2. 在后端插入​

此操作在后端添加一个元素。

  1. 检查数组是否已满。 检查 deque 是否已满

  2. 如果 deque 已满，重新初始化 rear = 0。

  3. 否则，将 rear 增加 1。 如果 deque 未满，则增加 rear

  4. 将新键 5 添加到 array[rear] 中。 在后端插入元素

3. 从前端删除​

此操作从前端删除一个元素。

  1. 检查 deque 是否为空。 检查 deque 是否为空

  2. 如果 deque 为空（即 front = -1），则无法执行删除（下溢条件）。

  3. 如果 deque 只有一个元素（即 front = rear），则设置 front = -1 和 rear = -1。

  4. 否则，如果 front 在末端（即 front = n - 1），则跳到前端 front = 0。

  5. 否则，front = front + 1。 增加前端的索引

4. 从后端删除​

此操作从后端删除一个元素。

  1. 检查 deque 是否为空。 检查 deque 是否为空

  2. 如果 deque 为空（即 front = -1），则无法执行删除（下溢条件）。

  3. 如果 deque 只有一个元素（即 front = rear），则设置 front = -1 和 rear = -1，否则按以下步骤操作。

  4. 如果 rear 在前端（即 rear = 0），则跳到后端 rear = n - 1。

  5. 否则，rear = rear - 1。 减少 rear 位置

5. 检查是否为空​

此操作用于检查双端队列是否为空。如果 front = -1，则双端队列为空。

6. 检查是否已满​

此操作用于检查双端队列是否已满。如果 front = 0 且 rear = n - 1 或 front = rear + 1，则双端队列已满。

Python、Java、C 和 C++ 中的双端队列实现​

Python Java C C++

# Python 中的双端队列实现

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addRear(self, item):
        self.items.append(item)

    def addFront(self, item):
        self.items.insert(0, item)

    def removeFront(self):
        return self.items.pop(0)

    def removeRear(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


d = Deque()
print(d.isEmpty())
d.addRear(8)
d.addRear(5)
d.addFront(7)
d.addFront(10)
print(d.size())
print(d.isEmpty())
d.addRear(11)
print(d.removeRear())
print(d.removeFront())
d.addFront(55)
d.addRear(45)
print(d.items)
// 在 Java 中实现双端队列

class Deque {
  static final int MAX = 100;
  int arr[];
  int front;
  int rear;
  int size;

  public Deque(int size) {
    arr = new int[MAX];
    front = -1;
    rear = 0;
    this.size = size;
  }

  // 判断双端队列是否已满
  boolean isFull() {
    return ((front == 0 && rear == size - 1) || front == rear + 1);
  }

  // 判断双端队列是否为空
  boolean isEmpty() {
    return (front == -1);
  }

  // 在队列前端插入元素
  void insertfront(int key) {
    if (isFull()) {
      System.out.println("Overflow");
      return;
    }

    if (front == -1) {
      front = 0;
      rear = 0;
    }

    else if (front == 0)
      front = size - 1;

    else
      front = front - 1;

    arr[front] = key;
  }

  // 在队列后端插入元素
  void insertrear(int key) {
    if (isFull()) {
      System.out.println(" Overflow ");
      return;
    }

    if (front == -1) {
      front = 0;
      rear = 0;
    }

    else if (rear == size - 1)
      rear = 0;

    else
      rear = rear + 1;

    arr[rear] = key;
  }

  // 删除队列前端的元素
  void deletefront() {
    if (isEmpty()) {
      System.out.println("Queue Underflow\n");
      return;
    }

    // 双端队列中只有一个元素
    if (front == rear) {
      front = -1;
      rear = -1;
    } else if (front == size - 1)
      front = 0;

    else
      front = front + 1;
  }

  // 删除队列后端的元素
  void deleterear() {
    if (isEmpty()) {
      System.out.println(" Underflow");
      return;
    }

    if (front == rear) {
      front = -1;
      rear = -1;
    } else if (rear == 0)
      rear = size - 1;
    else
      rear = rear - 1;
  }

  // 获取队列前端的元素
  int getFront() {
    if (isEmpty()) {
      System.out.println(" Underflow");
      return -1;
    }
    return arr[front];
  }

  // 获取队列后端的元素
  int getRear() {
    if (isEmpty() || rear < 0) {
      System.out.println(" Underflow\n");
      return -1;
    }
    return arr[rear];
  }

  public static void main(String[] args) {

    Deque dq = new Deque(4);

    System.out.println("在后端插入元素 : 12 ");
    dq.insertrear(12);

    System.out.println("在后端插入元素 : 14 ");
    dq.insertrear(14);

    System.out.println("获取后端元素 : " + dq.getRear());

    dq.deleterear();
    System.out.println("删除后端元素后新的后端元素为 : " + dq.getRear());

    System.out.println("在前端插入元素");
    dq.insertfront(13);

    System.out.println("获取前端元素: " + dq.getFront());

    dq.deletefront();

    System.out.println("删除前端元素后新的前端元素为 : " + dq.getFront());

  }
}
// 在 C 中实现双端队列

#include <stdio.h>

#define MAX 10

void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);

int main() {
  int arr[MAX];
  int front, rear, i, n;

  front = rear = -1;
  for (i = 0; i < MAX; i++)
    arr[i] = 0;

  addRear(arr, 5, &front, &rear);
  addFront(arr, 12, &front, &rear);
  addRear(arr, 11, &front, &rear);
  addFront(arr, 5, &front, &rear);
  addRear(arr, 6, &front, &rear);
  addFront(arr, 8, &front, &rear);

  printf("\n队列中的元素: ");
  display(arr);

  i = delFront(arr, &front, &rear);
  printf("\n移除的元素: %d", i);

  printf("\n删除后队列中的元素: ");
  display(arr);

  addRear(arr, 16, &front, &rear);
  addRear(arr, 7, &front, &rear);

  printf("\n添加后队列中的元素: ");
  display(arr);

  i = delRear(arr, &front, &rear);
  printf("\n移除的元素: %d", i);

  printf("\n删除后队列中的元素: ");
  display(arr);

  n = count(arr);
  printf("\n双端队列中的元素总数: %d", n);
}

// 在前端添加元素
void addFront(int *arr, int item, int *pfront, int *prear) {
  int i, k, c;

  if (*pfront == 0 && *prear == MAX - 1) {
    printf("\n队列已满。\n");
    return;
  }

  if (*pfront == -1) {
    *pfront = *prear = 0;
    arr[*pfront] = item;
    return;
  }

  if (*prear != MAX - 1) {
    c = count(arr);
    k = *prear + 1;
    for (i = 1; i <= c; i++) {
      arr[k] = arr[k - 1];
      k--;
    }
    arr[k] = item;
    *pfront = k;
    (*prear)++;
  } else {
    (*pfront)--;
    arr[*pfront] = item;
  }
}

// 在后端添加元素
void addRear(int *arr, int item, int *pfront, int *prear) {
  int i, k;

  if (*pfront == 0 && *prear == MAX - 1) {
    printf("\n队列已满。\n");
    return;
  }

  if (*pfront == -1) {
    *prear = *pfront = 0;
    arr[*prear] = item;
    return;
  }

  if (*prear == MAX - 1) {
    k = *pfront - 1;
    for (i = *pfront - 1; i < *prear; i++) {
      k = i;
      if (k == MAX - 1)
        arr[k] = 0;
      else
        arr[k] = arr[i + 1];
    }
    (*prear)--;
    (*pfront)--;
  }
  (*prear)++;
  arr[*prear] = item;
}

// 从前端删除元素
int delFront(int *arr, int *pfront, int *prear) {
  int item;

  if (*pfront == -1) {
    printf("\n队列为空。\n");
    return 0;
  }

  item = arr[*pfront];
  arr[*pfront] = 0;

  if (*pfront == *prear)
    *pfront = *prear = -1;
  else
    (*pfront)++;

  return item;
}

// 从后端删除元素
int delRear(int *arr, int *pfront, int *prear) {
  int item;

  if (*pfront == -1) {
    printf("\n队列为空。\n");
    return 0;
  }

  item = arr[*prear];
  arr[*prear] = 0;
  (*prear)--;
  if (*pre

ar == -1)
    *pfront = -1;
  return item;
}

// 显示队列中的元素
void display(int *arr) {
  int i;

  printf("\n front:  ");
  for (i = 0; i < MAX; i++)
    printf("  %d", arr[i]);
  printf("  :rear");
}

// 计算队列中的元素数量
int count(int *arr) {
  int c = 0, i;

  for (i = 0; i < MAX; i++) {
    if (arr[i] != 0)
      c++;
  }
  return c;
}
// C++ 中的 Deque 实现

#include <iostream>
using namespace std;

#define MAX 10

class Deque {
  int arr[MAX];
  int front;
  int rear;
  int size;

   public:
  Deque(int size) {
    front = -1;
    rear = 0;
    this->size = size;
  }

  void insertfront(int key);
  void insertrear(int key);
  void deletefront();
  void deleterear();
  bool isFull();
  bool isEmpty();
  int getFront();
  int getRear();
};

bool Deque::isFull() {
  return ((front == 0 && rear == size - 1) ||
      front == rear + 1);
}

bool Deque::isEmpty() {
  return (front == -1);
}

void Deque::insertfront(int key) {
  if (isFull()) {
    cout << "Overflow\n"
       << endl;
    return;
  }

  if (front == -1) {
    front = 0;
    rear = 0;
  }

  else if (front == 0)
    front = size - 1;

  else
    front = front - 1;

  arr[front] = key;
}

void Deque ::insertrear(int key) {
  if (isFull()) {
    cout << " Overflow\n " << endl;
    return;
  }

  if (front == -1) {
    front = 0;
    rear = 0;
  }

  else if (rear == size - 1)
    rear = 0;

  else
    rear = rear + 1;

  arr[rear] = key;
}

void Deque ::deletefront() {
  if (isEmpty()) {
    cout << "Queue Underflow\n"
       << endl;
    return;
  }

  if (front == rear) {
    front = -1;
    rear = -1;
  } else if (front == size - 1)
    front = 0;

  else
    front = front + 1;
}

void Deque::deleterear() {
  if (isEmpty()) {
    cout << " Underflow\n"
       << endl;
    return;
  }

  if (front == rear) {
    front = -1;
    rear = -1;
  } else if (rear == 0)
    rear = size - 1;
  else
    rear = rear - 1;
}

int Deque::getFront() {
  if (isEmpty()) {
    cout << " Underflow\n"
       << endl;
    return -1;
  }
  return arr[front];
}

int Deque::getRear() {
  if (isEmpty() || rear < 0) {
    cout << " Underflow\n"
       << endl;
    return -1;
  }
  return arr[rear];
}

int main() {
  Deque dq(4);

  cout << "insert element at rear end \n";
  dq.insertrear(5);
  dq.insertrear(11);

  cout << "rear element: "
     << dq.getRear() << endl;

  dq.deleterear();
  cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl;

  cout << "insert element at front end \n";

  dq.insertfront(8);

  cout << "front element: " << dq.getFront() << endl;

  dq.deletefront();

  cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}

时间复杂度​

上述所有操作的时间复杂度都是常数级别的，即 O(1)。

Deque 数据结构的应用​

  1. 在软件中用于撤销操作。
  2. 用于存储浏览器的历史记录。
  3. 用于实现栈和队列。
最后于 更新