Binary Queue

Concepts Used:

Queues.

Difficulty Level:

Medium.

Problem Statement :

Given a number N, print all possible binary numbers with decimal values from 1 to N, but the catch is you have to do this using queue data structure and not recursion.

See original problem statement here

Test Case:

Input:
2
4
5

Output:
1 10 11 100
1 10 11 100 101

Solving Approach:

Bruteforce Approach:

  1. Run a loop from 1 to N and call decimal to binary inside the loop.
  2. Print all the binary numbers in a single line.

Efficient Approach(Using queue):

  1. Create an empty queue of strings.
  2. Enqueue 1,since it is the first binary number.
  3. Deque the value a and print it.
  4. Initialize string temp with a.
  5. Append "0" to string a and enqueue it to the queue.
  6. Append "1" to string temp and enqueue it to the queue.
  7. Repeat steps 3 to 8 until the end value.

Solutions

#include 
#include 
#define MAX 10005
char queue[MAX][20], temp[20];
int front = -1, rear = -1;
void enqueue(char *ptr)
   {
if(rear == MAX-1)
{
    return;
}
if(front == -1 && rear == -1)
    front = rear = 0;
else
    rear = rear + 1;
strcpy(queue[rear],ptr);
}
char* dequeue()
{
if(front == -1)
    printf("\nEmpty Queue");
else
{
    strcpy(temp,queue[front]);
    if(front == rear)
        front = rear = -1;
    else
        front = front + 1;
    return temp;
}
}
 void binary_numbers_using_queue()
{
char temp2[MAX];
strcpy(temp,dequeue());
printf("%s ",temp);
strcpy(temp2,temp);
strcat(temp,"0");
enqueue(temp);
strcat(temp2,"1");
enqueue(temp2);
}
 int main()
{
int t;
scanf("%d",&t);
while(t--)
{
    int n;scanf("%d",&n);
char temp[2] = "1";
enqueue(temp);
for(int i = 1; i <= n; i++)
    binary_numbers_using_queue();
    printf("\n");
    front = -1, rear = -1;
    for(int i=0;i<10005;i++)
    for(int j=0;j<20;j++)
    queue[i][j]='\0';
}
return 0;
}
#include  
using namespace std; 
void binary(int n) 
{ 
queue q; 
q.push("1"); 
while (n--) 
{  
    string a = q.front(); 
    q.pop(); 
    cout << a << " "; 
    string temp = a;  
    q.push(a.append("0"));
    q.push(temp.append("1")); 
} 
}  
int main() 
{ int t;cin>>t;
while(t--)
{int n ; 
cin>>n;
binary(n);
cout<<"\n";}
return 0; 
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class BinaryQueue {
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int t = sc.nextInt();
    while(t-->0)
    {
        int n= sc.nextInt();
        generateAndPrint(n);
        System.out.println();
    }
}
private static void generateAndPrint(int n) {
    Queue queue = new LinkedList();
    ((LinkedList) queue).add("1");
    while (n-- >0)
    {
        String s1 = queue.peek();
        queue.remove();
        System.out.print(s1+" ");
        String s2 = s1;
        ((LinkedList) queue).add(s1 + "0");
        ((LinkedList) queue).add(s2+"1");
    }
}
}
def binary(n):
	q = []
	q.append("1")
	while n:
		n-=1
		a = q[0]
		q.pop(0)
		print(a, end = " " )
		temp = a
		q.append(a + "0")
		q.append(temp + "1")

for _ in range(int(input())):
	n = int(input())
	binary(n)
	print()


[forminator_quiz id="1836"]

So, in this blog, we have tried to explain the concept of queue data sructure. If you want to solve more questions on Queues, which are curated by our expert mentors at PrepBytes, you can follow this link Queues.

Leave a Reply

Your email address will not be published. Required fields are marked *