Queue Basics

excerpt: This covers the implementation of enqueue and dequeue operations of a linked list based stack. tags: linked-list-traversal sentinel

A queue is a data structure where items are added and removed in first-in-first-out order. They are sometimes called FIFO lists or FIFOs. A queue is similar to grocery checkout line. People join the end of the line and wait their turn. When they get to the front of the line, the cashier checks out your items and give you a receipt.

The method that adds an item to a queue is called Enqueue and the item that removes an item from a queue is called Dequeue.

Linked-List Queues

Linked list can be used to implement a queue. Doubly linked list makes removing the last item from the queue easy. The enqueue method add a new node to the head of the list and the dequeue method removes the last node from the list. The following code shows the enqueue method to add an item in a linked-list stack.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def enqueue(head, value)
  node = Node.new
  node.value = value
  
  # add new node to the linked list
  node.link = head.link
  head.link = node
  node.previous = head
end

enqueue(sentinel, 3)

list.traverse(sentinel)

This will add the node with value three to the beginning of the linked list.

The node class has getters and setters for getting and setting the values for the value, next and previous pointers.

1
2
3
4
5

 class Node
   attr_accessor :link
   attr_accessor :value
   attr_accessor :previous
 end

The implementation of doubly linked list with the code for testing:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

require_relative 'node'

class DoubleLinkedList
  def traverse(node)
    while node
      p node.value
      node = node.link
    end
  end  

  def insert(after, node)
    # update the next links
    node.link = after.link
    after.link = node
    
    # update previous links
    node.previous = after
    node.link.previous = node  
  end
end

sentinel = Node.new
sentinel.value = 0
tail = Node.new
tail.value = 0

first = Node.new
first.value = 1
first.previous = sentinel
sentinel.link = first

second = Node.new
second.value = 2
second.previous = first
first.link = second
second.link = tail
tail.previous = second

list = DoubleLinkedList.new
list.traverse(sentinel)

The dequeue method removes the item in the end of the doubly linked list. There must be an item in the queue to remove it. Otherwise, an exception will be thrown. The dequeue method will return the value of the node that was removed from the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def dequeue(tail, head)
  # queue cannot be empty
  if tail.previous == head
    raise 'Cannot dequeue an empty stack'
  end
  
  # Get the last node's value
  result = tail.previous.value

  tail.previous = tail.previous.previous
  tail.previous.link = tail
  
  return result
end

dequeue(tail, sentinel)
list.traverse(sentinel)

The enqueue and dequeue operations implemented using doubly linked list have O(1) run times. The don’t need any extra space, so the space complexity is O(1).