An input restricted queue is a special case of a double-ended queue where data can be inserted from one end(rear) but can be removed from both ends (front and rear). This kind of Queue does not follow FIFO(first in first out):
Operations on Input Restricted Queue:
Mainly the following three basic operations are performed on input restricted queue:
- insertRear(): Adds an item at the rear of the queue.
- deleteFront(): Deletes an item from the front of the queue.
- deleteRear(): Deletes an item from rear of the queue.
In addition to above operations, following operations are also supported
- getFront(): Gets the front item from the queue.
- getRear(): Gets the last item from the queue.
- isEmpty(): Checks whether queue is empty or not.
- isFull(): Checks whether queue is full or not.
Below is the implementation of Input restricted queue:
C++
// C++ implementation of Input Restricted // Queue using circular array #include <iostream> using namespace std; // Maximum size of array or Input // Restricted Queue #define MAX 100 // A structure to represent a Input // Restricted Queue class Deque { int arr[MAX]; int front; int rear; int size; public : Deque( int size) { front = -1; rear = 0; this ->size = size; } // Operations on Input // Restricted Queue void insertrear( int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); }; // Checks whether Input Restricted // Queue is full or not. bool Deque::isFull() { return ((front == 0 && rear == size - 1) || front == rear + 1); } // Checks whether Input Restricted // Queue is empty or not. bool Deque::isEmpty() { return (front == -1); } // function to inset element at rear end // of Input Restricted Queue 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 // Input Restricted Queue 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 // Input Restricted Queue 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 Input // Restricted Queue 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 // Input Restricted Queue int Deque::getRear() { // Check whether Deque is empty // or not if (isEmpty() || rear < 0) { cout << " Underflow\n" << endl; return -1; } return arr[rear]; } // Driver code int main() { Deque dq(5); // Function calls cout << "Insert element at rear end : 5 \n" ; dq.insertrear(5); cout << "insert element at rear end : 10 \n" ; dq.insertrear(10); cout << "insert element at rear end : 15 \n" ; dq.insertrear(15); cout << "Get rear element : " << " " << dq.getRear() << endl; dq.deleterear(); cout << "After delete rear element new rear" << " become : " << dq.getRear() << endl; cout << "Get front element : " << dq.getFront() << endl; dq.deletefront(); cout << "After delete front element new " << "front become : " << dq.getFront() << endl; return 0; } |
Java
// Java program for the above approach // Queue using circular array // A structure to represent a Input // Restricted Queue class Deque { int [] arr; int front; int rear; int size; public Deque( int size) { this .size = size; arr = new int [size]; front = - 1 ; rear = 0 ; } // Operations on Input // Restricted Queue // Checks whether Input Restricted // Queue is full or not. public boolean isFull() { return (front == 0 && rear == size - 1 ) || front == rear + 1 ; } // Checks whether Input Restricted // Queue is empty or not. public boolean isEmpty() { return front == - 1 ; } // function to inset element at rear end // of Input Restricted Queue public 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++; } arr[rear] = key; } // Deletes element at front end of // Input Restricted Queue public void deleteFront() { if (isEmpty()) { System.out.println( "Queue Underflow" ); return ; } if (front == rear) { front = - 1 ; rear = - 1 ; } else if (front == size - 1 ) { front = 0 ; } else { front++; } } // Delete element at rear end of // Input Restricted Queue public 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--; } } // Returns front element of Input // Restricted Queue public int getFront() { if (isEmpty()) { System.out.println( " Underflow" ); return - 1 ; } return arr[front]; } // Function return rear element of // Input Restricted Queue public int getRear() { if (isEmpty() || rear < 0 ) { System.out.println( " Underflow" ); return - 1 ; } return arr[rear]; } // Driver code public static void main(String[] args) { Deque dq = new Deque( 5 ); // Function calls 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( "Insert element at rear end : 15 " ); dq.insertRear( 15 ); 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( "Get front element : " + dq.getFront()); dq.deleteFront(); System.out.println( "After delete front element new front become :" + dq.getFront()); } } |
C#
// C# program for the above approach // Queue using circular array using System; // A structure to represent a Input // Restricted Queue public class Deque { int [] arr; int front; int rear; int size; public Deque( int size) { this .size = size; arr = new int [size]; front = -1; rear = 0; } // Operations on Input // Restricted Queue // Checks whether Input Restricted // Queue is full or not. public bool isFull() { return (front == 0 && rear == size - 1) || front == rear + 1; } // Checks whether Input Restricted // Queue is empty or not. public bool isEmpty() { return front == -1; } // function to inset element at rear end // of Input Restricted Queue public void insertRear( int key) { if (isFull()) { Console.WriteLine( " Overflow" ); return ; } if (front == -1) { front = 0; rear = 0; } else if (rear == size - 1) { rear = 0; } else { rear++; } arr[rear] = key; } // Deletes element at front end of // Input Restricted Queue public void deleteFront() { if (isEmpty()) { Console.WriteLine( "Queue Underflow" ); return ; } if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) { front = 0; } else { front++; } } // Delete element at rear end of // Input Restricted Queue public void deleteRear() { if (isEmpty()) { Console.WriteLine( " Underflow" ); return ; } if (front == rear) { front = -1; rear = -1; } else if (rear == 0) { rear = size - 1; } else { rear--; } } // Returns front element of Input // Restricted Queue public int getFront() { if (isEmpty()) { Console.WriteLine( " Underflow" ); return -1; } return arr[front]; } // Function return rear element of // Input Restricted Queue public int getRear() { if (isEmpty() || rear < 0) { Console.WriteLine( " Underflow" ); return -1; } return arr[rear]; } static public void Main() { // Code Deque dq = new Deque(5); // Function calls Console.WriteLine( "Insert element at rear end : 5 " ); dq.insertRear(5); Console.WriteLine( "Insert element at rear end : 10 " ); dq.insertRear(10); Console.WriteLine( "Insert element at rear end : 15 " ); dq.insertRear(15); Console.WriteLine( "Get rear element : " + dq.getRear()); dq.deleteRear(); Console.WriteLine( "After delete rear element new rear become : " + dq.getRear()); 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 lokesh. |
Python3
class Deque: def __init__( self , size): self .size = size self .arr = [ 0 ] * size self .front = - 1 self .rear = 0 def is_full( self ): return ( self .front = = 0 and self .rear = = self .size - 1 ) or self .front = = self .rear + 1 def is_empty( self ): return self .front = = - 1 def insert_rear( self , key): if self .is_full(): print ( "Overflow" ) return if self .front = = - 1 : self .front = 0 self .rear = 0 elif self .rear = = self .size - 1 : self .rear = 0 else : self .rear + = 1 self .arr[ self .rear] = key def delete_front( self ): if self .is_empty(): print ( "Queue Underflow" ) return if self .front = = self .rear: self .front = - 1 self .rear = - 1 elif self .front = = self .size - 1 : self .front = 0 else : self .front + = 1 def delete_rear( self ): if self .is_empty(): print ( "Underflow" ) return if self .front = = self .rear: self .front = - 1 self .rear = - 1 elif self .rear = = 0 : self .rear = self .size - 1 else : self .rear - = 1 def get_front( self ): if self .is_empty(): print ( "Underflow" ) return - 1 return self .arr[ self .front] def get_rear( self ): if self .is_empty() or self .rear < 0 : print ( "Underflow" ) return - 1 return self .arr[ self .rear] if __name__ = = "__main__" : dq = Deque( 5 ) print ( "Insert element at rear end : 5 " ) dq.insert_rear( 5 ) print ( "Insert element at rear end : 10 " ) dq.insert_rear( 10 ) print ( "Insert element at rear end : 15 " ) dq.insert_rear( 15 ) print ( "Get rear element : " , dq.get_rear()) dq.delete_rear() print ( "After delete rear element new rear become : " , dq.get_rear()) print ( "Get front element : " , dq.get_front()) dq.delete_front() print ( "After delete front element new front become : " , dq.get_front()) |
Javascript
// JavaScript program for the above approach // Queue using circular array // A structure to represent a Input // Restricted Queue class Deque { constructor(size) { this .arr = new Array(size); this .front = -1; this .rear = 0; this .size = size; } // Operations on Input // Restricted Queue // Checks whether Input Restricted // Queue is full or not. isFull() { return ( this .front === 0 && this .rear === this .size - 1) || this .front === this .rear + 1; } // Checks whether Input Restricted // Queue is empty or not. isEmpty() { return this .front === -1; } // function to inset element at rear end // of Input Restricted Queue insertrear(key) { if ( this .isFull()) { console.log( "Overflow" ); return ; } if ( this .front === -1) { this .front = 0; this .rear = 0; } else if ( this .rear === this .size - 1) { this .rear = 0; } else { this .rear = this .rear + 1; } this .arr[ this .rear] = key; } // Deletes element at front end of // Input Restricted Queue deletefront() { if ( this .isEmpty()) { console.log( "Queue Underflow" ); return ; } if ( this .front === this .rear) { this .front = -1; this .rear = -1; } else if ( this .front === this .size - 1) { this .front = 0; } else { this .front = this .front + 1; } } // Delete element at rear end of // Input Restricted Queue deleterear() { if ( this .isEmpty()) { console.log( "Underflow" ); return ; } 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 Input // Restricted Queue getFront() { if ( this .isEmpty()) { console.log( "Underflow" ); return -1; } return this .arr[ this .front]; } // Function return rear element of // Input Restricted Queue getRear() { if ( this .isEmpty() || this .rear < 0) { console.log( "Underflow" ); return -1; } return this .arr[ this .rear]; } } // Driver code // Function calls const dq = new Deque(5); console.log( "Insert element at rear end : 5" ); dq.insertrear(5); console.log( "Insert element at rear end : 10" ); dq.insertrear(10); console.log( "Insert element at rear end : 15" ); dq.insertrear(15); console.log( "Get rear element : " , dq.getRear()); dq.deleterear(); console.log( "After delete rear element new rear become : " , dq.getRear()); console.log( "Get front element : " , dq.getFront()); dq.deletefront(); console.log( "After delete front element new front become : " , dq.getFront()); // This code is contributed by Prasad Kandekar(prasad264) |
Insert element at rear end : 5 insert element at rear end : 10 insert element at rear end : 15 Get rear element : 15 After delete rear element new rear become : 10 Get front element : 5 After delete front element new front become : 10
Time Complexity: O(N)
Auxiliary Space: O(N)
Need to implement input restricted queue:
- This queue is used when it is necessary to consume data in FIFO order but it is necessary to discard recently added data for a variety of reasons, such as useless data, performance issues, etc.
- It is needed when we have to inhibit insertion from the front of the deque.
- It is used in job scheduling algorithms.
Advantages of Input Restricted Queue:
- Security of the system by restricting the insert method of the queue at the front.
Disadvantages of Input Restricted Queue:
- Can’t provide the added functionality in comparison to Deque.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!