Creating a Queue with O(1) Operations

NOTE

For this problem, familiarity with queues, hash tables, and linked lists would help.

Instructions

Create a queue data structure with O(1) insertion, deletion, and size calculation.

---

Queue

A queue is a data structure that keeps track of data in the order in which it was entered. Items are inserted into the back of the queue and removed from the front of the queue.

A real-world analogy would be a line at a grocery store. Everyone enters the line at the back. The first person who enters will be the first person served.

Common operations available to perform on a queue are:

• enqueue, or adding someone to the back of the queue
• dequeue, or removing someone from the front of the queue
• size, or checking the number of items in the queue

A common interview question is to create a queue that can perform each of these operations in constant-time. There are two common ways to do this.

Feel free to try it yourself first. There are many correct ways to complete this, so we won’t have prepared tests for it.

---