Question

Write an (efficient) pseudocode for the implementation of each of the following function prototypes (proper C code will also be accepted)

- void print(Q) – prints the entire queue Q from front to back.

- int enqueue(Q,x) – enqueues the element x into queue Q (if unsuccessful, return -1)

- int* dequeue(Q) – dequeues the next integer from front of the queue (if unsuccessful, return null)

- int isEmpty(Q) – returns 1 (true) or 0 (false) depending on emptiness of the queue Q

- unsigned int size(Q) – returns the number of items currently in the queue

In your final solution, you may add any extra attributes that you feel is needed for this question but you must use as few extra attributes as possible and your algorithm must be as efficient as possible (in terms of big-O analysis).

Answer 1

Dear Learner,

I'm providing you the pseudocode of the functions asked

We will be implementing queue using array data structure.

There will be attributes of the queue viz., front, rear and capacity, indicating the front element,last element and the maxmum capacity of the queue, respectively.

1. void print(Q) //time complexity = O(N)

if (front = = rear) //to check if the queue is empty

print("EMPTY QUEUE")

return

else //when the queue is not empty

for i = front to i <= rear

print(Q[i])

2. int enqueue(Q,x) //time complexity = O(1)

if (capacity == rear) //if the queue is full

printf("Queue is full")

           return (-1)

else

queue[rear] = data

           rear = rear + 1

3. int* dequeue(Q) //time complexity = O(1)

if (front == rear) //if queue is empty

printf("Queue is empty")

return null

else

for i=0 to i<rear

queue[i] = queue[i+1]

rear = rear-1

4. int isEmpty(Q) //time complexity = O(1)

if (front = = rear) //when the queue IS empty

return (1)

else // when the queue IS NOT empty

return (0)

5. NOTE : There are basically 2 ways in which you can count the number of elements in queue.

1. Where you have a rear pointer pointing towards the last element in the queue. In this case returning the value of rear will give us the number of elements in the queue.

2. Traversing the entire queue and counting the elements. This method is much less efficient as we have to go through the entire queue each time we want to count the number of elements in it.

However, we'll discuss both the methods here,

METHOD 1. time complexity = O(1)

unsigned int size(Q)

return rear

METHOD 2. time complexity = O(N)

unsigned int size(Q)

int count = 0

for i = front to i<=rear

count = count + 1

return rear

I hope I have explained the question the way you were expecting. In case if you still have any doubts or further queries, feel free to ask us in the comment section.

Please leave a like if this was helpful.

Thanks,

Happy Studying.