C Program to Implement Queue using Two Stacks

This is a C program to implement queue using two stacks.
Enqueue operation:
1. Simply push the elements into the first stack.
Dequeue operation:
1. Pop from the second stack if the second stack is not empty.
2. If second stack is empty, pop from the first stack and push all the elements into second until the first stack becomes empty.
3. Now pop an element from the second stack.

Here is the source code of the C Program. The C program is successfully compiled and run on a Windows system. The program output is also shown below.

/* C program to implement queues using two stacks */

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
struct node
```
```
{
```
```
    int data;
```
```
    struct node *next;
```
```
};
```
```
void push(struct node** top, int data);
```
```
int pop(struct node** top);
```
```
struct queue
```
```
{
```
```
    struct node *stack1;
```
```
    struct node *stack2;
```
```
};
```
```
void enqueue(struct queue *q, int x)
```
```
{
```
```
    push(&q->stack1, x);
```
```
}
```
```
void dequeue(struct queue *q)
```
```
{
```
```
    int x;
```

    if (q->stack1 == NULL && q->stack2 == NULL) {

```
        printf("queue is empty");
```
```
        return;
```
```
    }
```
```
    if (q->stack2 == NULL) {
```
```
        while (q->stack1 != NULL) {
```
```
        x = pop(&q->stack1);
```
```
        push(&q->stack2, x);
```
```
        }
```
```
    }
```
```
    x = pop(&q->stack2);
```
```
    printf("%d\n", x);
```
```
}
```
```
void push(struct node** top, int data)
```
```
{
```

    struct node* newnode = (struct node*) malloc(sizeof(struct node));

```
        if (newnode == NULL) {
```

            printf("Stack overflow \n");

```
            return;
```
```
        }
```
```
    newnode->data = data;
```
```
    newnode->next = (*top);
```
```
    (*top) = newnode;
```
```
}
```
```
int pop(struct node** top)
```
```
{
```
```
    int buff;
```
```
    struct node *t;
```
```
    if (*top == NULL) {
```
```
        printf("Stack underflow \n");
```
```
        return;
```
```
    }
```
```
    else {
```
```
        t = *top;
```
```
        buff = t->data;
```
```
        *top = t->next;
```
```
        free(t);
```
```
        return buff;
```
```
    }
```
```
}
```

void display(struct node *top1,struct node *top2)

```
{
```
```
    while (top1 != NULL) {
```
```
        printf("%d\n", top1->data);
```
```
        top1 = top1->next;
```
```
    }
```
```
    while (top2 != NULL) {
```
```
        printf("%d\n", top2->data);
```
```
        top2 = top2->next;
```
```
    }
```
```
}
```
```
int main()
```
```
{
```

    struct queue *q = (struct queue*)malloc(sizeof(struct queue));

```
    int f = 0, a;
```
```
    char ch = 'y';
```
```
    q->stack1 = NULL;
```
```
    q->stack2 = NULL;
```
```
    while (ch == 'y'||ch == 'Y') {
```

        printf("enter ur choice\n1.add to queue\n2.remove

               from queue\n3.display\n4.exit\n");

```
        scanf("%d", &f);
```
```
        switch(f) {
```

            case 1 : printf("enter the element to be added to queue\n");

```
                     scanf("%d", &a);
```
```
                     enqueue(q, a);
```
```
                     break;
```
```
            case 2 : dequeue(q);
```
```
                     break;
```

            case 3 : display(q->stack1, q->stack2);

```
                     break;
```
```
            case 4 : exit(1);
```
```
                     break;
```

            default : printf("invalid\n");

```
                      break;
```
```
        }
```
```
    }
```
```
}
```

Output

Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
34
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
55
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
99
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
1
Enter the element to be added to queue
77
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
3
34
55
99
77
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
2
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
3
55
99
77
Enter your choice
1. Add an element to the queue
2. Remove an element from queue
3. Display the elements in queue
4. Exit
4

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Binary Heap

» Next - C Program to Implement Stack

Related Posts:

Practice Programming MCQs
Check Programming Books
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books

Recommended Articles: