One of the popular interview question asked on queue data structure:
Write a program to print the numbers from 1 to N in Binary Representation using QUEUE data structure.
Example:
Input: N = 3
Output: 1, 10, 11
Input: N= 5
Output: 1, 10, 11, 100, 101
Code will follow the following Logic:
- Initialize queue with 1
- Repeat this step until required ‘n’ is reached
- Dequeue front and print
- Suffix front element with ‘0’ once and ‘1’ another and enqueue both into queue in the same order
One possible C Implementation Solution:
#include <stdio.h> #include <string.h> struct queue { char items[50][20]; int front; int rear; }; typedef struct queue QUEUE; void enqueue(QUEUE *q, char x[]) { q->rear++; strcpy(q->items[q->rear], x); } void dequeue(QUEUE *q, char *x) { strcpy(x, q->items[q->front]); q->front++; } void print_binary(int n) { QUEUE q; q.front = 0; q.rear = -1; char x[20], tx[20]; int i = 1; enqueue(&q, "1"); while(i <= n) { dequeue(&q, x); // Copy the value to temp so that we dont lose it // for second time append strcpy(tx, x); // Print the dequeued item printf("%s\t", x); // Append a 0 and enqueue enqueue(&q, (strcat(x, "0"))); // Copy back the original string strcpy(x, tx); // Append a 1 and enqueue enqueue(&q, (strcat(x, "1"))); i++; } } int main() { int n; printf("Enter the value of n"); scanf("%d", &n); print_binary(n); return 0; }
Reblogged this on PH Bytes.
LikeLike