queue-data-structure

A queue is a first-in-first-out (FIFO) data structure.

We all know that the list/array in Python is very powerful, that it can be used as a queue itself. For example, to create a queue in Python, we do this:

1

q = []

q = []

Then, we can push an element to the queue using the list append() method.

1
2
3
4
5

q.append(1)
q.append(2)
q.append(3)
# now the queue has 3 elements
[1, 2, 3]

q.append(1)
q.append(2)
q.append(3)
# now the queue has 3 elements
[1, 2, 3]

We can check the length of the list in order to perform the queue.empty() test.

1
2

def isEmptyQueue(queue):
   return len(queue) == 0

def isEmptyQueue(queue):
   return len(queue) == 0

The last element in the list/array will be useful, such as peeking the top of the queue:

1
2

def peekQueue(queue):
   return queue[-1]

def peekQueue(queue):
   return queue[-1]

Popping an element i.e. deQueue() is even simpler with the array.pop(0) method – which removes the first element (index zero) from the list/array and return it. For example:

1
2

def deQueue(queue):
   return queue.pop(0)

def deQueue(queue):
   return queue.pop(0)

The Monotone Queue in Python

A Monotone queue is a queue, however, it preserves the orders of the elements in the queue from left to the right. For example, the Monotone decreasing queue looks like:

1

q = [5, 4, 3, 2, 1]

q = [5, 4, 3, 2, 1]

Now, if we now push another element, e.g. 3, to the queue. It will dequeue the elements that are larger than 3 before 3 is pushed to the queue.

1

q = [3, 3, 2, 1] # 5 and 4 will be dequeued and removed.

q = [3, 3, 2, 1] # 5 and 4 will be dequeued and removed.

At anytime, the monotone queue will keep the elements in the queue in either increasing or decreasing order (monotone sequence). The Monotone queue is handy as it tells us the next smaller-or-equal element. For example, in the above case, we know the next smaller-or-equal number is 3.

1
2
3
4

def pushMontoQueue(queue, ele):
   while len(queue) > 0 and queue[0] > ele:
       queue.pop(0) # deQueue
   queue.push(ele)

def pushMontoQueue(queue, ele):
   while len(queue) > 0 and queue[0] > ele:
       queue.pop(0) # deQueue
   queue.push(ele)

Similar, the array/list can be used to implement a monotone stack.

–EOF (The Ultimate Computing & Technology Blog) —