Data Structures — Queues
Algorithms and Data Structures From Zero to Hero
Intro
In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. The operations of a queue make it a first-in-first-out (FIFO) data structure. — Wikipedia
We define a queue to be a list in which all insertions to the list are made at one end, and all deletions from the list are made at the other end. The element which is first pushed into the order, the operation is first performed on that.
Analogy
A queue works exactly as does in real life. Suppose you are in the supermarket and when it is time to pay there is a queue where you have to wait, the first one in is the first one out and the last one in is the last one out (FIFO).
Time complexity
- Enqueue O(1)
- Dequeue O(1)
Implementation
Sequential allocation: You can implement a queue using an array, and it can be organise a limited number of elements.
Linked list allocation: using a linked list, in which it can organise an unlimited number of elements.
Summary
- The queue is called FIFO data structure: First In, First Out.
- The main operations of a queue are enqueue (addition at the end of the queue) and dequeue (deletion from the front end).
