Implementation of queue using Array in C
Introduction
Data structures are crucial in computer science because they provide effective information storage and retrieval. This kind of data structure includes queues, which follow the FIFO (First-In-First-Out) concept. The C programming language's array-based queue implementation will be discussed in this article. By the conclusion, you will be able to design, manage, and use a queue to handle various issues effectively.
Understanding the Queue Data Structure
An abstract data type called a queue is a queue that looks like a real queue. A queue data structure's contents are stored and retrieved in a precise sequence, just as individuals waiting in a queue do. The first thing to go is always the thing that came in initially. The abbreviation FIFO, or "First-In-First-Out," refers to this theory.
How do Queues work?
Data structures called queues adhere to the FIFO (First-In-First-Out) concept. They operate using the ideas of the enqueue and dequeue procedures.
Main Operations of a Queue
1.Enqueue:
- It is added to the back (end) of the queue when an element is enqueued.
- The element switches between the front and rear elements if the queue is empty.
- The rear pointer is changed to point to the new element if the queue is not empty before the new element is inserted following the existing rear element.
2. Dequeue:
- Dequeued elements are removed from the front of the queue.
- Nothing will require dequeueing if the queue is empty.
- If elements are still in the queue after the front element, they are discarded, and the front pointer is changed to refer to the subsequent element.
Algorithm for Enqueue:
- Step1: IF REAR = MAX_SIZE-1
print “OVERFLOW”
Go to step
[END OF IF]
- Step2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR +1
[END OF IF]
- Step3: set QUEUE[REAR] = NUM
- Step4: EXIT
Flow chart of Enqueue:
Algorithm for Dequeue:
- Step1: IF FRONT = -1 or FRONT > REAR
print “UNDERFLOW”
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
- Step2: EXIT
Flow chart of Dequeue:
Implementation :
#include<stdio.h> #define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1, rear =-1; void enqueue(int value){ if (rear == MAX_SIZE - 1) { printf("Queue is full. Enqueue operation failed. "); } else { if (front == -1) { front = 0; } rear++; queue[rear] = value; printf("Element %d enqueued successfully. ", value); } } void dequeue() { if (front == -1) { printf("Queue is empty. Dequeue operation failed. "); } else { int removedElement = queue[front]; if (front == rear) { front = rear = -1; // Reset the pointers for an empty queue } else { front++; } printf("Element %d dequeued successfully. ", removedElement); } } int main() { // Enqueue elements enqueue(10); enqueue(20); enqueue(30); enqueue(40); // Dequeue elements dequeue(); dequeue(); dequeue(); dequeue(); // Try to dequeue when the queue is empty dequeue(); return 0; }
Output:
Time Complexity and Space Complexity
An array-based queue's enqueue, and dequeue operations have the following time and space complexity:
1.Enqueue:
- Time Complexity:0(1)
- An element is queued when initially added, the rear pointer is adjusted, and the element is subsequently allocated to the proper location in the array. No matter how many components are in the queue, these tasks require the same time.
- Space Complexity:0(1)
- Besides the array, no additional space is needed while queuing an element. The space complexity does not change as the queue size grows.
2. Dequeue:
- Time Complexity:0(1)
- When an element is dequeued, it is removed from the front of the queue, the front pointer is updated, and maybe other elements are moved to fill the empty space. However, not every dequeue process involves a shifting action. Rather, it is only necessary when the number of dequeues equals the queue's maximum size. As a result, the time complexity for Dequeue generally stays the same.
- Space Complexity:
- Aside from the array itself, no additional space is needed when an element is dequeued. As the queue size gets smaller, the space complexity stays the same.
Terminology used
- Queue: A data structure based on the FIFO principle, where components are inserted from the back and deleted from the front.
- Enqueue: the action of pushing a component to the end of the queue.
- Dequeue: a procedure where a queue item is deleted from the front.
- Front: A pointer that keeps track of the first element in the queue.
- Rear: a pointer that tracks the final item in the queue.
- Array: a fixed-size container used to keep the queue's components in place.
- MAX_SIZE: a constant that indicates how many items the queue may contain in total.
- Overflow: the circumstance where further components cannot be added because the queue is full.
- Underflow: when no components are in the queue, and they cannot be deleted.
- Print: A function used to print output messages to the console.
- -1: A sentinel value indicates an empty queue or an uninitialized pointer.
Drawbacks
1.Wasted Memory:
As a result of items being dequeued, the array may wind up having unused memory at the head of the queue if the queue is subjected to a succession of enqueue and dequeue operations. Memory is wasted because this useless memory cannot be recovered or utilized by other program components.
2. Fixed Size:
The queue's size is predetermined at the time of declaration because arrays are used to construct it. This fixed size may result in two possible problems. The queue may first overflow if more elements are added than it can hold if the size is too small. Second, RAM may be wasted if the size is too large and the queue is not completely utilized.
3. Inefficient Memory Management:
No matter how many elements are currently in the queue, memory is allocated for the queue's maximum capacity in an array-based implementation. This may lead to wasteful memory consumption, particularly if the queue's size fluctuates often or if the maximum capacity is significantly more than the queue's average element count.
4. Shifting Elements:
All the array's items must be moved to fill the space at the front when a dequeue action is performed. Iterating through the array and shifting each element one position to the left is required for this shifting procedure. This shifting procedure might be time-consuming and impact the program's overall performance in cases when the queue is big or has a lot of components.
5. Limited Dynamicity:
The queue's size cannot be changed dynamically in the array-based approach. If it fills up, the queue cannot automatically grow to include more elements. The solution might become more difficult and error-prone if extra logic and memory reallocation were needed to grow the array to get around this restriction dynamically.