Table of Contents

Description

Think of a queue as a line of people waiting for something. You add more people to the back of the line, and remove people from the front of the line. The first person added to the line will be the first to get out of it.

• A queue is a data structure that models a real life queue (waiting line).
• Properties
  • FIFO: The first element to enter the queue will be the first one removed from the queue.
    • This means you must enqueue and dequeue from opposite sides
  • When using a linked list, the tail is the back of the queue, and the head is the front.
    • tail = back, head = front
• Operations
  • Enqueue: adds an element to the back of the queue.
    • For a linked list, this adds a new head.
  • Dequeue: removes an element from front of the queue.
    • For a linked list, this adds a new tail.
  • Peek: check the value of the first element on the queue
  • Contains: searches the queue to see if it contains a specific element.
  • Remove: remove an element from inside the queue (not the end)
  • isEmpty: checks if the queue is empty

Usage

• Algorithms that use a queue
  • Breadth First Search: Elements are enqueue’d when they’re checked, then dequeue’d afterwards.
  • Caches: stores recently accessed data, so that they can be quickly loaded if re-accessed.
  • Web servers: Used to handle web requests and send out responses; only 5 or so requests are handled at once, the rest are added in queue and added to the batch in order of recency.
• A queue can be used to model:
  • A real-life waiting line.
  • A queue to wait for some event (e.g. speaking with a customer service representative).
  • Anything where you want to keep track of and later revisit recently added objects, in the same order they were added.
    • Search node 1, 2, 3.
    • Revisit node 1, then node 2, then node 3.

Efficiency

• Enqueue and Dequeue, and Peek are constant time because they require no iteration. You just have to look at the first or last element of the queue.
• isEmpty is constant time because you just have to look at the first element of the queue. If there is no element (it’s NULL), then the queue is empty.
• Contains, in the worst case, will require you to iterate through the entire queue until you find the element you’re searching for. Since you’re iterating through every element once, it’s linear time.
• Remove, in the worst case, will require you to iterate through most of the queue to get to the element you want to remove. So its linear time.

Implementation

• Implementation methods

  • Arrays
    • Static Array
      • Static arrays are faster than linked lists, but require the queue to be fixed to a certain size. Make sure the array is big enough for your needs.
    • Dynamic Array
  • Linked List
    • Singly Linked List
    • Doubly Linked List

• Operational implementations (using a Linked List)

    ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0ca00c81-4a1d-40d2-a28b-a6bccdae576e/Untitled.png>)
  

  • Enqueue: Adding a new tail (back of line).
    1. Create a new node.
    2. Point the tail pointer to the new node.
    3. Point the old tail to the new node.
  • Dequeue: Removing the current head (front of line).
    1. Point the head pointer to the second node in the linked list.
    2. Delete the pointer between the first and second nodes.
    3. Set the first node to NULL so that it’ll be picked up by the garbage collector.