Deque o Double Ended Queue es una versión generalizada de la estructura de datos de Queue que permite insertar y eliminar en ambos extremos. En una publicación anterior, discutimos la introducción de deque. Ahora, en esta publicación, vemos cómo implementamos deque usando una array circular.
Operaciones en Deque:
Principalmente, las siguientes cuatro operaciones básicas se realizan en la cola:
- insertFront() : Agrega un elemento al frente de Deque.
- insertRear() : Agrega un elemento en la parte posterior de Deque.
- deleteFront() : Elimina un elemento del frente de Deque.
- deleteRear() : Elimina un elemento de la parte posterior de Deque.
Además de las operaciones anteriores, también se admiten las siguientes operaciones
- getFront() : Obtiene el elemento frontal de la cola.
- getRear() : Obtiene el último elemento de la cola.
- isEmpty() : Comprueba si Deque está vacío o no.
- isFull() : Comprueba si Deque está lleno o no.
Deque de implementación de array circular
Para implementar deque, necesitamos realizar un seguimiento de dos índices, delantero y trasero. Ponemos en cola (empujamos) un elemento en la parte trasera o delantera de la cola y sacamos de la cola (pop) un elemento tanto en la parte trasera como en la delantera.
Laboral :
Cree una array vacía ‘arr’ de tamaño ‘n’
initialize front = -1 , rear = 0
Insertar el primer elemento en deque, ya sea en la parte delantera o trasera, dará el mismo resultado.
Después de insertar Puntos delanteros = 0 y Puntos traseros = 0
Insertar elementos en el extremo trasero
a). First we check deque if Full or Not b). IF Rear == Size-1 then reinitialize Rear = 0 ; Else increment Rear by '1' and push current key into Arr[ rear ] = key Front remain same.
Insertar elementos en el extremo frontal
a). First we check deque if Full or Not b). IF Front == 0 || initial position, move Front to points last index of array front = size - 1 Else decremented front by '1' and push current key into Arr[ Front] = key Rear remain same.
Eliminar elemento de la parte trasera
a). first Check deque is Empty or Not b). If deque has only one element front = -1 ; rear =-1 ; Else IF Rear points to the first index of array it's means we have to move rear to points last index [ now first inserted element at front end become rear end ] rear = size-1 ; Else || decrease rear by '1' rear = rear-1;
Eliminar elemento del front-end
a). first Check deque is Empty or Not b). If deque has only one element front = -1 ; rear =-1 ; Else IF front points to the last index of the array it's means we have no more elements in array so we move front to points first index of array front = 0 ; Else || increment Front by '1' front = front+1;
A continuación se muestra la implementación de la idea anterior.
C++
// C++ implementation of De-queue using circular // array #include<iostream> using namespace std; // Maximum size of array or Dequeue #define MAX 100 // A structure to represent a Deque class Deque { int arr[MAX]; int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); }; // Checks whether Deque is full or not. bool Deque::isFull() { return ((front == 0 && rear == size-1)|| front == rear+1); } // Checks whether Deque is empty or not. bool Deque::isEmpty () { return (front == -1); } // Inserts an element at front void Deque::insertfront(int key) { // check whether Deque if full or not if (isFull()) { cout << "Overflow\n" << endl; return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // front is at first position of queue else if (front == 0) front = size - 1 ; else // decrement front end by '1' front = front-1; // insert current element into Deque arr[front] = key ; } // function to inset element at rear end // of Deque. void Deque ::insertrear(int key) { if (isFull()) { cout << " Overflow\n " << endl; return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // rear is at last position of queue else if (rear == size-1) rear = 0; // increment rear end by '1' else rear = rear+1; // insert current element into Deque arr[rear] = key ; } // Deletes element at front end of Deque void Deque ::deletefront() { // check whether Deque is empty or not if (isEmpty()) { cout << "Queue Underflow\n" << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // increment front by '1' to remove current // front value from Deque front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << " Underflow\n" << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // Returns front element of Deque int Deque::getFront() { // check whether Deque is empty or not if (isEmpty()) { cout << " Underflow\n" << endl; return -1 ; } return arr[front]; } // function return rear element of Deque int Deque::getRear() { // check whether Deque is empty or not if(isEmpty() || rear < 0) { cout << " Underflow\n" << endl; return -1 ; } return arr[rear]; } // Driver program to test above function int main() { Deque dq(5); cout << "Insert element at rear end : 5 \n"; dq.insertrear(5); cout << "insert element at rear end : 10 \n"; dq.insertrear(10); cout << "get rear element " << " " << dq.getRear() << endl; dq.deleterear(); cout << "After delete rear element new rear" << " become " << dq.getRear() << endl; cout << "inserting element at front end \n"; dq.insertfront(15); cout << "get front element " << " " << dq.getFront() << endl; dq.deletefront(); cout << "After delete front element new " << "front become " << dq.getFront() << endl; return 0; }
Java
// Java implementation of De-queue using circular // array // A structure to represent a Deque 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; } /*// Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear();*/ // Checks whether Deque is full or not. boolean isFull() { return ((front == 0 && rear == size-1)|| front == rear+1); } // Checks whether Deque is empty or not. boolean isEmpty () { return (front == -1); } // Inserts an element at front void insertfront(int key) { // check whether Deque if full or not if (isFull()) { System.out.println("Overflow"); return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // front is at first position of queue else if (front == 0) front = size - 1 ; else // decrement front end by '1' front = front-1; // insert current element into Deque arr[front] = key ; } // function to inset element at rear end // of Deque. void insertrear(int key) { if (isFull()) { System.out.println(" Overflow "); return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // rear is at last position of queue else if (rear == size-1) rear = 0; // increment rear end by '1' else rear = rear+1; // insert current element into Deque arr[rear] = key ; } // Deletes element at front end of Deque void deletefront() { // check whether Deque is empty or not if (isEmpty()) { System.out.println("Queue Underflow\n"); return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // increment front by '1' to remove current // front value from Deque front = front+1; } // Delete element at rear end of Deque void deleterear() { if (isEmpty()) { System.out.println(" Underflow"); return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // Returns front element of Deque int getFront() { // check whether Deque is empty or not if (isEmpty()) { System.out.println(" Underflow"); return -1 ; } return arr[front]; } // function return rear element of Deque int getRear() { // check whether Deque is empty or not if(isEmpty() || rear < 0) { System.out.println(" Underflow\n"); return -1 ; } return arr[rear]; } // Driver program to test above function public static void main(String[] args) { Deque dq = new Deque(5); System.out.println("Insert element at rear end : 5 "); dq.insertrear(5); System.out.println("insert element at rear end : 10 "); dq.insertrear(10); 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(15); System.out.println("get front element: " +dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + + dq.getFront()); } }
Python3
# Python implementation of De-queue using circular # array # A structure to represent a Deque MAX = 100; class Deque: def __init__(self, size): self.arr = [0] * MAX self.front = -1; self.rear = 0; self.size = size; ''' Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ''' # Checks whether Deque is full or not. def isFull(self): return ((self.front == 0 and self.rear == self.size-1) or self.front == self.rear + 1) # Checks whether Deque is empty or not. def isEmpty (self): return (self.front == -1); # Inserts an element at front def insertfront(self, key): # check whether Deque if full or not if (self.isFull()): print("Overflow"); return; # If queue is initially empty if (self.front == -1): self.front = 0; self.rear = 0; # front is at first position of queue elif (self.front == 0): self.front = self.size - 1 ; else: # decrement front end by '1' self.front = self.front-1; # insert current element into Deque self.arr[self.front] = key ; # function to inset element at rear end # of Deque. def insertrear(self, key): if (self.isFull()): print(" Overflow"); return; # If queue is initially empty if (self.front == -1): self.front = 0; self.rear = 0; # rear is at last position of queue elif (self.rear == self.size-1): self.rear = 0; # increment rear end by '1' else: self.rear = self.rear+1; # insert current element into Deque self.arr[self.rear] = key ; # Deletes element at front end of Deque def deletefront(self): # check whether Deque is empty or not if (self.isEmpty()): print("Queue Underflow"); return ; # Deque has only one element if (self.front == self.rear): self.front = -1; self.rear = -1; else: # back to initial position if (self.front == self.size -1): self.front = 0; else: # increment front by '1' to remove current # front value from Deque self.front = self.front+1; # Delete element at rear end of Deque def deleterear(self): if (self.isEmpty()): print(" Underflow"); return ; # Deque has only one element if (self.front == self.rear): self.front = -1; self.rear = -1; elif (self.rear == 0): self.rear = self.size-1; else: self.rear = self.rear-1; # Returns front element of Deque def getFront(self): # check whether Deque is empty or not if (self.isEmpty()): print(" Underflow"); return -1 ; return self.arr[self.front]; # function return rear element of Deque def getRear(self): # check whether Deque is empty or not if(self.isEmpty() or self.rear < 0): print(" Underflow"); return -1 ; return self.arr[self.rear]; # Driver program to test above function dq = Deque(5); print("Insert element at rear end : 5 "); dq.insertrear(5); print("insert element at rear end : 10 "); dq.insertrear(10); print(f"get rear element : {dq.getRear()}"); dq.deleterear(); print(f"After delete rear element new rear become : {dq.getRear()}"); print("inserting element at front end"); dq.insertfront(15); print(f"get front element: {dq.getFront()}"); dq.deletefront(); print(f"After delete front element new front become : {dq.getFront()}"); # This code is contributed by _saurabh_jaiswal
C#
// C# implementation of De-queue using circular // array using System; // A structure to represent a Deque public class Deque { static readonly 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; } /*// Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool .Count!=0; int getFront(); int getRear();*/ // Checks whether Deque is full or not. bool isFull() { return ((front == 0 && rear == size - 1)|| front == rear + 1); } // Checks whether Deque is empty or not. bool isEmpty () { return (front == -1); } // Inserts an element at front void insertfront(int key) { // check whether Deque if full or not if (isFull()) { Console.WriteLine("Overflow"); return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // front is at first position of queue else if (front == 0) front = size - 1 ; else // decrement front end by '1' front = front - 1; // insert current element into Deque arr[front] = key ; } // function to inset element at rear end // of Deque. void insertrear(int key) { if (isFull()) { Console.WriteLine(" Overflow "); return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // rear is at last position of queue else if (rear == size - 1) rear = 0; // increment rear end by '1' else rear = rear+1; // insert current element into Deque arr[rear] = key ; } // Deletes element at front end of Deque void deletefront() { // check whether Deque is empty or not if (isEmpty()) { Console.WriteLine("Queue Underflow\n"); return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size - 1) front = 0; else // increment front by '1' to remove current // front value from Deque front = front + 1; } // Delete element at rear end of Deque void deleterear() { if (isEmpty()) { Console.WriteLine(" Underflow"); return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size - 1; else rear = rear - 1; } // Returns front element of Deque int getFront() { // check whether Deque is empty or not if (isEmpty()) { Console.WriteLine(" Underflow"); return -1 ; } return arr[front]; } // function return rear element of Deque int getRear() { // check whether Deque is empty or not if (isEmpty() || rear < 0) { Console.WriteLine(" Underflow\n"); return -1 ; } return arr[rear]; } // Driver code public static void Main(String[] args) { Deque dq = new Deque(5); Console.WriteLine("Insert element at rear end : 5 "); dq.insertrear(5); Console.WriteLine("insert element at rear end : 10 "); dq.insertrear(10); Console.WriteLine("get rear element : "+ dq.getRear()); dq.deleterear(); Console.WriteLine("After delete rear element new rear become : " + dq.getRear()); Console.WriteLine("inserting element at front end"); dq.insertfront(15); Console.WriteLine("get front element: " +dq.getFront()); dq.deletefront(); Console.WriteLine("After delete front element new front become : " + + dq.getFront()); } } // This code is contributed by aashish1995
Javascript
<script> // Javascript implementation of De-queue using circular // array // A structure to represent a Deque let MAX = 100; class Deque { constructor(size) { this.arr = new Array(MAX); this.front = -1; this.rear = 0; this.size = size; } /*// Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear();*/ // Checks whether Deque is full or not. isFull() { return ((this.front == 0 && this.rear == this.size-1)|| this.front == this.rear+1); } // Checks whether Deque is empty or not. isEmpty () { return (this.front == -1); } // Inserts an element at front insertfront(key) { // check whether Deque if full or not if (this.isFull()) { document.write("Overflow<br>"); return; } // If queue is initially empty if (this.front == -1) { this.front = 0; this.rear = 0; } // front is at first position of queue else if (this.front == 0) this.front = this.size - 1 ; else // decrement front end by '1' this.front = this.front-1; // insert current element into Deque this.arr[this.front] = key ; } // function to inset element at rear end // of Deque. insertrear(key) { if (this.isFull()) { document.write(" Overflow <br>"); return; } // If queue is initially empty if (this.front == -1) { this.front = 0; this.rear = 0; } // rear is at last position of queue else if (this.rear == this.size-1) this.rear = 0; // increment rear end by '1' else this.rear = this.rear+1; // insert current element into Deque this.arr[this.rear] = key ; } // Deletes element at front end of Deque deletefront() { // check whether Deque is empty or not if (this.isEmpty()) { document.write("Queue Underflow<br>"); return ; } // Deque has only one element if (this.front == this.rear) { this.front = -1; this.rear = -1; } else // back to initial position if (this.front == this.size -1) this.front = 0; else // increment front by '1' to remove current // front value from Deque this.front = this.front+1; } // Delete element at rear end of Deque deleterear() { if (this.isEmpty()) { document.write(" Underflow<br>"); return ; } // Deque has only one element if (this.front == this.rear) { this.front = -1; this.rear = -1; } else if (this.rear == 0) this.rear = this.size-1; else this.rear = this.rear-1; } // Returns front element of Deque getFront() { // check whether Deque is empty or not if (this.isEmpty()) { document.write(" Underflow<br>"); return -1 ; } return this.arr[this.front]; } // function return rear element of Deque getRear() { // check whether Deque is empty or not if(this.isEmpty() || this.rear < 0) { document.write(" Underflow<br>"); return -1 ; } return this.arr[this.rear]; } } // Driver program to test above function let dq = new Deque(5); document.write("Insert element at rear end : 5 <br>"); dq.insertrear(5); document.write("insert element at rear end : 10 <br>"); dq.insertrear(10); document.write("get rear element : "+ dq.getRear()+"<br>"); dq.deleterear(); document.write("After delete rear element new rear become : " + dq.getRear()+"<br>"); document.write("inserting element at front end<br>"); dq.insertfront(15); document.write("get front element: " +dq.getFront()+"<br>"); dq.deletefront(); document.write("After delete front element new front become : " + + dq.getFront()+"<br>"); // This code is contributed by avanitrachhadiya2155 </script>
Insert element at rear end : 5 insert element at rear end : 10 get rear element 10 After delete rear element new rear become 5 inserting element at front end get front element 15 After delete front element new front become 5
Complejidad de tiempo: la complejidad de tiempo de todas las operaciones como insertfront(), insertlast(), deletefront(), deletelast()is O(1) .
En la próxima publicación, discutiremos la implementación de deque utilizando la lista doblemente enlazada.
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA