💡
My Docs
BlogLinkedin
WEB_DEV_JOB_SEARCH
WEB_DEV_JOB_SEARCH
  • Home
  • 🏡Home
  • 🗺️Navigation
  • 📥Useful Downloads
  • TO DO
    • Meetings:
    • Take Home Assignments
  • Jobs To Apply To
  • 🛠️Skills
    • 🍢My Stack
    • E-Engineering
    • SQL / PSQL
  • 📋Filling Out Forms
  • 📖Resources
    • Linkedin Cheat Shee
    • Job Search Advice
    • Orientation:
    • Links
    • Running List Of MISC Resources:
    • ❄️Cold Outreach Generator
  • Profiles
  • Linkedin
  • Examples
  • Resume
    • Resume
      • Certificate (Lambda)
      • Examples
      • Advice
      • Dice
      • Linkedin Resume
      • Indeed Resume
  • Applications
    • 🖱️TRACKING_APPLICATIONS
    • Amazon
  • Applications & Job Postings
    • Job Boards
      • More Job Boards
    • 📮Postings:
      • Avid / Pro Tools
      • Amazon
      • My Applications
        • Application Info
        • In Progress
      • First Round Of Applications
      • Jobs To Keep Track Of
      • Recommended Jobs
  • Cover Letter
    • Cover Letter
      • CV-Guidance
    • More Advice
      • Practice Problems:
    • Example
    • Example Of Developer Bio
    • Old Engineering Cover Letter
  • Portfolio
    • 💾Git Repo
    • 🖼️Portfolio
  • 📈Slack&Lambda
    • 📺Recordings
    • 🧑‍🤝‍🧑🧑🤝🧑 🧑🤝🧑 🧑People
  • Aux-Resources
    • Youtube
    • 👨‍🏫👨🏫 👨🏫 👨Guidance
  • 🖋️Interview Prep
    • INTERVIEW
    • 👨‍💻👨💻 👨💻 👨💻 👨💻 👨💻 👨💻 👨💻 Leetcode
      • 37-Essential-Js-Questions
      • 📈Rubric
    • Resources
      • List of List
      • Cheat-Sheet
    • Cheat-Sheet-Raw
    • General Advice & Tips
      • Website Checklist
      • Phone Interview Advice
    • Overview
      • Data-Structures Q & A
    • Web Dev Interview Questions
      • FULL-STACK DEVELOPER INTERVIEW QUESTIONS AND ANSWERS
    • ⁉️Interview Questions.
      • cross-site scripting attack (XSS) and how do you prevent it?
      • What are refs in React? When should they be used?
      • virtual DOM and why is it used in libraries/frameworks?
      • What does the following code evaluate to?
      • What is the this keyword and how does it work?
      • What are landmark roles and how can they be useful?
      • What is the difference between lexical scoping and dynamic scoping?
      • What is the difference between null and undefined?
      • What is CSS BEM?
      • What is HTML5 Web Storage? Explain localStorage and sessionStorage.
      • How can you avoid callback hells?
      • What is functional programming?
      • useful example of one?
      • What is an async function?
      • What is the difference between the equality operators == and ===?
      • use-strict
      • sync-vs-async
      • null-vs-undefined
      • promises
      • accessibility-tree
        • imperative-vs-declarative
      • bem
      • cors
      • alt-attribute
    • Qualitative Questions
      • Cheat Sheets
        • Python-VS-JS Cheat Sheet
        • 🐍Python
      • React Interview
        • React Questions:
      • Front End Questions
    • 🧮DS_ALGO Practice:
      • Algorithms
      • Exampes
      • DS_ALGO_NOTES
        • The queue data structure (JS)(PY)
    • Behavorial
      • Python Subpage
      • DS_&_ALGO_STUDY_GUIDE
      • Intro 2 Graphs:
      • Graphs
        • Graph (py)
      • Free Code Camp
      • Types Of Data Structures
      • Arrays
      • Page 2
      • 🥅Hash Tables
    • FANG PREP (medium article)
    • ⏱️More Practice:
    • 300 React Q & A's
      • 💸React Tips
    • Redux
    • 🛕Examples
      • Representing A Graph:
      • Anagrams & Big O
        • Python Performance
        • Strongly Connected Graph
      • Gists
    • Common Knowledge Questions
  • Tutorials
    • Custom Outreach Message Generator
      • Common Questions
      • Self Introduction
  • Technical Interview Tutorial
  • Job Boards
    • 📋Job Boards
      • Less Promising Job Boards
      • LIST OF BOARDS
  • Networking
    • 🗓️Events
  • MISC
    • Articles To Read
    • Job Search Images
  • Notes
    • Interview Navigation
    • Notes
    • CSS Interview Prep Quiz
  • 🖨️Interviewing
    • General
    • Inspiration
    • Front End Interview
    • Common Questions
  • Networking
    • Networking
      • a/A Email List
    • Page 1
  • 📓ARCHIVE
    • Archive
      • ❇️Slack Announcements
    • Projects
Powered by GitBook
On this page
  • The queue data structure
  • 2. The operations on queues
  • 3. Implementing a queue in JavaScript
  • 4. Summary

Was this helpful?

Edit on GitHub
  1. Interview Prep
  2. DS_ALGO Practice:
  3. DS_ALGO_NOTES

The queue data structure (JS)(PY)

PreviousDS_ALGO_NOTESNextBehavorial

Last updated 3 years ago

Was this helpful?

The queue data structure

If you enjoy traveling (like I do), most likely you passed the check-in process at the airport. If there are a lot of travelers willing to check-in, naturally a queue of people is formed at the check-in desk.

A traveler who's just entered the airport and wants to check-in is going to enqueue into the queue. Another traveler that has just passed the check-in process at the desk is dequeued from the queue.

This is the real-world example of a queue — and the queue data structure works the same way.

The queue is a type of First Input-First Output (FIFO) data structure. The first enqueued item (input) is the first to dequeue (output).

A queue has 2 pointers: head and tail. The earliest enqueued item in the queue is at the head, while the latest enqueued item is at the tail of the queue.

Recalling the airport example, the traveler at the check-in desk is the head of the queue. The traveler who has just entered the queue is at the tail.

From a higher-point of view, the queue is the data structure that lets you process items, one at a time, in the same order they come in.

2. The operations on queues

The queue supports 2 main operations: enqueue and dequeue. Additionally, you might find it useful to have the peek and length operations.

2.1 Enqueue operation

The enqueue operation inserts an item at the tail of the queue. The enqueued item becomes the tail of the queue.

The enqueue operation in the picture above inserts the item 8 at the tail. 8 becomes the tail of the queue.

queue.enqueue(8);

2.2 Dequeue operation

The dequeue operation extracts the item at the head of the queue. The next item in the queue becomes the head.

In the picture above the dequeue operation returns and removes the item 7 from the queue. After dequeue, item 2 becomes the new head.

queue.dequeue(); // => 7

2.3 Peek operation

The peek operation reads the head of the queue, without altering the queue.

Item 7 is the head of the queue in the picture above. The peek operation simply returns the head — the item 7 — without modifying the queue.

queue.peek(); // => 7

2.4 Queue length

Length operation counts how many items the queue contains.

The queue in the picture has 4 items: 4, 6, 2, and 7. As result, the queue length is 4.

queue.length; // => 4

2.5 Queue operations time complexity

What's important regarding all of the queue operations — enqueue, dequeue, peek and length — all these operations must be performed in constant time O(1).

The constant time O(1) means that no matter the size of the queue (it can have 10 or 1 million items): the enqueue, dequeue, peek and length operations must be performed at relatively the same time.

3. Implementing a queue in JavaScript

Let's look at a possible implementation of the queue data structure while maintaining the requirement that all operations must perform in constant time O(1).

class Queue {  constructor() {    this.items = {};    this.headIndex = 0;    this.tailIndex = 0;  }  enqueue(item) {    this.items[this.tailIndex] = item;    this.tailIndex++;  }  dequeue() {    const item = this.items[this.headIndex];    delete this.items[this.headIndex];    this.headIndex++;    return item;  }  peek() {    return this.items[this.headIndex];  }  get length() {    return this.tailIndex - this.headIndex;  }}const queue = new Queue();queue.enqueue(7);queue.enqueue(2);queue.enqueue(6);queue.enqueue(4);queue.dequeue(); // => 7queue.peek();    // => 2queue.length;    // => 3

const queue = new Queue() is how you create an instance of a queue.

Calling queue.enqueue(7) method enqueues the item 7 into the queue.

queue.dequeue() dequeues a head item from the queue, while queue.peek() just peeks the item at the head.

Finally, queue.length shows how many items are still in the queue.

Regarding the implementation: inside the Queue class the plain object this.items keeps the items of the queue by a numerical index. The index of the head item is tracked by this.headIndex, and the tail item is tracked by this.tailIndex.

Queue** methods complexity**

queue(), dequeue(), peek() and length() methods of the Queue class use only:

  • Property accessors (e.g. this.items[this.headIndex]),

  • Or perform aritmetical operations (e.g. this.headIndex++)

Thus the time complexity of these methods is constant time O(1).

4. Summary

The queue data structure is a type of First Input First Output (FIFO): the earliest enqueued item is the earlies to dequeue.

The queue has 2 main operations: enqueue and dequeue. Additionally, queues can have helper operations like peek and length.

All queue operations have to be performed in constant time O(1).

Queue Data Structure
Queue: Enqueue Operation
Queue Data Structure: Dequeue Operation
Queue Data Structure: Peek Operation
Queue Data Structure: Length

🖋️
🧮
Try the demo.
Airport Check-In Queue