Queue Operations
Last Updated :
18 Feb, 2023
The queue is an abstract data type which is defined by following structure and operations.
Queue is structured as an ordered collection of items which are added at one end called rear end, and other end called front end.
The queue operations are as follows:
- create
- enqueue
- dequeue
- isEmpty
- isFull
- size
1) create : Creates and initializes new queue that is empty, it does not require any parameter and returns an empty queue.
2) enqueue: Add a new element to the rear of queue . It requires the element to be added and returns nothing.
3) dequeue: removes the elements from the front of queue. It does not require any parameters and returns the deleted item.
4) isEmpty: Check the whether the queue is empty or not. It does not require any parameter and returns a Boolean value.
Given N integers, the task is to insert those elements in the queue. Also, given M integers, the task is to find the frequency of each number in the Queue.
Examples:
Input:
N = 8
1 2 3 4 5 2 3 1 (N integers)
M = 5
1 3 2 9 10 (M integers)
Output:
2 2 2 -1 -1
Explanation:
After inserting 1, 2, 3, 4, 5, 2, 3, 1 into the queue, frequency of 1 is 2, 3 is 2, 2 is 2, 9 is -1 and 10 is -1 (since, 9 and 10 is not there in the queue).
Input:
N = 5
5 2 2 4 5 (N integers)
M = 5
2 3 4 5 1 (M integers)
Output:
2 -1 1 2 -1
Approach: The given problem can be solved by using a simple queue. The idea is to insert N integers one by one into the queue and then check the frequency of M integers. Separate functions will be created to perform both operations. Follow the steps below to solve the problem.
- Create a queue and push all given integers into the queue.
- After pushing all the elements into the queue create another function for counting the frequency of given M elements one by one.
- Take a variable cntFrequency to keep track of frequency of current element.
- Pop all the elements from queue till its size and each time check if current element in queue is equal to element for which we are checking for frequency.
– if both are equal, increment cntFrequency by 1
– else, do nothing.
- Push the current element back to the queue so that for next case queue will not get disturbed.
- Print the frequency of each element found.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
class Geeks
{
public:
void insert(queue<int> &q, int k)
{
q.push(k);
}
int findFrequency(queue<int> &q, int k)
{
int cntFrequency = 0;
int h = q.size();
while (h)
{
h = h - 1;
int x = q.front();
q.pop();
if (x == k)
{
cntFrequency += 1;
}
q.push(x);
}
return cntFrequency;
}
};
int main()
{
queue<int> q;
int N = 8;
int a[N] = {1, 2, 3, 4, 5, 2, 3, 1};
int M = 5;
int b[M] = {1, 3, 2, 9, 10};
Geeks obj;
for (int i = 0; i < N; i++)
{
obj.insert(q, a[i]);
}
for (int i = 0; i < M; i++)
{
int f = obj.findFrequency(q, b[i]);
if (f != 0)
{
cout << f << " ";
}
else
{
cout << ("-1") << " ";
}
}
}
|
Java
import java.io.*;
import java.util.*;
class GFG {
public static void main(String[] args)
{
Queue<Integer> q = new LinkedList<>();
int N = 8;
int[] a = new int[] { 1, 2, 3, 4, 5, 2, 3, 1 };
int M = 5;
int[] b = new int[] { 1, 3, 2, 9, 10 };
Geeks obj = new Geeks();
for (int i = 0; i < N; i++) {
obj.insert(q, a[i]);
}
for (int i = 0; i < M; i++) {
int f = obj.findFrequency(q, b[i]);
if (f != 0) {
System.out.print(f + " ");
}
else {
System.out.print("-1"
+ " ");
}
}
}
}
class Geeks {
static void insert(Queue<Integer> q, int k)
{
q.add(k);
}
static int findFrequency(Queue<Integer> q, int k)
{
int cntFrequency = 0;
int size = q.size();
while (size-- != 0) {
int x = q.poll();
if (x == k) {
cntFrequency++;
}
q.add(x);
}
return cntFrequency;
}
}
|
Python3
import collections
class Geeks:
def insert(self, q, k):
q.append(k)
def findFrequency(self, q, k):
cntFrequency = 0
size = len(q)
while (size):
size = size - 1
x = q.popleft()
if (x == k):
cntFrequency += 1
q.append(x)
return cntFrequency
q = collections.deque()
N = 8
a = [1, 2, 3, 4, 5, 2, 3, 1]
M = 5
b = [1, 3, 2, 9, 10]
obj = Geeks()
for i in range(N):
obj.insert(q, a[i])
for i in range(M):
f = obj.findFrequency(q, b[i])
if (f != 0):
print(f, end=" ")
else:
print("-1", end=" ")
print(" ")
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public class Geeks {
public void insert(Queue<int> q, int k)
{
q.Enqueue(k);
}
public int findFrequency(Queue<int> q, int k)
{
int cntFrequency = 0;
int size = q.Count;
while (size-- != 0) {
int x = q.Peek();
q.Dequeue();
if (x == k) {
cntFrequency++;
}
q.Enqueue(x);
}
return cntFrequency;
}
}
public static void Main()
{
Queue<int> q = new Queue<int>();
int N = 8;
int[] a = new int[] { 1, 2, 3, 4, 5, 2, 3, 1 };
int M = 5;
int[] b = new int[] { 1, 3, 2, 9, 10 };
Geeks obj = new Geeks();
for (int i = 0; i < N; i++)
{
obj.insert(q, a[i]);
}
for (int i = 0; i < M; i++)
{
int f = obj.findFrequency(q, b[i]);
if (f != 0)
{
Console.Write(f + " ");
}
else {
Console.Write("-1"
+ " ");
}
}
}
}
|
Javascript
class Geeks {
insert(q, k) {
q.unshift(k);
}
findFrequency(q, k) {
let cntFrequency = 0;
let size = q.length;
while (size) {
size = size - 1;
let x = q.pop();
if (x == k) {
cntFrequency += 1;
}
q.unshift(x);
}
return cntFrequency;
}
}
let q = new Array;
let N = 8;
let a = [1, 2, 3, 4, 5, 2, 3, 1];
let M = 5;
let b = [1, 3, 2, 9, 10];
let obj = new Geeks;
for (let i = 0; i < N; i++) {
obj.insert(q, a[i]);
}
for (let i = 0; i < M; i++) {
f = obj.findFrequency(q, b[i]);
if (f != 0) {
console.log(f);
}
else {
console.log("-1");
}
}
|
Time Complexity: O(N*M)
Auxiliary Space: O(N)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...