C Program for Reverse a Queue

November 2, 2023

How to Reverse a Queue in C programming language?

In this we will learn how to write a C Program for Reverse a Queue. In below sections, we will learn steps and code to perform the task.
For example :- Input : 10 12 3 14
Output : 14 3 12 10 (after reverse the queue)

Reverse a Queue in C

Method 1 : Reverse A Queue Using Stack

Create a queue and a stack data structure. We’ll use the queue to store the input elements, and the stack to temporarily hold the elements while we reverse the queue.
Enqueue all the elements of the original queue into the stack until the queue is empty.
Dequeue all the elements from the stack and enqueue them back into the original queue.
Repeat steps 2 and 3 until the stack is empty.
The original queue will now be reversed.

Method 2 : Reverse A Queue Using Recursion

Pop the front element from the queue and store it in a variable.
Recursively reverse the remaining elements of the queue.
Enqueue the front element that was popped in step 1 to the back of the reversed queue.
Repeat steps 1 to 3 until all elements have been dequeued and enqueued.
The original queue will now be reversed.

Queues In Data Structures

Queues using Linked Lists

Implement Queue using Stack

Implement Queue using two Stacks

Circular queue in C

C Program for Reversing a Queue:-

Method 1 : Reversing a queue using Stack

Method 2 : Reversing a queue using recursion

Method 1 : Reversing a queue using Stack

Run

#include<stdio.h> 
#include<stdlib.h> 

#define MAX_SIZE 100

struct Queue
{
  int items[MAX_SIZE];
  int front;
  int rear;
};

struct Stack
{
  int items[MAX_SIZE];
  int top;
};

void enqueue (struct Queue *q, int item)
{
  if (q->rear == MAX_SIZE - 1)
    {
      printf ("Queue overflow\n");
      return;
    }

  if (q->front == -1)
    {
      q->front = 0;
    }

  q->rear++;
  q->items[q->rear] = item;
}

int dequeue (struct Queue *q)
{
  if (q->front == -1)
    {
      printf ("Queue underflow\n");
      return -1;
    }

  int item = q->items[q->front];
  q->front++;

  if (q->front > q->rear)
    {
      q->front = q->rear = -1;
    }

  return item;
}

void display (struct Queue *q)
{
  if (q->rear == -1)
    {
      printf ("Queue is empty\n");
      return;
    }

  for (int i = q->front; i <= q->rear; i++)
    {
      printf ("%d ", q->items[i]);
    }
  printf ("\n");
}

void push (struct Stack *s, int item)
{
  if (s->top == MAX_SIZE - 1)
    {
      printf ("Stack overflow\n");
      return;
    }

  s->top++;
  s->items[s->top] = item;
}

int pop (struct Stack *s)
{
  if (s->top == -1)
    {
      printf ("Stack underflow\n");
      return -1;
    }

  int item = s->items[s->top];
  s->top--;

  return item;
}

int main ()
{
  struct Queue q;
  q.front = -1;
  q.rear = -1;

  struct Stack s;
  s.top = -1;

  enqueue (&q, 1);
  enqueue (&q, 2);
  enqueue (&q, 3);
  enqueue (&q, 4);

  printf ("Queue before reversing:\n");
  display (&q);

  while (q.front != -1)
    {
      push (&s, dequeue (&q));
    }

  while (s.top != -1)
    {
      enqueue (&q, pop (&s));
    }

  printf ("Queue after reversing:\n");
  display (&q);

  return 0;
}

Output

Queue before reversing:
1 2 3 4 
Queue after reversing:
4 3 2 1

In this code, we define two data structures: Queue and Stack. The Queue is implemented using an array and has two pointers – front and rear. The Stack is also implemented using an array and has one pointer – top.
The enqueue() and dequeue() functions are used to insert and remove items from the queue, respectively. The display() function is used to display the contents of the queue.
The push() and pop() functions are used to insert and remove items from the stack, respectively.
To reverse the queue using a stack, we first dequeue all the items from the queue and push them onto the stack. Then, we pop all the items from the stack and enqueue them back into the queue. This effectively reverses the order of the items in the queue.

Method 2 : Reversing a queue using recursion

Run

#include <stdio.h>
#include<stdlib.h> 

#define MAX_SIZE 100

struct Queue
{
  int items[MAX_SIZE];
  int front;
  int rear;
};

void enqueue (struct Queue *q, int item)
{
  if (q->rear == MAX_SIZE - 1)
    {
      printf ("Queue overflow\n");
      return;
    }

  if (q->front == -1)
    {
      q->front = 0;
    }

  q->rear++;
  q->items[q->rear] = item;
}

int dequeue (struct Queue *q)
{
  if (q->front == -1)
    {
      printf ("Queue underflow\n");
      return -1;
    }

  int item = q->items[q->front];
  q->front++;

  if (q->front > q->rear)
    {
      q->front = -1;
      q->rear = -1;
    }

  return item;
}

void display (struct Queue *q)
{
  if (q->rear == -1)
    {
      printf ("Queue is empty\n");
      return;
    }

  for (int i = q->front; i <= q->rear; i++)
    {
      printf ("%d ", q->items[i]);
    }

  printf ("\n");
}

void reverse (struct Queue *q)
{
  if (q->front == -1)
    {
      return;
    }

  int item = dequeue (q);

  reverse (q);

  enqueue (q, item);
}

int main ()
{
  struct Queue q;
  q.front = -1;
  q.rear = -1;

  enqueue (&q, 1);
  enqueue (&q, 2);
  enqueue (&q, 3);
  enqueue (&q, 4);

  printf ("Queue before reversing:\n");
  display (&q);

  reverse (&q);

  printf ("Queue after reversing:\n");
  display (&q);

  return 0;
}

Output

Queue before reversing:
1 2 3 4 
Queue after reversing:
4 3 2 1

In this code, we define a Queue data structure, which is implemented using an array and has two pointers – front and rear. The enqueue(), dequeue(), and display() functions are used to insert, remove, and display items from the queue, respectively.
To reverse the queue using recursion, we define a reverse() function that takes a pointer to the queue as its argument. The reverse() function works as follows:
- If the queue is empty, return.
- Dequeue the first item from the queue.
- Recursively call reverse() on the remaining items in the queue.
- Enqueue the first item at the rear of the queue.
By recursively calling reverse() on the remaining items in the queue, we effectively reverse the order of the items in the queue. Finally, we enqueue the first item at the rear of the queue to complete the reversal process.
Note that this code assumes that the maximum size of the queue is defined as MAX_SIZE. You may need to adjust this value depending on your needs

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

Introduction to Stack in Data Structure
Operations on a Stack
Stack: Infix, Prefix and Postfix conversions
Stack Representation in – C | C++ | Java
Representation of a Stack as an Array. – C | C++ | Java
Representation of a Stack as a Linked List. – C | C++ | Java
Infix to Postfix Conversion – C | C++ | Java
Infix to prefix conversion in – C | C++ | Java
Postfix to Prefix Conversion in – C | C++ | Java

Queues

Queues in Data Structures (Introduction)
Queues Program in C and implementation
Implementation of Queues using Arrays | C Program
Types of Queues in Data Structure
Application of Queue Data Structure
Insertion in Queues Program (Enqueuing) – C | C++ | Java
Deletion (Removal) in Queues Program(Dequeuing) – C | C++ | Java
Reverse a Queue – C | C++ | Java
Queues using Linked Lists – C | C++ | Java
Implement Queue using Stack – C | C++ | Java
Implement Queue using two Stacks – C | C++ | Java

Circular Queues

Circular queue in Data Structure
Applications of Circular Queues
Circular queue in – C | C++ | Java
Circular queue using Array – C | C++ | Java
Circular Queue using Linked Lists – C | C++ | Java

Priority Queue

Application of Priority Queue
Priority Queue Example
Priority Queue Introduction – C | C++ | Java
Priority Queue Implementation using Array – C | C++ | Java
Priority Queue using Linked List – C | C++ | Java
Priority Queue Insertion and Deletion- C | C++ | Java

Stacks

Introduction to Stack in Data Structure
Click Here
Operations on a Stack
Click Here
Stack: Infix, Prefix and Postfix conversions
Click Here
Stack Representation in –
C | C++ | Java
Representation of a Stack as an Array. –
C | C++ | Java
Representation of a Stack as a Linked List. –
C | C++ | Java
Infix to Postfix Conversion –
C | C++ | Java
Infix to prefix conversion in –
C | C++ | Java
Postfix to Prefix Conversion in –
C | C++ | Java

Queues

Queues in Data Structures (Introduction)
Click Here
Queues Program in C and implementation
Click Here
Implementation of Queues using Arrays | C Program
Click Here
Types of Queues in Data Structure
Click Here
Application of Queue Data Structure
Click Here
Insertion in Queues Program (Enqueuing) –
C | C++ | Java
Deletion (Removal) in Queues Program(Dequeuing) –
C | C++ | Java
Reverse a Queue –
C | C++ | Java
Queues using Linked Lists –
C | C++ | Java
Implement Queue using Stack –
C | C++ | Java
Implement Queue using two Stacks –
C | C++ | Java

Circular Queues

Circular queue in Data Structure
Click Here
Applications of Circular Queues
Click Here
Circular queue in –
C | C++ | Java
Circular queue using Array –
C | C++ | Java
Circular Queue using Linked Lists –
C | C++ | Java

Priority Queue

Application of Priority Queue
Priority Queue Example
Priority Queue Introduction –
C | C++ | Java
Priority Queue Implementation using Array –
C | C++ | Java
Priority Queue using Linked List –
C | C++ | Java
Priority Queue Insertion and Deletion-
C | C++ | Java