Ask LSBot
Back to Open Book Shelf

Queues

A queue is an abstract data type that follows the "First In, First Out" (FIFO) principle. This means the first item added to the queue is the first item to be removed.

Imagine a line of people waiting for a movie theater ticket. The first person to get in line is the first to be served and leave. No one typically cuts in the middle or leaves from the middle unless all the people before have been served. This orderly process is the essence of FIFO.

Key Operations

Here are the three primary operations you can perform on a queue data structure:

Enqueue

  • In queue terminology, enqueueing is the act of adding an element to the back of the queue. Just as a new person joins the end of the line, adding an element in a data context places a data element (like a number, character, or object) at the end of the queue.
  • This operation is accomplished in constant time, O(1), because it doesn't require shifting or moving other elements around; you simply add the new item to the end.

Dequeue

  • Similar to the first person in line being served and leaving the queue, dequeueing in a queue data structure involves removing the front element.
  • This is also a constant time operation, O(1), as it directly accesses the front element without needing to rearrange or look through the rest of the queue.

Peek

  • In a queue of people, you might look at the person at the front to see who will be served next. In a queue data structure, "peeking" allows you to see the value of the front element without removing it from the queue. This can be useful for checking the value before deciding to serve or remove it.

Practical Applications of Queues

Process Scheduling

In operating systems, processes are managed in a queue format. Each process joins the queue and waits its turn to be executed by the CPU. The first process added to the queue is the first to get CPU time, ensuring orderly processing.

Print Job Management

Consider a printer connected to multiple computers. Print jobs sent to the printer are managed using a queue, ensuring that documents are printed in the order they were received. This prevents conflicts and confusion, maintaining a fair system.

Real-Time Systems

In real-time systems like traffic lights or customer service lines, queues manage tasks that must be executed in the order they arrive. This can ensure fairness and efficiency, reducing wait times and preventing bottlenecks.

Breadth-First Search (BFS) in Graphs

We will cover Graphs in one of the later lessons. For now, know that a breadth-first search algorithm exists that uses a queue to systematically explore each vertex (node of a graph) and its neighbors.

Implement a Queue with a Singly Linked List

In these exercises, your goal is to implement a queue using a singly linked list. Once again we'll provide you with some template code to get started. If you need help, you can refer to the walkthroughs below.

description">Problem Description

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.back = null;
  }
  peek() {
    // Returns the value of the top most element without removing it.

    // If the queue is empty, it returns `null`.
  }

  enqueue(value) {
    // Adds an item to the queue
  }

  dequeue() {
    // Removes the item from the queue and returns it

    // If the queue is empty, it returns `null`.
  }
}

const myQueue = new Queue();
myQueue.enqueue(1);
console.log('Front element:', myQueue.peek());  // logs 'Front element: 1'
myQueue.enqueue(2);
console.log('Front element:', myQueue.peek());  // logs 'Front element: 1'
myQueue.enqueue(3);
console.log('Front element:', myQueue.peek());  // logs 'Front element: 1'
myQueue.dequeue();
console.log('Front element after dequeue:', myQueue.peek());  // logs 'Front element after dequeue: 2'
myQueue.dequeue();
console.log('Front element after dequeue:', myQueue.peek());  // logs 'Front element after dequeue: 3'
myQueue.dequeue();
console.log('Peek on empty queue:', myQueue.peek());  // logs 'Peek on empty queue: null'
console.log('`back` on empty queue:', myQueue.back);  // logs '`back` on empty queue: null'

Exercises

  1. Implement peek and write some test code to ensure that it's working.

    As you might have already noticed from the template, you'll need to use two pointers to implement a queue using a singly linked list. One pointer will always point to the front of the queue, and the other will point to the back of the queue.

    View Our Solution

    The peek method in a queue is straightforward. It returns the value of the frontmost node or null if the queue is empty.

    // some code above

peek() {
  return this.front ? this.front.val : null;
}

    We use a ternary operator for simplicity. If the front element exists, this.front.val is returned; otherwise, it returns null. This can be rewritten with an if statement for clarity:

    // some code above

peek() {
  if (this.front) {
    return this.front.val;
  }
  return null;
}

  2. Implement enqueue and write some test code to ensure that it's working.

    View Our Solution

    The enqueue method is more challenging.

    • First, create a new ListNode with the given value.
    • If the queue is empty (no front node), the new node becomes both the front and back of the queue.
    • If the queue is not empty:
      • Link the next property of the current back node to the new node.
      • Update the back to point to the new node.

    Assuming we have created a queue, let's see how adding the first 3 elements would look visually:

    myQueue.enqueue(1)

    We start by creating a new ListNode with 1 as the value. Because front is null when our queue is empty, we'll assign both front and back to our new node.

    myQueue.enqueue(2)

    Again, we start by creating our new node, newNode. Now that our list is not empty, we'll assign the next property of the back node (the last node in our queue) to newNode. This puts our new node 'behind' the end of our queue. We finish by assigning back to the new end of our queue.

    myQueue.enqueue(3)

    Adding yet another node follows the same process as the previous call to enqueue. We create a new node, update the next pointer of back, and reassign back to newNode.

    // some code above

enqueue(value) {
  const newNode = new ListNode(value);
  if (!this.back) {
    this.front = this.back = newNode;
  } else {
    this.back.next = newNode;
    this.back = newNode;
  }
}

  3. Implement dequeue and write some test code to ensure that it's working.

    View Our Solution

    The dequeue method removes and returns the value from the front of the queue, returning null if the queue is empty. If the queue is not empty we should:

    • Store the current front node in a temporary variable.
    • Update the front pointer to point to the next node.
    • If the front is null, also set back to null (the queue is empty now).
    • Return the value of the removed node.

    Let's see how this looks visually:

    myQueue.dequeue()

    We start by storing the existing front node (with a value of 1) in a variable removedNode. Now that we've saved the removed node, we can reassign front to front.next, effectively deleting the node with value 1 form our queue. Since front references a node, and not null, we can finish by returning the value of our stored removedNode, 1.

    myQueue.dequeue()

    This invocation is similar to the previous step. We save a reference to the node with a value of 2, reassign front to front.next (node with value 3) and can return the value of removedNode, 2.

    myQueue.dequeue()

    Our last invocation of dequeue takes a bit more work. We can begin as normal, storing the node referenced by front with our removedNode variable. Then we reassign front to front.next, which is null, because our queue only had 1 element. If we were to stop here and return removedNode.val, we would return the correct value, but we would have a problem in that back would still be pointing to our removed node. Since our queue is now empty, back should be referencing null, just like front.

    This is where our final check comes in. After reassigning front to front.next, we need to check if this new front is null. This time, it is. We must reassign back to null, and finally we can return removedNode.val.

    myQueue.dequeue()

    When trying to dequeue and empty queue, we return null because there's no front node.

    // some code above

dequeue() {
  if (!this.front) return null;

  const removedNode = this.front;
  this.front = this.front.next;
  if (!this.front) {
    this.back = null;
  }
  return removedNode.val;
}

    Finally, here's all of our code together:

    class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.back = null;
  }
  peek() {
    return this.front ? this.front.val : null;
  }

  enqueue(value) {
    const newNode = new ListNode(value);
    if (!this.front) {
      this.front = this.back = newNode;
    } else {
      this.back.next = newNode;
      this.back = newNode;
    }
  }

  dequeue() {
    if (!this.front) return null;

    const removedNode = this.front;
    this.front = this.front.next;
    if (!this.front) {
      this.back = null;
    }
    return removedNode.val;
  }
}


const myQueue = new Queue();
myQueue.enqueue(1);
console.log('Front element:', myQueue.peek());  // logs 'Front element: 1'
myQueue.enqueue(2);
console.log('Front element:', myQueue.peek());  // logs 'Front element: 1'
myQueue.enqueue(3);
console.log('Front element:', myQueue.peek());  // logs 'Front element: 1'
myQueue.dequeue();
console.log('Front element after dequeue:', myQueue.peek());  // logs 'Front element after dequeue: 2'
myQueue.dequeue();
console.log('Front element after dequeue:', myQueue.peek());  // logs 'Front element after dequeue: 3'
myQueue.dequeue();
console.log('Peek on empty queue:', myQueue.peek());  // logs 'Peek on empty queue: null'
console.log('`back` on empty queue:', myQueue.back);  // logs '`back` on empty queue: null'

Ask LSBot about: Queues

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

Queues - Exercise

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.