CONCEPT OF QUEUE AND PROBLEM SET

Data Structure: Queue

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

To clear your concepts you can follow these steps...

Step 1: Visit this article to clear your basic theory

Step 2: Visit this article to deep-dive into Queue

Some additional see-through contents...

1. Introduction to queue

2. Implementation using Arrays

3. Implementation using Linked Lists

4. Implementation using Stack

Problem Set: Level Basic

1. Write a C Program to implement Queue with the following Operation using Array ( Solution ) :[ Theory ]

• enqueue
• dequeue
• display  

2. Write a C Program to implement Circular Queue with the same Operation using Array( Solution ): [Theory]

3. Write a C Program to implement Queue with the following Operation (using Linked List):

     [ Solution + Theory ]

• enqueue
• dequeue
• display

Problem Set: Level Intermediate

1. Check if a queue can be sorted into another queue using a stack (Solution)

2. Level Order Tree Traversal using Queue (Solution)

3. Construct a Complete Binary Tree from its Linked List Representation (Solution)

4. Reversing a queue using recursion (Solution)

5. Given an array and an integer K, find the maximum for each and every contiguous subarray of size k. (Solution)

6. ***"The Petrol Pump Problem"****

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

  1. The amount of petrol that every petrol pump has.

  2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). Expected time complexity is O(n). Assume for 1-litre petrol, the truck can go 1 unit of distance.

For example, let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where the truck can make a circular tour is 2nd petrol pump. The output should be “start = 1” (index of 2nd petrol pump). (Solution)

7. Smallest multiple of a given number made of digits 0 and 9 only

We are given an integer N. We need to write a program to find the least positive integer X made up of only digits 9’s and 0’s, such that, X is a multiple of N. (Solution)

Input : N = 5
Output : X = 90
Explanation: 90 is the smallest number made up 
of 9's and 0's which is divisible by 5.

8. Minimum time required to rot all oranges

Given a matrix of dimension m*n where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:

0: Empty cell

1: Cells have fresh oranges

2: Cells have rotten oranges 

So we have to determine what is the minimum time required so that all the oranges become rotten. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right). If it is impossible to rot every orange then simply return -1. (Solution)

9. An Interesting Method to Generate Binary Numbers from 1 to n

Given a number n, write a function that generates and prints all binary numbers with decimal values from 1 to n. (Solution)

Examples:

Input: n = 2
Output: 1, 10

Input: n = 5
Output: 1, 10, 11, 100, 101

10. First negative integer in every window of size k

Given an array and a positive integer k, find the first negative integer for each window(contiguous subarray) of size k. If a window does not contain a negative integer, then print 0 for that window. (Solution)

Examples:

Input : arr[] = {-8, 2, 3, -6, 10}, k = 2
Output : -8 0 -6 -6
First negative integer for each window of size k
{-8, 2} = -8
{2, 3} = 0 (does not contain a negative integer)
{3, -6} = -6
{-6, 10} = -6

Input : arr[] = {12, -1, -7, 8, -15, 30, 16, 28} , k = 3
Output : -1 -1 -7 -15 -15 0 

11. Check if all levels of two trees are anagrams or not

Given two binary trees, we have to check if each of their levels is anagrams of each other or not. (Solution)

Example:

Tree 1:
Level 0 : 1
Level 1 : 3, 2
Level 2 : 5, 4

Tree 2:
Level 0 : 1
Level 1 : 2, 3
Level 2 : 4, 5

As we can clearly see all the levels of above two binary trees are anagrams of each other, hence return true.

12. Check mirror in n-ary tree

Given two n-ary trees, the task is to check if they are the mirror of each other or not. Print “Yes” if they are mirror of each other else “No”. (Solution)