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).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
/* 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:
