Data Structure in Swift (Queue) — Part 5

Nitin Aggarwal

5 min readMar 15, 2020

In this series, previously we have learned about Array & Dictionary, Singly Linked List, Stack, and Doubly Linked List

In this section, we’ll learn about the implementation of the Queue.

What is the Queue and comparison with Stack?

A Queue is a linear data structure that follows the FIFO (First-In-First-Out) pattern for insertion and deletion.
The difference between Queue and Stack is in deletion. In Stack, we remove the item which is last added but in Queue, we remove the item which is least recently added.

Queue Operations?

Enqueue: To insert an item from the rear
Dequeue: To delete an item from the front
Front: To get the first item
Rear: To get the last item

Some real-life examples of Queue?

Breadth-First Search uses the Queue mechanism
CPU and Disk scheduling among multiples processes
To performs multiple tasks asynchronously. Example: NSOperationQueue

What is the Priority Queue?

A Priority Queue is an extension of the Queue in which every item has a priority associated with it. An element with high priority is dequeued before an item with low priority. If more than one items have the same priority, they will serve according to the order they added. Examples: CPU scheduling, Dijkstra’s shortest path algorithm, and others.

What is the Deque (Double Ended Queue)?

It is a generalized form of Queue data structure that allows insertion and deletion at both ends (Front & Rear). Deque allows us both Stack and Queue operations or we can use it as both.

What is the Circular Queue?

It is an extension of the Queue data structure in which the last item is connected with the first item or the first index comes right after the last index. You can think of a circular queue as a Ring Buffer.

How we can implement the Queue data structure?

Using Array
Using Linked List (Singly or Doubly)
Using Ring Buffer (Circular Queue)
Using Two Stacks

1) Implement Queue using Array

Let’s see some important points here of Queue using Array:

Enqueue an element is an O(1) as we are appending an element at last position.
Dequeue an element is an O(n) as we are removing an element from the first position due to this all the remaining elements in the array to be shifted.

Note: When you insert an element in Array, it’s automatically resized (almost double) when required. So removing an element from the front causes shifted all the elements in the array. This makes a big impact on very large queues.
Once the array gets full, it has to resize and it may have many unused spaces in memory that may increase your memory space and time.

To overcome this problem, we can implement the Queue using Linked List.

2) Implement Queue using Linked List (Singly)

Let’s see implement the Queue using Singly Linked List (we can also use Doubly Linked List).

enqueue: We are inserting the element in last. Using rear reference, just adding a new node in last.
dequeue: We are removing the element from the front. Using front reference, just removing the first node in the queue.

Note: Enqueue and Dequeue an element both are constant time based operations i.e. O(1)

3) Implement Queue using Ring Buffer (Circular Queue)

In Queue with Linked list, while enqueueing an element, each time it requires dynamic memory allocation which is extra overhead. But in Queue with array-based, it does allocate memory in bulk only when required which is faster.

But if you have a fixed size queue, we have another good solution i.e. Circular Queue. (Introduction about Circular Queue has given in starting of this story)

As the queue size is fixed in the Circular queue, so the enqueue operation can be failed after overflowing the queue.
Note: Enqueue and Dequeue an element both are constant time based operations i.e. O(1)

4) Implement Queue using two stacks

Note: Enqueue and Dequeue an element both are constant time based operations i.e. O(1)

This is how the two-stacks implementation works as:

Left Stack: All the dequeue operations will be performed on it.
Right Stack: All the enqueue operations will be performed on it.

enqueue():

Append an element in the right stack’s array. So this is a constant time O(1) operation.

dequeue():

If queue (both stacks) is empty, then queue in the underflow.
If the left stack is empty, set all the elements in reverse order from the right stack.
Make the right stack is empty.
Remove the last element from the left stack.

Note: With two stacks, it is a dynamic approach and no restriction here about the size like Circular Queue.

This implementation is better than other ways because it is an array-based implementation. Because in an array, all the elements stored are in contiguous allocation indexes. So a large number of elements will be loaded into cache at first access.

Please reply if you have any questions or suggestions. I hope, you really enjoyed this article, so don’t forget to claps (up to 50* if you found it useful) on it and share it with others.
Get the full source code here: GitHub

Other Stuff

See the previous stories of this series ‘Data Structure’:

See the other stories on iOS (Swift):

Happy Coding !!
Nitin A