Most efficient ways to implement a Stack and Queue
1) Using Double-Ended Queue:
- One of the most efficient ways to implement both a stack and a queue together is to use a deque (double-ended queue) data structure. A deque is a generalization of a queue that allows elements to be added and removed from both ends, making it a suitable data structure for implementing both a stack and a queue.
- In C++, the deque is implemented as a container in the Standard Template Library (STL). It provides a convenient way to implement a stack and a queue using a single data structure.
- To implement a stack, you can push elements to the front of the deque using the insertfront() method, and pop elements from the front of the deque using the deletefront() method. This ensures that the most recently added element is always at the front of the deque, which is similar to the behavior of a stack.
- To implement a queue, you can enqueue elements to the back of the deque using the insertrear() method, and dequeue elements from the front of the deque using the deletefront() method. This ensures that the first element added to the deque is always the first to be removed, which is similar to the behavior of a queue.
Here’s an example of how to use a deque to implement a stack and a queue in C++:
C++
// C++ implementation of De-queue using // circular array #include <bits/stdc++.h> 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; // Decrement front end by '1' else 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; // Increment front by '1' to remove // current front value from Deque else 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 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 << "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 : 15 \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
// C++ implementation of De-queue using // circular array class Deque{ int front; int rear; int size; int [] arr; public Deque( int size){ front = - 1 ; rear = 0 ; this .size = size; arr = new int [size]; } // Checks whether Deque is full or not. public boolean isFull(){ return ((front == 0 && rear == size - 1 ) || front == rear + 1 ); } // Checks whether Deque is empty or not. public boolean isEmpty(){ return (front == - 1 ); } // Inserts an element at front public 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 ; // Decrement front end by '1' else front = front - 1 ; // Insert current element into Deque arr[front] = key; } // Function to insert element at rear end of Deque. public void insertrear( 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 ; } // 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 public void deletefront(){ if (isEmpty()) { System.out.println( "Queue Underflow" ); return ; } // Deque has only one element if (front == rear) { front = - 1 ; rear = - 1 ; } // Back to initial position else if (front == size - 1 ) front = 0 ; // Increment front by '1' to remove // current front value from Deque else front = front + 1 ; } // Delete element at rear end of Deque public 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 public 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 public int getRear(){ // Check whether Deque is empty or not if (isEmpty() || rear < 0 ) { System.out.println( " Underflow" ); return - 1 ; } return arr[rear]; } 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( "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 : 15 " ); 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 class Deque: def __init__( self , size): self .arr = [ 0 ] * size self .front = - 1 self .rear = 0 self .size = size def isFull( self ): return ( self .front = = 0 and self .rear = = self .size - 1 ) or self .front = = self .rear + 1 def isEmpty( self ): return self .front = = - 1 def insertfront( self , key): if self .isFull(): print ( "Overflow" ) return if self .front = = - 1 : self .front = 0 self .rear = 0 elif self .front = = 0 : self .front = self .size - 1 else : self .front - = 1 self .arr[ self .front] = key def insertrear( self , key): if self .isFull(): 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 deletefront( self ): if self .isEmpty(): 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 deleterear( self ): if self .isEmpty(): 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 getFront( self ): if self .isEmpty(): print ( "Underflow" ) return - 1 return self .arr[ self .front] def getRear( self ): if self .isEmpty() or self .rear < 0 : print ( "Underflow" ) return - 1 return self .arr[ self .rear] # Driver code if __name__ = = '__main__' : dq = Deque( 5 ) print ( "Insert element at rear end: 5" ) dq.insertrear( 5 ) print ( "Insert element at rear end: 10" ) dq.insertrear( 10 ) print ( "Get rear element:" , dq.getRear()) dq.deleterear() print ( "After delete rear element, new rear becomes:" , dq.getRear()) print ( "Inserting element at front end: 15" ) dq.insertfront( 15 ) print ( "Get front element:" , dq.getFront()) dq.deletefront() print ( "After delete front element, new front becomes:" , dq.getFront()) |
C#
using System; class Deque { private const int MAX = 100; private int [] arr; private int front; private int rear; private int size; public Deque( int size) { front = -1; rear = 0; this .size = size; arr = new int [MAX]; } public bool IsFull() { return (front == 0 && rear == size - 1) || front == rear + 1; } public bool IsEmpty() { return front == -1; } public void InsertFront( int key) { if (IsFull()) { Console.WriteLine( "Overflow" ); return ; } if (front == -1) { front = 0; rear = 0; } else if (front == 0) { front = size - 1; } else { front = front - 1; } arr[front] = key; } 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 = rear + 1; } arr[rear] = key; } 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 = front + 1; } } 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 = rear - 1; } } public int GetFront() { if (IsEmpty()) { Console.WriteLine( "Underflow" ); return -1; } return arr[front]; } public int GetRear() { if (IsEmpty() || rear < 0) { Console.WriteLine( "Underflow" ); return -1; } return arr[rear]; } public static void Main() { 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 deleting rear element, new rear becomes: " + dq.GetRear()); Console.WriteLine( "Inserting element at front end: 15" ); dq.InsertFront(15); Console.WriteLine( "Get front element: " + dq.GetFront()); dq.DeleteFront(); Console.WriteLine( "After deleting front element, new front becomes: " + dq.GetFront()); } } |
Javascript
class Deque { constructor(size) { this .arr = new Array(size); // Initialize the circular array this .front = -1; // Initialize front pointer this .rear = 0; // Initialize rear pointer this .size = size; // Store the size of the deque } isFull() { return ( this .front === 0 && this .rear === this .size - 1) || this .front === this .rear + 1; } isEmpty() { return this .front === -1; } insertfront(key) { if ( this .isFull()) { console.log( "Overflow" ); // Deque is full, cannot insert return ; } if ( this .front === -1) { this .front = 0; this .rear = 0; } else if ( this .front === 0) { this .front = this .size - 1; } else { this .front = this .front - 1; } this .arr[ this .front] = key; } insertrear(key) { if ( this .isFull()) { console.log( "Overflow" ); // Deque is full, cannot insert 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; } deletefront() { if ( this .isEmpty()) { console.log( "Queue Underflow" ); // Deque is empty, cannot delete 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; } } deleterear() { if ( this .isEmpty()) { console.log( "Underflow" ); // Deque is empty, cannot delete 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; } } getFront() { if ( this .isEmpty()) { console.log( "Underflow" ); // Deque is empty, cannot get front return -1; } return this .arr[ this .front]; } getRear() { if ( this .isEmpty() || this .rear < 0) { console.log( "Underflow" ); // Deque is empty, cannot get rear return -1; } return this .arr[ this .rear]; } } // Driver code const dq = new Deque(5); // Function calls console.log( "Insert element at rear end: 5" ); dq.insertrear(5); console.log( "Insert element at rear end: 10" ); dq.insertrear(10); console.log( "Get rear element:" , dq.getRear()); dq.deleterear(); console.log( "After delete rear element new rear becomes:" , dq.getRear()); console.log( "Inserting element at front end: 15" ); dq.insertfront(15); console.log( "Get front element:" , dq.getFront()); dq.deletefront(); console.log( "After delete front element new front becomes:" , dq.getFront()); |
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 : 15 get front element 15 After delete front element new front become 5
The deque data structure has a constant time complexity of O(1) for insert and delete operations, which means that the time taken to perform these operations is independent of the size of the deque. This makes it an efficient data structure for implementing a stack and a queue together.
2) Using Doubly Linked List
Here’s an implementation of a data structure that can function as both a stack and a queue using a doubly linked list:
- In this implementation, we use a doubly linked list with a head and tail pointer.
- The push method adds an element to the end of the list, while the enqueue method adds an element to the front of the list.
- The pop method removes an element from the end of the list, while the dequeue method removes an element from the front of the list.
Below is the implementation for the above steps:
C++
// C++ code for the approach #include <iostream> using namespace std; // A class representing a Node in a doubly linked list class Node { public : int data; Node* prev; Node* next; Node( int d) { data = d; prev = NULL; next = NULL; } }; // A class representing a StackQueue data structure class StackQueue { public : Node* head; Node* tail; StackQueue() { head = NULL; tail = NULL; } // Pushes an item onto the top of the stack // @param data the data to be pushed onto the stack void push( int data) { Node* new_node = new Node(data); if (tail == NULL) { tail = new_node; head = new_node; } else { new_node->prev = tail; tail->next = new_node; tail = new_node; } } // Removes and returns the item at the top of the stack // @return the item at the top of the stack int pop() { if (tail == NULL) { return -1; } Node* popped_node = tail; if (tail == head) { head = NULL; tail = NULL; } else { tail = popped_node->prev; tail->next = NULL; } return popped_node->data; } // Adds an item to the back of the queue // @param data the data to be added to the queue void enqueue( int data) { Node* new_node = new Node(data); if (head == NULL) { head = new_node; tail = new_node; } else { new_node->prev = tail; tail->next = new_node; tail = new_node; } } // Removes and returns the item at the front of the queue // @return the item at the front of the queue int dequeue() { if (head == NULL) { return -1; } Node* dequeued_node = head; if (head == tail) { head = NULL; tail = NULL; } else { head = dequeued_node->next; head->prev = NULL; } return dequeued_node->data; } }; // Driver Code int main() { // Create a new StackQueue object StackQueue sq; // Perform stack operations sq.push(1); sq.push(2); sq.push(3); cout << sq.pop() << endl; // Output: 3 cout << sq.pop() << endl; // Output: 2 cout << sq.pop() << endl; // Output: 1 // Perform queue operations sq.enqueue(4); sq.enqueue(5); sq.enqueue(6); cout << sq.dequeue() << endl; // Output: 4 cout << sq.dequeue() << endl; // Output: 5 cout << sq.dequeue() << endl; // Output: 6 return 0; } |
Java
/** A class representing a Node in a doubly linked list */ class Node { int data; Node prev; Node next; /** Constructor for creating a new Node object @param data the data to be stored in the Node */ Node( int data) { this .data = data; this .prev = null ; this .next = null ; } } /** A class representing a StackQueue data structure */ class StackQueue { Node head; Node tail; /** Constructor for creating a new StackQueue object */ StackQueue() { this .head = null ; this .tail = null ; } /** Pushes an item onto the top of the stack @param data the data to be pushed onto the stack */ void push( int data) { Node new_node = new Node(data); if ( this .tail == null ) { this .tail = new_node; this .head = new_node; } else { new_node.prev = this .tail; this .tail.next = new_node; this .tail = new_node; } } /** Removes and returns the item at the top of the stack @return the item at the top of the stack */ int pop() { if ( this .tail == null ) { return - 1 ; // Or throw an exception } Node popped_node = this .tail; if ( this .tail == this .head) { this .head = null ; this .tail = null ; } else { this .tail = popped_node.prev; this .tail.next = null ; } return popped_node.data; } /** Adds an item to the back of the queue @param data the data to be added to the queue */ void enqueue( int data) { Node new_node = new Node(data); if ( this .head == null ) { this .head = new_node; this .tail = new_node; } else { new_node.prev = this .tail; this .tail.next = new_node; this .tail = new_node; } } /** Removes and returns the item at the front of the queue @return the item at the front of the queue */ int dequeue() { if ( this .head == null ) { return - 1 ; // Or throw an exception } Node dequeued_node = this .head; if ( this .head == this .tail) { this .head = null ; this .tail = null ; } else { this .head = dequeued_node.next; this .head.prev = null ; } return dequeued_node.data; } } public class Main { public static void main(String[] args) { // Create a new StackQueue object StackQueue sq = new StackQueue(); // Perform stack operations sq.push( 1 ); sq.push( 2 ); sq.push( 3 ); System.out.println(sq.pop()); // Output: 3 System.out.println(sq.pop()); // Output: 2 System.out.println(sq.pop()); // Output: 1 // Perform queue operations sq.enqueue( 4 ); sq.enqueue( 5 ); sq.enqueue( 6 ); System.out.println(sq.dequeue()); // Output: 4 System.out.println(sq.dequeue()); // Output: 5 System.out.println(sq.dequeue()); // Output: 6 } } // This code is contributed by Shwetark_Kadam |
Python3
class Node: def __init__( self , data): self .data = data self .prev = None self . next = None class StackQueue: def __init__( self ): self .head = None self .tail = None def push( self , data): new_node = Node(data) if self .tail is None : self .tail = new_node self .head = new_node else : new_node.prev = self .tail self .tail. next = new_node self .tail = new_node def pop( self ): if self .tail is None : return None popped_node = self .tail if self .tail = = self .head: self .head = None self .tail = None else : self .tail = popped_node.prev self .tail. next = None return popped_node.data def enqueue( self , data): new_node = Node(data) if self .head is None : self .head = new_node self .tail = new_node else : new_node.preb = self .tail self .tail. next = new_node self .tail = new_node def dequeue( self ): if self .head is None : return None dequeued_node = self .head if self .head = = self .tail: self .head = None self .tail = None else : self .head = dequeued_node. next self .head.prev = None return dequeued_node.data if __name__ = = "__main__" : # Create a new StackQueue object sq = StackQueue() # Perform stack operations sq.push( 1 ) sq.push( 2 ) sq.push( 3 ) print (sq.pop()) # Output: 3 print (sq.pop()) # Output: 2 print (sq.pop()) # Output: 1 # Perform queue operations sq.enqueue( 4 ) sq.enqueue( 5 ) sq.enqueue( 6 ) print (sq.dequeue()) # Output: 4 print (sq.dequeue()) # Output: 5 print (sq.dequeue()) # Output: 6 |
C#
// C# code for the approach using System; // A class representing a Node in a doubly linked list class GFG { public int Data; public GFG Prev; public GFG Next; public GFG( int data) { Data = data; Prev = null ; Next = null ; } } // A class representing a StackQueue data structure class StackQueue { private GFG head; private GFG tail; public StackQueue() { head = null ; tail = null ; } // Pushes an item onto the top of the stack // @param data the data to be pushed onto the stack public void Push( int data) { GFG new_node = new GFG(data); if (tail == null ) { tail = new_node; head = new_node; } else { new_node.Prev = tail; tail.Next = new_node; tail = new_node; } } // Removes and returns the item at the top of the stack // @return the item at the top of the stack public int Pop() { if (tail == null ) { return -1; } GFG popped_node = tail; if (tail == head) { head = null ; tail = null ; } else { tail = popped_node.Prev; tail.Next = null ; } return popped_node.Data; } // Adds an item to the back of the queue // @param data the data to be added to the queue public void Enqueue( int data) { GFG new_node = new GFG(data); if (head == null ) { head = new_node; tail = new_node; } else { new_node.Prev = tail; tail.Next = new_node; tail = new_node; } } // Removes and returns the item at the front of the queue // @return the item at the front of the queue public int Dequeue() { if (head == null ) { return -1; } GFG dequeued_node = head; if (head == tail) { head = null ; tail = null ; } else { head = dequeued_node.Next; head.Prev = null ; } return dequeued_node.Data; } } // Driver Code class Geeks { static void Main() { // Create a new StackQueue object StackQueue sq = new StackQueue(); // Perform stack operations sq.Push(1); sq.Push(2); sq.Push(3); Console.WriteLine(sq.Pop()); // Output: 3 Console.WriteLine(sq.Pop()); // Output: 2 Console.WriteLine(sq.Pop()); // Output: 1 // Perform queue operations sq.Enqueue(4); sq.Enqueue(5); sq.Enqueue(6); Console.WriteLine(sq.Dequeue()); // Output: 4 Console.WriteLine(sq.Dequeue()); // Output: 5 Console.WriteLine(sq.Dequeue()); // Output: 6 } } |
Javascript
// JavaScript code for the approach // A class representing a Node in a doubly linked list class Node { constructor(d) { this .data = d; this .prev = null ; this .next = null ; } } // A class representing a StackQueue data structure class StackQueue { constructor() { this .head = null ; this .tail = null ; } // Pushes an item onto the top of the stack // @param data the data to be pushed onto the stack push(data) { const new_node = new Node(data); if ( this .tail == null ) { this .tail = new_node; this .head = new_node; } else { new_node.prev = this .tail; this .tail.next = new_node; this .tail = new_node; } } // Removes and returns the item at the top of the stack // @return the item at the top of the stack pop() { if ( this .tail == null ) { return -1; } const popped_node = this .tail; if ( this .tail == this .head) { this .head = null ; this .tail = null ; } else { this .tail = popped_node.prev; this .tail.next = null ; } return popped_node.data; } // Adds an item to the back of the queue // @param data the data to be added to the queue enqueue(data) { const new_node = new Node(data); if ( this .head == null ) { this .head = new_node; this .tail = new_node; } else { new_node.prev = this .tail; this .tail.next = new_node; this .tail = new_node; } } // Removes and returns the item at the front of the queue // @return the item at the front of the queue dequeue() { if ( this .head == null ) { return -1; } const dequeued_node = this .head; if ( this .head == this .tail) { this .head = null ; this .tail = null ; } else { this .head = dequeued_node.next; this .head.prev = null ; } return dequeued_node.data; } } // Driver Code (() => { // Create a new StackQueue object const sq = new StackQueue(); // Perform stack operations sq.push(1); sq.push(2); sq.push(3); console.log(sq.pop()); // Output: 3 console.log(sq.pop()); // Output: 2 console.log(sq.pop()); // Output: 1 // Perform queue operations sq.enqueue(4); sq.enqueue(5); sq.enqueue(6); console.log(sq.dequeue()); // Output: 4 console.log(sq.dequeue()); // Output: 5 console.log(sq.dequeue()); // Output: 6 })(); |
3 2 1 4 5 6
In this code, we create a new StackQueue object and use its push and pop methods to perform stack operations. We then use its enqueue and dequeue methods to perform queue operations. This approach has O(1) time complexity for all operations.