blob: beffd64d5e2bf82ed6ab9e9def8ab64768b46340 (
plain)
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
|
#include "stack.h"
#include <stdio.h>
#include <stdlib.h>
static Queue *newQueue(){
Queue *queue = malloc(sizeof(Queue));
queue->size = 0;
queue->head = NULL;
return queue;
}
Stack *initialize() {
Stack *stack = malloc(sizeof(Stack));
stack->q1 = newQueue();
return stack;
}
Node *newNode(int data) {
Node *node = malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
void enqueue(Queue *q, int data) {
Node *node = newNode(data);
q->size++;
if (q->head == NULL) {
q->head = node;
} else {
Node *tail = q->head;
while (tail->next != NULL)
tail = tail->next;
tail->next = node;
}
}
int dequeue(Queue *q) {
if (q->head == NULL) return -1;
Node *node = q->head;
int data = node->data;
q->head = node->next;
free(node);
return data;
}
// The running time is linear time.
void push(Stack *stack, int data) {
enqueue(stack->q1, data);
}
// The running time is linear time.
int pop(Stack *stack) {
int count = stack->q1->size - 1;
Queue *tmp = newQueue();
for (int i = 0; i < count; i++)
enqueue(tmp, dequeue(stack->q1));
int data = dequeue(stack->q1);
free(stack->q1);
stack->q1 = tmp;
return data;
}
int size(Stack *stack) {
return stack->q1->size;
}
void destroy(Stack *stack) {
int count = size(stack);
for (int i = 0; i < count; i++)
pop(stack);
free(stack->q1);
free(stack);
}
static void inspect(Queue *q) {
Node *tmp = q->head;
if (q->size == 0) {
printf("[]\n");
return;
}
printf("[");
for (int i = 0; i < q->size; i++) {
printf("%d,", tmp->data);
tmp = tmp->next;
}
printf("\b]\n");
}
|
