Implementation of Deque using doubly linked list | C ++ implementation of Deque using doubly linked list ; Node of a doubly linked list ; Function to get a new node ; A structure to represent a deque ; Operations on Deque ; Function to check whether deque is empty or not ; Function to return the number of elements in the deque ; Function to insert an element at the front end ; If true then new element cannot be added and it is an ' Overflow ' condition ; If deque is empty ; Inserts node at the front end ; Increments count of elements by 1 ; Function to insert an element at the rear end ; If true then new element cannot be added and it is an ' Overflow ' condition ; If deque is empty ; Inserts node at the rear end ; Function to delete the element from the front end ; If deque is empty then ' Underflow ' condition ; Deletes the node from the front end and makes the adjustment in the links ; If only one element was present ; Decrements count of elements by 1 ; Function to delete the element from the rear end ; If deque is empty then ' Underflow ' condition ; Deletes the node from the rear end and makes the adjustment in the links ; If only one element was present ; Decrements count of elements by 1 ; Function to return the element at the front end ; If deque is empty , then returns garbage value ; Function to return the element at the rear end ; If deque is empty , then returns garbage value ; Function to delete all the elements from Deque ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * prev , * next ; static Node * getnode ( int data ) { Node * newNode = ( Node * ) malloc ( sizeof ( Node ) ) ; newNode -> data = data ; newNode -> prev = newNode -> next = NULL ; return newNode ; } } ; class Deque { Node * front ; Node * rear ; int Size ; public : Deque ( ) { front = rear = NULL ; Size = 0 ; } void insertFront ( int data ) ; void insertRear ( int data ) ; void deleteFront ( ) ; void deleteRear ( ) ; int getFront ( ) ; int getRear ( ) ; int size ( ) ; bool isEmpty ( ) ; void erase ( ) ; } ; bool Deque :: isEmpty ( ) { return ( front == NULL ) ; } int Deque :: size ( ) { return Size ; } void Deque :: insertFront ( int data ) { Node * newNode = Node :: getnode ( data ) ; if ( newNode == NULL ) cout << " OverFlow STRNEWLINE " ; else { if ( front == NULL ) rear = front = newNode ; else { newNode -> next = front ; front -> prev = newNode ; front = newNode ; } Size ++ ; } } void Deque :: insertRear ( int data ) { Node * newNode = Node :: getnode ( data ) ; if ( newNode == NULL ) cout << " OverFlow STRNEWLINE " ; else { if ( rear == NULL ) front = rear = newNode ; else { newNode -> prev = rear ; rear -> next = newNode ; rear = newNode ; } Size ++ ; } } void Deque :: deleteFront ( ) { if ( isEmpty ( ) ) cout << " UnderFlow STRNEWLINE " ; else { Node * temp = front ; front = front -> next ; if ( front == NULL ) rear = NULL ; else front -> prev = NULL ; free ( temp ) ; Size -- ; } } void Deque :: deleteRear ( ) { if ( isEmpty ( ) ) cout << " UnderFlow STRNEWLINE " ; else { Node * temp = rear ; rear = rear -> prev ; if ( rear == NULL ) front = NULL ; else rear -> next = NULL ; free ( temp ) ; Size -- ; } } int Deque :: getFront ( ) { if ( isEmpty ( ) ) return -1 ; return front -> data ; } int Deque :: getRear ( ) { if ( isEmpty ( ) ) return -1 ; return rear -> data ; } void Deque :: erase ( ) { rear = NULL ; while ( front != NULL ) { Node * temp = front ; front = front -> next ; free ( temp ) ; } Size = 0 ; } int main ( ) { Deque dq ; cout << " Insert ▁ element ▁ ' 5 ' ▁ at ▁ rear ▁ end STRNEWLINE " ; dq . insertRear ( 5 ) ; cout << " Insert ▁ element ▁ ' 10 ' ▁ at ▁ rear ▁ end STRNEWLINE " ; 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 ▁ STRNEWLINE " ; 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 ; }