Queue - Data structure

Queue is data structure like array and stack. But here the first element added to the queue, will be the first element removed from the queue. So queue called first in first out (FIFO) or first come first serve

We can in queue:

Enqueue(Key): To add key to collection
Key Dequeue(): To remove and return least recently-added key
Boolean Empty(): means,, Are there any elements?

Queue implementation:

We can implement queue in several way (Linked list, Array, 2 Stack).

Queue implementation with linked list:

There two things we must to know:

The first : When we enqueue, we are going to push to the back of the linked list
The second : To make sure the the queue list is empty , we make sure if the head is null or not

Here the code using linked list:

Queue implementation with array:

It’s easy to implement queue using array but pay attention in this case.

When we want to enqueue(g) maybe causes error!! WHY??

This case occurred when we have array say with size (5) but this array have (4) occupied by values

Here example:

if we did enqueue(g), The read and write would be both 2

• And it would be hard to distinguish read and write index 2 because the queue is full
• Or read and write index both 2 because the queue is empty
• So we have a buffer of at least one that can’t be written to make sure read and write are separate and and distinct if the queue isn’t empty

Notice:
one distinction between the array and linked list implementation
is that in the array implementation we have a maximum size that the queue can grow to so it is bounded

Here the code using array:

Queue time complexity

Cost for doing a dequeue and enqueue , all are O(1). And there is no “worst case”

Finally … Here you can find how to implement queue using 2 stack and all source code in c++