  Interview Questions

Implement a queue using a linked list
A queue is an abstract data structure where items can either be added to a collection or removed from a collection, enqueuing and dequeuing, respectively. A queue is similar to a physical line of people: people can be added to the end of the line (enqueuing), and to make the line smaller, people are removed from the front of the line (dequeuing). We're going to implement a queue using a linked list and we'll be using some code we've written in a previous solution. Another term used to describe queues is FIFO, which stands for first in, first out. It is a data structure where the first elements added to the collection will be the first removed.

## Example

We want our queue to have two methods, enqueue X, which will add element X to the end of the queue, and a dequeue method which will remove the current first item from the queue. We don't need to specify what we want to dequeue because the method always returns the first element from the queue. Here is an example of a few operations we want our queue to be able to perform. ## Algorithm

We will store a reference to the front and back of the queue in order to make enqueuing and dequeuing run in O(1) constant time. Every time we want to insert into the queue, we add the new element to the end of the linked list and update the back pointer. When we want to dequeue we return the first node in the linked list and update the front pointer.

## Code

```// queue is initially empty
var Queue = {front: null, back: null};

// we will use a node to keep track of the elements
// in the queue which is represented by a linked list
function Node(data, next) {
this.data = data;
this.next = next;
}

// add elements to queue in O(1) time
function Enqueue(element) {
var N = new Node(element, null);
if (Queue.back === null) {
Queue.front = N;
Queue.back = N;
} else {
Queue.back.next = N;
Queue.back = Queue.back.next;
}
}

// remove first element from queue in O(1) time
function Dequeue() {
if (Queue.front !== null) {
var first = Queue.front;
Queue.front = Queue.front.next;
return first.data;
} else {
if (Queue.back !== null) { Queue.back = null; }
return 'Cannot dequeue because queue is empty';
}
}

Enqueue('a');
Enqueue('b');
Enqueue('c');
Dequeue();
```
```# queue is initially empty
Queue = {'front': None, 'back': None}

# we will use a node to keep track of the elements
# in the queue which is represented by a linked list
class Node:
def __init__(self, data, next):
self.data = data
self.next = next

// add elements to queue in O(1) time
def Enqueue(Queue, element):
N = Node(element, None)
if Queue['back'] == None:
Queue['front'] = N
Queue['back'] = N
else:
Queue['back'].next = N
Queue['back'] = Queue['back'].next

# remove first element from queue in O(1) time
def Dequeue(Queue):
if Queue['front'] != None:
first = Queue['front']
Queue['front'] = Queue['front'].next
return first.data
else:
if Queue['back'] != None:
Queue['back'] = None
return 'Cannot dequeue because queue is empty'

Enqueue(Queue, 'a')
Enqueue(Queue, 'b')
Enqueue(Queue, 'c')
print Dequeue(Queue)
```

## Running time

Because we keep a reference to the front and back pointers of the linked list, inserting a new node and removing the first node are both done in O(1), constant time. These operations do not depend on the size of the queue at all. mrdaniel published this on 11/24/15 |