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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
// 225. Implement Stack using Queues
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/*
* implement a last in, first out (LIFO) stack using only two queues. the
* implemented stack should support all the functions of a normal stack ('push',
* 'top', 'pop', and 'empty'). implement the 'stack' class
* - void push(int x) pushes element 'x' to the top of the stack
* - int pop() removes the element on the top of the stack and returns it
* - int top() returns the element on the top of the stack
* - bool empty() returns 'true' if the stack is empty, 'false' otherwise
* notes:
* - you must use only standard operations of a queue, which means that only
* push to back, peek/pop from front, size, and is empty are valid operations.
* - depending on your language, the queue may not be supported natively. you
* may simulate a queue using a list of dequeu (double ended queue) as long as
* you only use a queue's standard operations.
*/
typedef struct {
int *q;
int size;
int front;
int rear;
} queue;
typedef struct {
queue *q1;
queue *q2;
} stack;
int queue_empty(queue *q) {
if (q->front == -1 && q->rear == -1) {
printf("\nqueue is EMPTY\n");
return 1;
}
return 0;
}
int queue_full(queue *q) {
if (q->rear == q->size - 1)
return 1;
return 0;
}
int queue_top(queue *q) {
if (queue_empty(q))
return -1;
return q->q[q->front];
}
int queue_pop(queue *q) {
if (queue_empty(q))
return -1;
int data = q->q[q->front];
if (q->front == q->rear)
q->front = q->rear = -1;
else
q->front++;
return data;
}
void queue_push(queue *q, int val) {
if (queue_full(q)) {
printf("\nqueue is FULL\n");
return;
}
if (queue_empty(q)) {
q->front++;
q->rear++;
} else {
q->rear++;
}
q->q[q->rear] = val;
}
queue *queue_create(int max_size) {
queue *q = (queue *)malloc(sizeof(queue));
q->front = q->rear = -1;
q->size = max_size;
q->q = (int *)malloc(sizeof(int) * max_size);
return q;
}
void stackCreate(stack *stk, int max_size) {
stack **s = (stack **)stk;
*s = (stack *)malloc(sizeof(stack));
(*s)->q1 = queue_create(max_size);
(*s)->q2 = queue_create(max_size);
}
void stackPush(stack *obj, int x) {
stack **s = (stack **)obj;
queue_push((*s)->q2, x);
while (!queue_empty((*s)->q1)) {
int data = queue_pop((*s)->q1);
queue_push((*s)->q2, data);
}
queue *tmp = (*s)->q1;
(*s)->q1 = (*s)->q2;
(*s)->q2 = tmp;
}
int stackPop(stack *obj) {
stack **s = (stack **)obj;
return queue_pop((*s)->q1);
}
int stackTop(stack *obj) {
stack **s = (stack **)obj;
if (!queue_empty((*s)->q1))
return queue_top((*s)->q1);
return -1;
}
bool stackEmpty(stack *obj) {
stack **s = (stack **)obj;
if (queue_empty((*s)->q1))
return true;
return false;
}
void stackFree(stack *obj) {
stack **s = (stack **)obj;
free((*s)->q1);
free((*s)->q2);
free((*s));
}
int main() {
stack *obj = stackCreate();
stackPush(obj, 1);
stackPush(obj, 2);
printf("%d\n", stackTop(obj)); // expect: 2
printf("%d\n", stackPop(obj)); // expect: 2
printf("%d\n", stackEmpty(obj)); // expect: 0
}
|