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 , se discutió la implementación de Deque usando una array circular. Ahora, en esta publicación, vemos cómo implementamos Deque usando la lista doblemente enlazada .
Operaciones en Deque:
Principalmente, las siguientes cuatro operaciones básicas se realizan en la cola:
insertFront() : Adds an item at the front of Deque. insertRear() : Adds an item at the rear of Deque. deleteFront() : Deletes an item from front of Deque. deleteRear() : Deletes an item from rear of Deque.
Además de las operaciones anteriores, también se admiten las siguientes operaciones:
getFront() : Gets the front item from queue. getRear() : Gets the last item from queue. isEmpty() : Checks whether Deque is empty or not. size() : Gets number of elements in Deque. erase() : Deletes all the elements from Deque.
Representación de lista doblemente enlazada de Deque:
para implementar deque, necesitamos realizar un seguimiento de dos punteros, delantero y trasero . Ponemos en cola (empujamos) un elemento en la parte trasera o delantera de deque y sacamos de la cola (pop) un elemento tanto en la parte trasera como en la delantera.
Trabajo:
Declare dos punteros delante y detrás de tipo Node , donde Node representa la estructura de un Node de una lista doblemente enlazada. Inicialice ambos con valor NULL.
Inserción en la parte delantera:
1. Allocate space for a newNode of doubly linked list. 2. IF newNode == NULL, then 3. print "Overflow" 4. ELSE 5. IF front == NULL, then 6. rear = front = newNode 7. ELSE 8. newNode->next = front 9. front->prev = newNode 10. front = newNode
Inserción en el extremo trasero:
1. Allocate space for a newNode of doubly linked list. 2. IF newNode == NULL, then 3. print "Overflow" 4. ELSE 5. IF rear == NULL, then 6. front = rear = newNode 7. ELSE 8. newNode->prev = rear 9. rear->next = newNode 10. rear = newNode
Eliminación de Front-end:
1. IF front == NULL 2. print "Underflow" 3. ELSE 4. Initialize temp = front 5. front = front->next 6. IF front == NULL 7. rear = NULL 8. ELSE 9. front->prev = NULL 10 Deallocate space for temp
Eliminación de la parte trasera:
1. IF front == NULL 2. print "Underflow" 3. ELSE 4. Initialize temp = rear 5. rear = rear->prev 6. IF rear == NULL 7. front = NULL 8. ELSE 9. rear->next = NULL 10 Deallocate space for temp
Implementación:
CPP
// C++ implementation of Deque using
// doubly linked list
#include <bits/stdc++.h>
using namespace std;
// Node of a doubly linked list
struct Node
{
int data;
Node *prev, *next;
// Function to get a new node
static Node* getnode(int data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = newNode->next = NULL;
return newNode;
}
};
// A structure to represent a deque
class Deque
{
Node* front;
Node* rear;
int Size;
public:
Deque()
{
front = rear = NULL;
Size = 0;
}
// Operations on Deque
void insertFront(int data);
void insertRear(int data);
void deleteFront();
void deleteRear();
int getFront();
int getRear();
int size();
bool isEmpty();
void erase();
};
// Function to check whether deque
// is empty or not
bool Deque::isEmpty()
{
return (front == NULL);
}
// Function to return the number of
// elements in the deque
int Deque::size()
{
return Size;
}
// Function to insert an element
// at the front end
void Deque::insertFront(int data)
{
Node* newNode = Node::getnode(data);
// If true then new element cannot be added
// and it is an 'Overflow' condition
if (newNode == NULL)
cout << "OverFlow\n";
else
{
// If deque is empty
if (front == NULL)
rear = front = newNode;
// Inserts node at the front end
else
{
newNode->next = front;
front->prev = newNode;
front = newNode;
}
// Increments count of elements by 1
Size++;
}
}
// Function to insert an element
// at the rear end
void Deque::insertRear(int data)
{
Node* newNode = Node::getnode(data);
// If true then new element cannot be added
// and it is an 'Overflow' condition
if (newNode == NULL)
cout << "OverFlow\n";
else
{
// If deque is empty
if (rear == NULL)
front = rear = newNode;
// Inserts node at the rear end
else
{
newNode->prev = rear;
rear->next = newNode;
rear = newNode;
}
Size++;
}
}
// Function to delete the element
// from the front end
void Deque::deleteFront()
{
// If deque is empty then
// 'Underflow' condition
if (isEmpty())
cout << "UnderFlow\n";
// Deletes the node from the front end and makes
// the adjustment in the links
else
{
Node* temp = front;
front = front->next;
// If only one element was present
if (front == NULL)
rear = NULL;
else
front->prev = NULL;
free(temp);
// Decrements count of elements by 1
Size--;
}
}
// Function to delete the element
// from the rear end
void Deque::deleteRear()
{
// If deque is empty then
// 'Underflow' condition
if (isEmpty())
cout << "UnderFlow\n";
// Deletes the node from the rear end and makes
// the adjustment in the links
else
{
Node* temp = rear;
rear = rear->prev;
// If only one element was present
if (rear == NULL)
front = NULL;
else
rear->next = NULL;
free(temp);
// Decrements count of elements by 1
Size--;
}
}
// Function to return the element
// at the front end
int Deque::getFront()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return front->data;
}
// Function to return the element
// at the rear end
int Deque::getRear()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return rear->data;
}
// Function to delete all the elements
// from Deque
void Deque::erase()
{
rear = NULL;
while (front != NULL)
{
Node* temp = front;
front = front->next;
free(temp);
}
Size = 0;
}
// Driver program to test above
int main()
{
Deque dq;
cout << "Insert element '5' at rear end\n";
dq.insertRear(5);
cout << "Insert element '10' at rear end\n";
dq.insertRear(10);
cout << "Rear end element: "
<< dq.getRear() << endl;
dq.deleteRear();
cout << "After deleting rear element new rear"
<< " is: " << dq.getRear() << endl;
cout << "Inserting element '15' at front end \n";
dq.insertFront(15);
cout << "Front end element: "
<< dq.getFront() << endl;
cout << "Number of elements in Deque: "
<< dq.size() << endl;
dq.deleteFront();
cout << "After deleting front element new "
<< "front is: " << dq.getFront() << endl;
return 0;
}
Java
// Java implementation of Deque using
// doubly linked list
import java.util.*;
class GFG
{
// Node of a doubly linked list
static class Node
{
int data;
Node prev, next;
// Function to get a new node
static Node getnode(int data)
{
Node newNode = new Node();
newNode.data = data;
newNode.prev = newNode.next = null;
return newNode;
}
};
// A structure to represent a deque
static class Deque {
Node front;
Node rear;
int Size;
Deque()
{
front = rear = null;
Size = 0;
}
// Function to check whether deque
// is empty or not
boolean isEmpty() { return (front == null); }
// Function to return the number of
// elements in the deque
int size() { return Size; }
// Function to insert an element
// at the front end
void insertFront(int data)
{
Node newNode = Node.getnode(data);
// If true then new element cannot be added
// and it is an 'Overflow' condition
if (newNode == null)
System.out.print("OverFlow\n");
else {
// If deque is empty
if (front == null)
rear = front = newNode;
// Inserts node at the front end
else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
// Increments count of elements by 1
Size++;
}
}
// Function to insert an element
// at the rear end
void insertRear(int data)
{
Node newNode = Node.getnode(data);
// If true then new element cannot be added
// and it is an 'Overflow' condition
if (newNode == null)
System.out.print("OverFlow\n");
else {
// If deque is empty
if (rear == null)
front = rear = newNode;
// Inserts node at the rear end
else {
newNode.prev = rear;
rear.next = newNode;
rear = newNode;
}
Size++;
}
}
// Function to delete the element
// from the front end
void deleteFront()
{
// If deque is empty then
// 'Underflow' condition
if (isEmpty())
System.out.print("UnderFlow\n");
// Deletes the node from the front end and makes
// the adjustment in the links
else {
Node temp = front;
front = front.next;
// If only one element was present
if (front == null)
rear = null;
else
front.prev = null;
// Decrements count of elements by 1
Size--;
}
}
// Function to delete the element
// from the rear end
void deleteRear()
{
// If deque is empty then
// 'Underflow' condition
if (isEmpty())
System.out.print("UnderFlow\n");
// Deletes the node from the rear end and makes
// the adjustment in the links
else {
Node temp = rear;
rear = rear.prev;
// If only one element was present
if (rear == null)
front = null;
else
rear.next = null;
// Decrements count of elements by 1
Size--;
}
}
// Function to return the element
// at the front end
int getFront()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return front.data;
}
// Function to return the element
// at the rear end
int getRear()
{
// If deque is empty, then returns
// garbage value
if (isEmpty())
return -1;
return rear.data;
}
// Function to delete all the elements
// from Deque
void erase()
{
rear = null;
while (front != null) {
Node temp = front;
front = front.next;
}
Size = 0;
}
}
// Driver program to test above
public static void main(String[] args)
{
Deque dq = new Deque();
System.out.print(
"Insert element '5' at rear end\n");
dq.insertRear(5);
System.out.print(
"Insert element '10' at rear end\n");
dq.insertRear(10);
System.out.print("Rear end element: " + dq.getRear()
+ "\n");
dq.deleteRear();
System.out.print(
"After deleting rear element new rear"
+ " is: " + dq.getRear() + "\n");
System.out.print(
"Inserting element '15' at front end \n");
dq.insertFront(15);
System.out.print(
"Front end element: " + dq.getFront() + "\n");
System.out.print("Number of elements in Deque: "
+ dq.size() + "\n");
dq.deleteFront();
System.out.print("After deleting front element new "
+ "front is: " + dq.getFront()
+ "\n");
}
}
// This code is contributed by gauravrajput1
Producción
Insert element '5' at rear end Insert element '10' at rear end Rear end element: 10 After deleting rear element new rear is: 5 Inserting element '15' at front end Front end element: 15 Number of elements in Deque: 2 After deleting front element new front is: 5
Análisis de Complejidad:
- Complejidad de tiempo: la complejidad de tiempo de operaciones como insertFront() , insertRear() , deleteFront() , deleteRear() es O(1) . La complejidad temporal de erase() es O(n) .
- Complejidad espacial: O(n) , en el peor de los casos n Nodes que se insertarán en el deque.
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA