Queues

A queue is a data structure for holding objects. It is a FIFO structure. It supports two operations: enqueue and dequeue

dequeue returns (and removes) the next element inserted (starting from the first).

enqueue adds a new element to the queue.

A line at the clerk’s counter in the grocery store is an example of a queue.

Question: Assume \(0-N\) were inserted in a queue in order, but randomly popped out \(N\) times, how can we determine if a given sequence of pops is valid?

Implementations

Linked List

You can implement it with a linked list. Maintain pointers to the head and tail of the list. Both enqueue and dequeue commands are \(O(1)\).

Array

You can implement it using an array. The first element is inserted in the front of the array, and each additional enqueue is inserted in the succeeding element, with two indices keeping track of front and last elements. When you dequeue, you simply increment the head counter.

However, there are complications:

You have to manually maintain the size of the queue.
When you dequeue, you need to set the removed element of the array to NULL - otherwise you could end up with a memory leak as there will always be a pointer to the object.
You need to allocate the array size appropriately.

Resizing Arrays

One issue is that after a number of dequeue operations, the head of the queue is far away from the head of the array. To solve this problem, whenever the tail hits the end of the array, we could copy all the elements such that the head is at the head of the array (and resize if needed).

Another solution is to use a circular array, where when the queue hits the end of the array, we continue it at the beginning of the array and keep track of all indices. We resize only when we have no more room.

I assume the criteria to resize an array matches that of stacks.

Linked List vs Arrays

Most individual operations in arrays are quicker than the overhead of maintaining a linked list (with less memory per item). But with a linked list you never get sudden slow downs due to allocations.

Using Stacks

You can implement a queue with 2 stacks, in and out. When you enqueue, you push into in. When you dequeue, if out is empty, pop all the elements from in into out, and then pop from out. If it is not empty, simply pop from out.

Each element is pushed twice, and popped twice, so on average, it takes constant time.

Implementations In Code

Python

Python lists can be used as stacks. Not ideal, as you can do more with Python lists to mess up your stack data structure.

One could also use the Queue module and specify the queue to be LIFO.

from Queue import Queue

queue = Queue()

queue.put(10)
queue.put(12)
print queue.get()
queue.put(14)
print queue.get()
print queue.get()

C++

The STL has a queue class.

By default it utilizes a double ended queue. You can make it use a linked list in the backend if you desire by passing std::list to the argument of Container.

Note that pop() does not return the value. To access it, use front().

#include <iostream>
#include <queue>

int main(void) {

  std::queue<int> q;
  
  q.push(10);
  q.push(12);

  std::cout << q.front() << std::endl;
  q.pop();
  q.push(14);
  std::cout << q.front() << std::endl;
  q.pop();
  std::cout << q.front() << std::endl;

  return 0;
}