Introduction to Stack:
- A stack is a linear data structure in computer science that follows the Last-In-First-Out (LIFO) principle. It is a data structure in which the insertion and removal of elements can only be performed at one end, which is called the top of the stack.
- In a stack, elements are pushed onto the top of the stack, and elements are popped off from the top of the stack. The last element that is pushed onto the stack is the first one to be popped off, hence it implies the LIFO principle.
The stack operations can be summarized as follows:
- push: Add an element to the top of the stack
- pop: Remove the element from the top of the stack
- top: Get the value of the element at the top of the stack
- empty: Check if the stack is empty
A stack can be implemented using an array, a linked list, or a dynamic array (such as a vector in C++ or ArrayList in Java). In programming, stacks are used to implement recursive algorithms, undo/redo functionality, expression evaluation, and more.
Introduction to Queue:
- A queue is a linear data structure in computer science that follows the First-In-First-Out (FIFO) principle in which the insertion of elements is done at the rear (tail) end and the removal of elements is done at the front (head) end.
- In a queue, the element that is inserted first is the first one to be removed, hence it implies the FIFO principle.
The queue operations can be summarized as follows:
- enqueue (or push): Add an element to the rear of the queue
- dequeue (or pop): Remove the element from the front of the queue
- front: Get the value of the element at the front of the queue
- empty: Check if the queue is empty
A queue can be implemented using an array, a linked list, or a dynamic array (such as a vector in C++ or ArrayList in Java). In programming, queues are used to implement algorithms like breadth-first search, round-robin scheduling, and more.
Different Ways to implement Stack and Queue together:
There are several ways to implement a data structure that combines both a stack and a queue:
- Using two stacks: We can simulate a queue using two stacks. We call these stacks input and output. We add elements to the input stack, and when we want to remove an element, we move all the elements from the input stack to the output stack. This will reverse the order of the elements, effectively simulating a queue. We can then remove an element from the output stack.
- Using two queues: We can simulate a stack using two queues. We call these queues q1 and q2. When we add an element, we add it to the q1 queue. When we want to remove an element, we move all the elements from q1 to q2, except for the last element. We can then remove the last element from q1 and repeat the process.
- Using a circular buffer: We can use a circular buffer to implement a data structure that combines both a stack and a queue. We can use an array of fixed size, and two pointers front and rear to keep track of the elements. When we add an element, we insert it at the rear of the array. When we remove an element, we remove it from the front of the array. We can use a variable ‘count’ to keep track of the number of elements in the buffer. If ‘count’ reaches the maximum size of the buffer, we can either resize the buffer or discard the oldest element and add the new element.
- Using a deque: A deque (double-ended queue) is a data structure that allows the insertion and removal of elements from both ends. We can use a deque to implement a data structure that combines both a stack and a queue. When we want to add an element, we can insert it at the front of the deque. When we want to remove an element, we can remove it from the back of the deque. This will simulate a stack. We can also add elements to the back of the deque to simulate a queue.
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 Dequeclass 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 frontvoid 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 Dequevoid 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 Dequevoid 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 Dequeint 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 Dequeint Deque::getRear(){ // Check whether Deque is empty or not if (isEmpty() || rear < 0) { cout << " Underflow\n" << endl; return -1; } return arr[rear];}// Driver codeint 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 arrayclass 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 arrayclass 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 codeif __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 codeconst dq = new Deque(5);// Function callsconsole.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()); |
Output
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 listclass Node {public: int data; Node* prev; Node* next; Node(int d) { data = d; prev = NULL; next = NULL; }};// A class representing a StackQueue data structureclass 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 Codeint 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 objectStackQueue 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 = Noneclass 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.dataif __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 approachusing System;// A class representing a Node in a doubly linked listclass 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 structureclass 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 Codeclass 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 listclass Node { constructor(d) { this.data = d; this.prev = null; this.next = null; }}// A class representing a StackQueue data structureclass 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})(); |
Output
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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
