Deque 数据结构

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

representation of deque data structure — 双端队列的表示

双端队列的类型

输入受限双端队列
在此双端队列中，输入仅限于一个端点，但允许在两个端点进行删除。
输出受限双端队列
在此双端队列中，输出仅限于一个端点，但允许在两个端点进行插入。

双端队列的操作

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

但在线性数组实现中，如果数组已满，则无法再插入元素。在下面的每个操作中，如果数组已满，将显示“溢出消息”。

在执行以下操作之前，会遵循以下步骤。

取一个大小为 n 的数组（双端队列）。
设置两个指针 front = -1 和 rear = 0。

initialize an array and pointers for deque operations — 初始化双端队列的数组和指针

1. 从前端插入

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

检查双端队列是否已满。

检查前端的位置
如果双端队列已满（即 (front == 0 && rear == n - 1) || (front == rear + 1) ），则无法执行插入操作（溢出条件）。
如果双端队列为空，则重新初始化 front = 0。然后，将新键添加到 array[front]。
如果 front = 0，则重新初始化 front = n-1（最后一个索引）。

将前端移到末尾
否则，将 front 减 1。
将新键 5 添加到 array[front]。

将元素插入前端

2. 从后端插入

此操作将元素添加到后端。

检查双端队列是否已满。

检查双端队列是否已满
如果双端队列已满，则无法执行插入操作（溢出条件）。
如果双端队列为空，则重新初始化 rear = 0。然后，将新键添加到 array[rear]。
如果 rear = n - 1，则重新初始化 real = 0（第一个索引）。
否则，将 rear 加 1。

增加后端
将新键 5 添加到 array[rear]。

将元素插入后端

3. 从前端删除

此操作从 front 删除一个元素。

检查双端队列是否为空。

检查双端队列是否为空
如果双端队列为空（即 front = -1），则无法执行删除操作（下溢条件）。
如果双端队列只有一个元素（即 front = rear），则将 front = -1 和 rear = -1。
否则，如果 front 在最后一个索引（即 front = n - 1），则将 front = 0。
否则，front = front + 1。

增加前端

4. 从后端删除

此操作从 rear 删除一个元素。

检查双端队列是否为空。

检查双端队列是否为空
如果双端队列为空（即 front = -1），则无法执行删除操作（下溢条件）。
如果双端队列只有一个元素（即 front = rear），则将 front = -1 和 rear = -1，否则按照以下步骤操作。
如果 rear 在第一个索引（即 rear = 0），则重新初始化 rear = n - 1。
否则，rear = rear - 1。

减少后端

5. 检查空

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

6. 检查满

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

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

Python

Java

C++

# Deque implementaion in 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)

// Deque implementation in 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;
    }

    // Deque has only one element
    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("Insert element at rear end : 12 ");
    dq.insertrear(12);

    System.out.println("insert element at rear end : 14 ");
    dq.insertrear(14);

    System.out.println("get rear element : " + dq.getRear());

    dq.deleterear();
    System.out.println("After delete rear element new rear become : " + dq.getRear());

    System.out.println("inserting element at front end");
    dq.insertfront(13);

    System.out.println("get front element: " + dq.getFront());

    dq.deletefront();

    System.out.println("After delete front element new front become : " + +dq.getFront());

  }
}

// Deque implementation in 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("\nElements in a deque: ");
  display(arr);

  i = delFront(arr, &front, &rear);
  printf("\nremoved item: %d", i);

  printf("\nElements in a deque after deletion: ");
  display(arr);

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

  printf("\nElements in a deque after addition: ");
  display(arr);

  i = delRear(arr, &front, &rear);
  printf("\nremoved item: %d", i);

  printf("\nElements in a deque after deletion: ");
  display(arr);

  n = count(arr);
  printf("\nTotal number of elements in deque: %d", n);
}

void addFront(int *arr, int item, int *pfront, int *prear) {
  int i, k, c;

  if (*pfront == 0 && *prear == MAX - 1) {
    printf("\nDeque is full.\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("\nDeque is full.\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("\nDeque is empty.\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("\nDeque is empty.\n");
    return 0;
  }

  item = arr[*prear];
  arr[*prear] = 0;
  (*prear)--;
  if (*prear == -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;
}

// Deque implementation in C++

#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)。

双端队列数据结构的应用

在软件的撤销操作中。
在浏览器中存储历史记录。
用于实现栈和队列。

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python
程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

Deque 数据结构

双端队列的类型

双端队列的操作

1. 从前端插入

2. 从后端插入

3. 从前端删除

4. 从后端删除

5. 检查空

6. 检查满

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

时间复杂度

双端队列数据结构的应用

目录

热门教程

热门实例

参考资料

认证课程

成为一名认证的 Python程序员。

热门教程

参考资料

热门实例

DSA 简介

数据结构 (I)

数据结构 (II)

基于树的 DSA (I)

基于树的 DSA (II)

基于图的 DSA

排序和搜索算法

贪婪算法

动态规划

其他算法

DSA 教程

Deque 数据结构

双端队列的类型

双端队列的操作

1. 从前端插入

2. 从后端插入

3. 从前端删除

4. 从后端删除

5. 检查空

6. 检查满

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

时间复杂度

双端队列数据结构的应用

目录

相关教程

成为一名认证的 Python
程序员。