```
/**
* A Stack Based Queue Implementation.
* The Queue data structure which follows the FIFO (First in First Out) rule.
* The dequeue operation in a normal stack based queue would be o(n), as the entire has to be shifted
* With the help of two stacks, the time complexity of this can be brought down to amortized-O(1).
* Here, one stack acts as an Enqueue stack where elements are added.
* The other stack acts as a dequeue stack which helps in dequeuing the elements
*/
import { Stack } from '../stack/stack'
import { Queue } from './queue'
export class StackQueue<T> implements Queue<T> {
private enqueueStack: Stack<T> = new Stack<T>()
private dequeueStack: Stack<T> = new Stack<T>()
/**
* Returns the length of the Queue
*
* @returns {number} the length of the Queue
*/
length(): number {
return this.enqueueStack.length() + this.dequeueStack.length()
}
/**
* Checks if the queue is empty.
*
* @returns {boolean} Whether the queue is empty or not.
*/
isEmpty(): boolean {
return this.enqueueStack.isEmpty() && this.dequeueStack.isEmpty()
}
/**
* Adds an item to the queue.
* We always add a new item to the enqueueStack.
* @param item The item being added to the queue.
*/
enqueue(item: T): void {
this.enqueueStack.push(item)
}
/**
* Shifts the elements from the enqueueStack to the dequeueStack
* In the worst case, all the elements from the enqueue stack needs to shifted, which needs O(n) time.
* However, after the shift, elements can de dequeued at O(1).
* This helps in dequeuing the elements in amortized O(1) time.
*/
private shift(): void {
while (!this.enqueueStack.isEmpty()) {
const enqueueStackTop = this.enqueueStack.pop()
this.dequeueStack.push(enqueueStackTop)
}
}
/**
* Removes an item from the queue and returns it.
*
* @throws Queue Underflow if the queue is empty.
* @returns The item that was removed from the queue.
*/
dequeue(): T {
if (this.isEmpty()) {
throw new Error('Queue Underflow')
}
if (this.dequeueStack.isEmpty()) {
this.shift()
}
return this.dequeueStack.pop()
}
/**
* Returns the item at the front of the queue.
*
* @returns The item at the front of the queue or null if the queue is empty.
*/
peek(): T | null {
if (this.isEmpty()) {
return null
}
if (this.dequeueStack.isEmpty()) {
this.shift()
}
return this.dequeueStack.top()
}
}
```