双端队列

/deque

在本教程中，您将学习什么是双端队列（双端队列）。另外，您还将找到在 C，C++ ，Java 和 Python 的双端队列上进行不同操作的工作示例。

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

Deque

双端队列

双端队列的类型

输入限制双端队列在此双端队列中，输入在一端限制，但允许在两端删除。
输出限制双端队列在此双端队列中，输出限制在一个端部，但允许在两端插入。

双端队列操作

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

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

在执行以下操作之前，请执行以下步骤。

取大小为n的数组。
在第一个位置设置两个指针，然后设置front = -1和rear = 0。

Initialize array

初始化数组和指针

在前面插入

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

检查前面的位置。

检查正面
如果为front < 1，请重新初始化front = n-1（最后一个索引）。

前端发送
否则，将front减小 1。
将新键5添加到array[front]中。

插入键

在后面插入

此操作在后部增加了一个元素。

检查数组是否已满。

检查完整的
如果数组已满，请重新初始化rear = 0。
否则，将rear增加 1。

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

插入键

从前面删除

该操作从前面删除一个元素。

检查数组是否为空。

检查为空
如果数组为空（即front = -1），则无法执行删除操作（下溢条件）。
如果双端队列只有一个元素（即front = rear），请设置front = -1和rear = -1。
否则，如果front位于末尾（即front = n - 1），则设置转到前front = 0。
否则，front = front + 1。

增加前线

从后面删除

此操作从背面删除一个元素。

检查数组是否为空。

检查为空
如果数组为空（即front = -1），则无法执行删除操作（下溢条件）。
如果双端队列只有一个元素（即front = rear），请设置front = -1和rear = -1，否则请按照以下步骤操作。
如果rear在前面（即rear = 0），则设置转到前rear = n - 1。
否则，rear = rear - 1。

降低后排

检查空

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

检查满

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

Python，Java 和 C/C++ 示例

# Deque operations in python

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

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

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

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

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

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

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

双端队列应用

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