Program to Implement Queue using two Stacks in Data Structures (C plus plus)

Program to Implement Queue using two Stacks in Data Structures (C plus plus)

In this tutorial, we will learn about Program to Implement Queue using two Stacks in Data Structures (C plus plus).

```/* Program to implement a queue using two stacks*/

#include<iostream>
#include<stdlib.h>

using namespace std;

struct sNode
{
int info;
struct sNode *next;
};

void insert(struct  sNode** top_ref, int new_data);

int delet(struct sNode** top_ref);

struct queue
{
struct sNode *stack1;
struct sNode *stack2;
};

void enqueue(struct queue *q, int x)
{
insert(&q->stack1, x);
}

int dequeue(struct queue *q)
{
int x;

if (q->stack1 == NULL && q->stack2 == NULL)
{
cout << "Empty Queue"<<endl;
exit(0);
}

if (q->stack2 == NULL)
{
while (q->stack1 != NULL)
{
x = delet(&q->stack1);
insert(&q->stack2, x);
}
}

x = delet(&q->stack2);
return x;
}

void insert(struct sNode** top_ref, int new_data)
{

struct sNode* new_node = (struct sNode*) malloc(sizeof(struct sNode));

if (new_node == NULL)
{
cout << "Stack overflowed \n";
exit(0);
}

new_node->info = new_data;

new_node->next = (*top_ref);

(*top_ref) = new_node;
}

int delet(struct sNode** top_ref)
{
int res;
struct sNode *top;

if (*top_ref == NULL)
{
cout << "Stack overflowed \n";
exit(0);
}

else
{
top = *top_ref;
res = top->info;
*top_ref = top->next;
free(top);
return res;
}
}

int main()
{

struct queue *q = (struct queue*) malloc(sizeof(struct  queue));
q->stack1 = NULL;
q->stack2 = NULL;
cout << "Enqueuing----"<<endl;

enqueue(q, 1);
cout << "Enqueuing----"<<endl;
enqueue(q, 2);
cout << "Enqueuing----"<<endl;
enqueue(q, 3);

cout << "Dequeuing----";
cout << dequeue(q) << " "<<endl;;
cout << "Dequeuing----";
cout << dequeue(q) << " "<<endl;
cout << "Dequeuing----";
cout << dequeue(q) << " "<<endl;;
}```

Output: