Queue data structure

This tutorial is a part of the Data Structures and Algorithms class:

• Queue in real life
• Build Queue data structure
• How to insert/delete/access/search data
• How fast to insert/delete/access/search data

Queue in real life

Queue data structure:

• mimics a queue of things in real life. Example: a queue of people waiting in front of a restaurant.
• data (ex: people) in/out follows the honor system: First-In-First-Out (FIFO).
• is a very popular data structure. Example applications: real life queue modeling (queue of people), message broker system, implement Breadth-First-Search algorithm, ...

Build Queue data structure

// build Queue data structure
class Queue {
  constructor() {
    this.queue = []
  }

  // add data to the queue, O(1)
  enqueue(val) {
    this.queue.push(val)
    return val
  }

  // remove first element in queue
  // Note: O(n) with this implementation (for simplicity),
  // but we can achieve O(1) for this operation,
  // try to implement that as a practice for your programming.
  dequeue() {
    return this.queue.shift(val)
  }

  // see queue size, O(1)
  size() {
    return this.queue.length
  }

  // see first element in line, O(1)
  peek() {
    return this.queue[0]
  }

  // see all data in the queue, O(1)
  print() {
    console.log(this.queue)
  }
}

// create a queue
const queue = new Queue()
queue.print() // []

$ node queue-data-structure.js
[]

How to insert/delete/access/search data

// insert
console.log(queue.enqueue(1)) // 1
console.log(queue.enqueue(2)) // 2
console.log(queue.enqueue(3)) // 3
queue.print() // [ 1, 2, 3 ]

// delete 
console.log(queue.dequeue()) // 1
queue.print() // [ 2, 3 ]

// peek
console.log(queue.peek()) // 2

// size
console.log(queue.size()) // 2

$ node queue-data-structure.js
1
2
3
[ 1, 2, 3 ]
1
[ 2, 3 ]
2
2

How fast to insert/delete/access/search data

⬆️ Time complexity (worst case) per operation

Real life interview questions

1. What is the Queue data structure usually used for? Give 3 different examples.
2. What is the distinct feature of Queue structure? What's its short, 4 characters name?
3. Write your own Queue data structure with these operations: enqueue, dequeue, peek, size, print.
4. How do you insert/delete/access/search with Queue data structure?
5. What is the Time Complexity of Queue data structure on insert/delete/access/search operation?

6. Implement an online ticket vending system for a famous, desirable music concert:

   • Input:
   • a million of users click buy tickets almost at the same time.
   • there are only 40,000 seats available in the stadium.
   • Output:
   • the first 40,000 requests to buy will receive a ticket and confirmation.
   • the rest will receive a sold out notice.