Queue Flashcards
Queue definition
Like Stack data structure, Queue is also a linear data structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO), which means that the element that is inserted first in the queue will be the first one to be removed from the queue. A good example of queue is any queue of consumers for a resource where the consumer who came first is served first.
The difference between stacks and queues is in removing. In a stack, we remove the most recently added item; whereas, in a queue, we remove the least recently added item.
Operations on Queue: Mainly the following four basic operations are performed on queue:
Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.
Applications of queue
Queue is used when things don’t have to be processed immediatly, but have to be processed in First InFirst Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios:
When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
Queue implementation using arrays
// C++ program to implement a queue using an array #include (bits/stdc++.h> using namespace std;
struct Queue {
int front, rear, capacity;
int* queue;
Queue(int c)
{
front = rear = 0;
capacity = c;
queue = new int;
}
~Queue() { delete[] queue; }
// function to insert an element
// at the rear of the queue
void queueEnqueue(int data)
{
// check queue is full or not
if (capacity == rear) {
printf("\nQueue is full\n");
return;
}
// insert element at the rear
else {
queue[rear] = data;
rear++;
}
return;
}
// function to delete an element
// from the front of the queue
void queueDequeue()
{
// if queue is empty
if (front == rear) {
printf("\nQueue is empty\n");
return;
}
// shift all the elements from index 2 till rear
// to the left by one
else {
for (int i = 0; i ( rear - 1; i++) {
queue[i] = queue[i + 1];
}
// decrement rear rear--; } return; }
// print queue elements
void queueDisplay()
{
int i;
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
// traverse front to rear and print elements
for (i = front; i ( rear; i++) {
printf(" %d (-- ", queue[i]);
}
return;
}
// print front of queue
void queueFront()
{
if (front == rear) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[front]);
return;
}
};
// Driver code
int main(void)
{
// Create a queue of capacity 4
Queue q(4);
// print Queue elements q.queueDisplay();
// inserting elements in the queue q. queueEnqueue(20); q. queueEnqueue(30); q. queueEnqueue(40); q. queueEnqueue(50);
// print Queue elements q.queueDisplay();
// insert element in the queue q.queueEnqueue(60);
// print Queue elements q.queueDisplay();
q. queueDequeue();
q. queueDequeue();
printf("\n\nafter two node deletion\n\n");
// print Queue elements q.queueDisplay();
// print front of the queue q.queueFront();
return 0; }
Implementation of a queue using a LinkedList.
#include (bits/stdc++.h> using namespace std;
struct QNode {
int data;
QNode* next;
QNode(int d)
{
data = d;
next = NULL;
}
};
struct Queue {
QNode *front, *rear;
Queue()
{
front = rear = NULL;
}
void enQueue(int x)
{
QNode* temp = new QNode(x);
if (rear == NULL) {
front = rear = temp;
return;
}
rear->next = temp;
rear = temp;
}
void deQueue()
{
if (front == NULL) return; QNode* temp = front; front = front->next; if (front == NULL) rear = NULL; delete (temp); } };
int main()
{
Queue q; q.enQueue(10); q.enQueue(20); q.deQueue(); q.deQueue(); q.enQueue(30); q.enQueue(40); q.enQueue(50); q.deQueue(); cout (( "Queue Front : " (( (q.front)->data (( endl; cout (( "Queue Rear : " (( (q.rear)->data; } Queue Front : 40 Queue Rear : 50
Can we traverse on queues ?
We cannot access queue elements randomly as they are not stored at contigous memory locations. Hence, we cannot use loops or iterators to traverse queues.
Problem: Given a number n, print first n numbers in increasing order such that all these numbers have digits in set {5, 6}.
Examples:
Input : n = 10
Output : 5, 6, 55, 56, 65, 66, 555,
556, 565, 566
Input : n = 4
Output : 5, 6, 55, 56
Note: n can be a big number and the result values might not fit in basic data types like long int or long long int.
Approach: We create a queue and add string element “5 and “6” to the queue. Then we run the loop n number of times and every time pop the top element and add two successive elements into the queue. The successive elements or the increasing order of the combination of 5 and 6 can be achieved by implementing a tree in the following way. In this tree, the node is an empty string followed by the successive combinations of 5 and 6, as shown in this picture.
For every node, we add 5 to the left node and 6 to the right node, thus getting every combination of 5 and 6. If the tree is traversed level-wise from left to right, then we get the required numbers in increasing order.
// CPP program to generate n number // using digits 5 and 6 #include #include using namespace std;
// Function to generate numbers
void printFirstN(int n)
{
// Sample queue
queue q;
// Pushing elements 5 and 6 to
// the queue
q.push("5");
q.push("6");
// for loop to generate n numbers
for (int count = 0; count < n; count++) {
// Getting the root node
string curr = q.front();
// Displaying the number
cout << curr << " ";
// Popping out the element
q.pop();
// Pushing element by appending 5
// on left side
q.push(curr + "5");
// Pushing element by appending 6
// on right side
q.push(curr + "6");
}
}
// Driver Method
int main()
{
int n = 5;
printFirstN(n);
return 0;
}
Working of the Loop for n = 5 When count = 0, q -> 5, 6 curr = 5 Print: 5 q -> 6, 55, 56
When count = 1, q -> 6, 55, 56 curr = 6 Print: 5 6 q -> 55, 56, 65, 66
When count = 2, q -> 55, 56, 65, 66 curr = 55 Print: 5 6 55 q -> 56, 65, 66, 555, 556
When count = 3, q -> 56, 65, 66, 555, 556 curr = 56 Print: 5 6 55 56 q -> 65, 66, 555, 556, 565, 566
When count = 4, q -> 65, 66, 555, 556, 565, 566 curr = 65 Print: 5 6 55 56 65 q -> 66, 555, 556, 565, 566, 655, 656
Time Complexity: O(n)
Write a program for queue traversal
void TraveseMe(queue myqueue){
// Your code here
// Use front function
while(!myqueue.empty()) {
cout << myqueue.front();
myqueue.pop();
}
}
Queue reversal
queue rev(queue q)
{
// add code here.
queuet;
int s=q.size();
vectorvect;
int x=0;
for(int i=0;i<=s;i++){
x=q.front();
vect.push_back(x);
q.pop();
}
int i=s-1;
while(i!=-1){
t.push(vect[i]);
i--;
}
return t;
}Implement queue from two stacks
For the pop function: first push all the elements in one of the stack. The elements in the other stack will be filled in the reverse order, which means the first element in the s1 will be at the top in s2. Pop the element from the s2, which will satisfy the condition for the queue(i,e. FIFO).
#include using namespace std;
class myQueue {
stack s1;
stack s2;
void push(int data) {
s1.push(data);
}
int pop() {
while(!s1.empty()) {
s2.push(s1.pop());
}
int ans = s2.pop();
while(!s2.empty()) {
s1.push(s2.pop());
}
return ans;
}
}
int main() {
return 0;
}
