A queue works in a very similar way to a stack. The only difference is that items that are first added to the queue are the first to be taken off the queue. The operations on a queue are simply Add and Remove. Add will add a node to the end of the queue while Remove will take the first node off the queue.

 

In order to make a queue work we need to store the start of the queue and also each node must store the previous node. This is almost identical to the stack. However we also need to store where the end of the queue is as well. Although this is not necessary it does improve performance. The end of the queue can always be found by starting at the front of the queue and keep going until you find the end. However this may take a long time is the queue is large. It is must simpler to go straight to the end of the queue and this is how we know as humans queues work. People normally get a bit upset if you try and join the front of the queue.

 

It is also important that you store who is in front of you in the queue otherwise it would not work. As such we now have what is known as a doubly linked data structure. The diagram below shows how this works.

Add

 

  1. Create a new node
  2. Set the previous node to be null
  3. Set the front node to be back link.
  4. The back link now is linked to the new node.

 

Remove

 

  1. Look at the node pointed to by the front link.
  2. Set the global front link to be the previous link of the front node.