Queue is a linear data structure in which elements are stored in First In First Out (FIFO) order. This means that the first element that was inserted into the queue will be the first one to be removed. The queue implements the following operations: Enqueue, Dequeue, IsEmpty, IsFull, and Peek [1].
A queue is defined as a linear data structure that is open at both ends and all additions to the list are made at one end and all deletions from the list are made at the other end [2].
One way to implement a queue using an array is to create an array "arr" of size "n" and two variables, "front" and "rear", both of which will be initialized to 0, meaning that the queue is currently empty. "Rear" is the index up to which the elements are stored in the array, and "front" is the index of the first element in the array [3].
As an example, let's consider a scenario where we have a queue of integers and we need to enqueue and dequeue elements. In this example, we use the array implementation of the queue.
c++ code
#include<bits/stdc++.h>
using namespace std;
#define MAX 100 class Queue
{int front, rear, arr[MAX];
public:
Queue()
{
front=rear=0;
}
void enqueue(int x)
{
if (rear == MAX)
{
cout<<"Queue Overflow\n";
return;
}
arr[rear]=x;
rear++;
}
void dequeue()
{
if (front == rear)
{
cout<<"Queue Underflow\n";
return;
}
front++;
}
int Front()
{
if (front == rear)
{
cout<<"Queue is Empty\n";
return -1;
}
return arr[front];
}
};
int main()
{
Queue q;
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
cout << q.Front() << endl;
q.dequeue();
cout << q.Front() << endl;
q.dequeue();
cout << q.Front() << endl;
q.dequeue();
q.dequeue();
return 0;
}
In the above code, we create a class Queue with the enqueue, dequeue, and Front operations. The enqueue operation adds an element to the end of the queue, the dequeue operation removes an element from the front of the queue, and the Front operation returns the value of the front element without removing it. The size of the queue is defined by the variable 'n' and the front and rear variables are initialized to 0, indicating that the queue is currently empty. The enqueue operation first checks if the queue is full by comparing the value of rear with n-1. If the queue is full, it returns a message indicating that the queue is full. If the queue is not full, the element is added to the end of the queue, and the rear variable is incremented by 1. The dequeue operation first checks if the queue is empty by comparing the values of front and rear. If the queue is empty, it returns a message indicating that the queue is empty. If the queue is not empty, the front element is removed and the front variable is incremented by 1. The Front operation simply returns the value of the front element without removing it. [3].
We also implement the isFull and isEmpty methods to check the state of the queue. The isFull method returns true if the "rear" value is equal to the size of the queue array, and the isEmpty method returns true if the "front" value is equal to the "rear" value, meaning there are no elements in the queue.
In Python, we can implement a queue using a list or a collections.deque object. The collections.deque object offers more efficient appending and popping from both ends, making it a good choice for implementing a queue.
Here's an example of implementing a basic queue using a collections.deque object:
python code
from collections import deque
queue = deque()
# Adding elements to the queue
queue.append(1)
queue.append(2)
queue.append(3)
# Removing elements from the queueprint(queue.popleft()) # Output: 1print(queue.popleft()) # Output: 2print(queue.popleft()) # Output: 3In the above code, we import the deque object from the collections module and create an instance of it. We then use the append method to add elements to the queue and the popleft method to remove elements from the front of the queue.
This is just a simple example of implementing a queue in Python. There are many other ways to implement a queue, and the best method will depend on your specific use case. Regardless of the implementation, understanding the basic principles of a queue and how to use it in your code is a valuable tool in any programmer's toolkit.
In conclusion, the queue data structure is useful for implementing first-in-first-out (FIFO) operations and can be implemented using an array as shown in this example.
References
[1] "A queue is an object (an abstract data structure - ADT) that allows the following operations: Enqueue: Add an element to the end of the queue Dequeue: Remove an element from the front of the queue IsEmpty: Check if the queue is empty IsFull: Check if the queue is full Peek: Get the value of the front of the queue without removing it" URL: https://www.programiz.com/dsa/queue
[2] "What is Queue Data Structure? A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order. We define a queue to be a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end." URL: https://www.geeksforgeeks.org/queue-data-structure/
[3] "To implement a queue using an array, create an array arr of size n and take two variables front and rear both of which will be initialized to 0 which means the queue is currently empty. Element rear is the index up to which the elements are stored in the array and front is the index of the first element of the array." URL: https://www.geeksforgeeks.org/array-implementation-of-queue-simple/
Comentarios