Last time I looked at implementing the Stack Data Structure in Python and C#. In this article I'll be implementing similar solutions in Python and C# using the Queue Data Structure. The Stack is a last-in, first-out data structure and the Queue is a first-in, first-out data structure.
Deque in Python
The collections module in Python has a lot of feature-rich containers, and one of them is deque. It allows for fast appends and pops to both the left and right sides of the container, making it a great solution for both Stacks and Queues in Python. Here is an example in Python using deque as a Queue.
from collections import deque queue = deque() queue.append(1) queue.append(2) queue.append(3) is_empty = len(queue) == 0 print(is_empty) # False print(queue.popleft()) # 1 print(queue.popleft()) # 2 print(queue.popleft()) # 3 is_empty = len(queue) == 0 print(is_empty) # True print(queue.popleft()) # IndexError: pop from an empty deque
Using Link List for Queue in Python
One can use a Link List as a Queue in Python. In order to make appends really fast I will add a tail pointer in addition to the normal head pointer. I can pop from the head of the Link List in O(1) with the head pointer, and append to the tail of the Link List in O(1) with the tail pointer.
class Node:
def __init__(self, key):
self.key = key
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def append(self, key):
new_node = Node(key)
# empty. add first node.
if self.is_empty():
self.head = new_node
self.tail = self.head
return
# not empty. add node to the tail.
self.tail.next = new_node
self.tail = new_node
def pop(self):
if self.is_empty():
raise IndexError('pop from an empty queue')
key = self.head.key
# if only 1 item in queue, otherwise...
if self.head is self.tail:
self.head = None
self.tail = self.head
else:
self.head = self.head.next
return key
def is_empty(self):
return self.head is None
queue = Queue()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.is_empty()) # False
print(queue.pop()) # 1
print(queue.pop()) # 2
print(queue.pop()) # 3
print(queue.is_empty()) # True
print(queue.pop()) # IndexError: pop from an empty queue
Queue Class as Abstraction in Python
The custom Queue Class used with the Link List abstracts away the details of using a Link List to handle Queue operations. In fact, it is easy to change the underlying implementation of using a Link List with deque and preserve the operations of pop, append, and is_empty. Let's do that to show that abstraction is a very useful concept in computer science. Here is the same Queue class as above using deque in place of a Link List.
from collections import deque
class Queue:
def __init__(self):
self.__queue = deque()
def append(self, key):
self.__queue.append(key)
def pop(self):
return self.__queue.popleft()
def is_empty(self):
return len(self.__queue) == 0
queue = Queue()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.is_empty()) # False
print(queue.pop()) # 1
print(queue.pop()) # 2
print(queue.pop()) # 3
print(queue.is_empty()) # True
print(queue.pop()) # IndexError: pop from an empty dequeue
Using Array as Queue in C#
One can also use an Array as a Queue, but there is a fixed limit to the number of items that can be queued using an Array. I am talking about a fixed array and not a Dynamic Array.
Python does not have Arrays, so let's explore this concept in C#. Using an Array as a Queue will require a read index and a write index. The read index will point to the index in the Array for the next read. The write index will point to the index in the Array where the next value will be written. The Array can be thought of as a circular Queue, such that when the read and write index hit the end of the Array they can loop back to the beginning of the Array. When the read index is equal to the write index the Queue is empty. Note that we need an empty cell between the read index and the write index in order to differentiate between an empty Queue and a full Queue. Therefore when I initialize the Array, I tack on one extra cell for the differentiation.
Here is a rough example of using an Array as a Queue in C# to help one understand the concept.
public class Queue<T> {
private readonly T[] _queue;
private int _readIndex;
private int _writeIndex;
public Queue(int length = 20) {
// Need empty cell to differentiate
// between full and empty.
_queue = new T[length + 1];
}
public void Append(T key) {
if (IsFull())
throw new IndexOutOfRangeException("append to full queue.");
_queue[_writeIndex] = key;
_writeIndex = (_writeIndex + 1)%_queue.Length;
}
public T Pop() {
if (IsEmpty())
throw new IndexOutOfRangeException("pop from empty queue.");
var key = _queue[_readIndex];
_readIndex = (_readIndex + 1)%_queue.Length;
return key;
}
public bool IsEmpty() {
return _readIndex == _writeIndex;
}
public bool IsFull() {
return (_writeIndex + 1)%_queue.Length == _readIndex;
}
}
Here is a C# Script similar to the Python Scripts that show the Queue's API. Since the Queue can be full in this case, I added an IsFull Method.
var queue = new Queue<int>(3); queue.Append(1); queue.Append(2); queue.Append(3); Console.WriteLine(queue.IsEmpty()); // False Console.WriteLine(queue.IsFull()); // True Console.WriteLine(queue.Pop()); // 1 Console.WriteLine(queue.Pop()); // 2 Console.WriteLine(queue.Pop()); // 3 Console.WriteLine(queue.IsEmpty()); // True Console.WriteLine(queue.IsFull()); // False Console.WriteLine(queue.Pop()); // IndexError: pop from an empty queue
Queue Class in C# from System.Collections
There is a Queue Class in System.Collections and Queue<T> Class in System.Collections.Generic that provides a Queue Data Structure for your .NET Applications. Rather than using append and pop, it uses enqueue and dequeue to represent appending and removing items from the Queue.
var queue = new Queue<int>(3); queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); Console.WriteLine(queue.Count == 0); // False Console.WriteLine(queue.Dequeue()); // 1 Console.WriteLine(queue.Dequeue()); // 2 Console.WriteLine(queue.Dequeue()); // 3 Console.WriteLine(queue.Count == 0); // True Console.WriteLine(queue.Dequeue()); // IndexOperationException
Conclusion
Hopefully this helps explain different ways of implementing a Queue in Python and C#. There is no need to implement a Queue yourself using an Array or Link List. I just added these to help explain the concepts of how a Queue could be implemented under the covers. The deque container in the collections module in Python and the Queue and Queue<T> Classes in System.Collections and System.Collections.Generic in C# are highly optimized solutions for implementing a Queue in your applications.
Best Wishes!
