Github: LeetCode-Solutions by Mitchell
Queue
Implement a queue data structure in JavaScript that contains the following operations:
new Queue()
: Creates an instance of aQueue
class that doesn't contain any items. The constructor does not accept any arguments.
enqueue()
: Adds an item to the back of the queue. Required time complexity: O(1).
dequeue()
: Removes an item from the front of the queue. Required time complexity: O(1).
isEmpty()
: Determines if the queue is empty. Required time complexity: O(1).
front()
: Returns the item at the front of the queue without removing it from the queue. Required time complexity: O(1).
back()
: Returns the item at the back of the queue without removing it from the queue. Required time complexity: O(1).
length()
: Returns the number of items in the queue. Required time complexity: O(1).
Solutions
LinkedList based implementation.
Code
TypeScript
class Node<T> {
value: T | undefined;
next: Node<T> | null;
prev: Node<T> | null;
constructor(value?: T) {
this.value = value;
this.next = null;
this.prev = null;
}
}
export default class Queue<T> {
_dummyHead: Node<T>;
_dummyTail: Node<T>;
_length: number;
constructor() {
this._dummyHead = new Node<T>();
this._dummyTail = new Node<T>();
this._dummyHead.prev = this._dummyTail;
this._dummyTail.next = this._dummyHead;
this._length = 0;
}
/**
* Adds an item to the back of the queue.
*/
enqueue(item: T) {
const node = new Node(item);
const prevLast = this._dummyTail.next;
prevLast!.prev = node;
node.next = prevLast;
node.prev = this._dummyTail;
this._dummyTail.next = node;
this._length++;
return this._length;
}
/**
* Remove an item from the front of the queue.
*/
dequeue(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
const node = this._dummyHead.prev;
const newFirst = node!.prev;
this._dummyHead.prev = newFirst;
newFirst!.next = this._dummyHead;
// Unlink the node to be dequeued.
node!.prev = null;
node!.next = null;
this._length--;
return node!.value;
}
/**
* Determines if the queue is empty.
*/
isEmpty(): boolean {
return this._length === 0;
}
/**
* Returns the item at the front of the queue without removing it from the queue.
*/
front(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
return this._dummyHead.prev!.value;
}
/**
* Returns the item at the back of the queue without removing it from the queue it.
*/
back(): T | undefined {
if (this.isEmpty()) {
return undefined;
}
return this._dummyTail.next!.value;
}
/**
* Returns the number of items in the queue.
* @return {number} The number of items in the queue.
*/
length(): number {
return this._length;
}
}
Python
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
self.prev = None
class Queue:
def __init__(self):
self._dummy_head = Node()
self._dummy_tail = Node()
self._dummy_head.prev = self._dummy_tail
self._dummy_tail.next = self._dummy_head
self._length = 0
def enqueue(self, item):
"""Adds an item to the back of the queue.
Args:
item: The item to be pushed onto the queue.
Returns:
int: The new length of the queue.
"""
node = Node(item)
prev_last = self._dummy_tail.next
prev_last.prev = node
node.next = prev_last
node.prev = self._dummy_tail
self._dummy_tail.next = node
self._length += 1
return self._length
def dequeue(self):
"""Remove an item from the front of the queue.
Returns:
The item at the front of the queue if it is not empty, `None` otherwise.
"""
if self.is_empty():
return None
node = self._dummy_head.prev
new_first = node.prev
self._dummy_head.prev = new_first
new_first.next = self._dummy_head
# Unlink the node to be dequeued.
node.prev = None
node.next = None
self._length -= 1
return node.value
def is_empty(self):
"""Determines if the queue is empty.
Returns:
bool: `True` if the queue has no items, `False` otherwise.
"""
return self._length == 0
def front(self):
"""Returns the item at the front of the queue without removing it from the queue.
Returns:
The item at the front of the queue if it is not empty, `None` otherwise.
"""
if self.is_empty():
return None
return self._dummy_head.prev.value
def back(self):
"""Returns the item at the back of the queue without removing it from the queue.
Returns:
The item at the back of the queue if it is not empty, `None` otherwise.
"""
if self.is_empty():
return None
return self._dummy_tail.next.value
def length(self):
"""Returns the number of items in the queue.
Returns:
int: The number of items in the queue.
"""
return self._length