blob: 7aa02ae980e6118f59b14f39d36297e8da33952e (
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
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
|
#include "min_stack.h"
#include <stdio.h>
#include <stdlib.h>
/**
* The equivalent of a constructor for initialzing
* a new Node in a linked list.
*
* @param data The data to bind to the node
* @param next The next node to point to. NULL for a new head.
* @return The new linked list Node.
*/
static Node *new (int data, Node *next) {
Node *node = malloc(sizeof(Node));
node->next = next;
node->data = data;
return node;
}
/**
* The equivalent of a constructor for initialzing
* a new min Stack.
*
* @return The new Stack
*/
Stack *initialize(void) {
Stack *self = malloc(sizeof(Stack));
self->head = NULL;
self->min = NULL;
self->size = 0;
return self;
}
/**
* Returns the number of items on the stack.
*
* @param self The stack to investigate.
*/
int size(Stack *self) { return self->size; }
/**
* Pushes a new item on to a Stack
*
* @param self The stack to push the data on to
* @param data The data to push on to the Stack
*/
void push(Stack *self, int data) {
if (!self->min || (data < self->min->data))
self->min = new (data, self->min);
self->head = new (data, self->head);
self->size++;
}
/**
* Iterates through each item in a linked list.
*
* @param head The head of the linked list
* @block The callback function to invoke on each item in the list.
*/
void each(Node *head, Visitor block) {
Node *tmp = head;
while (tmp) {
(*block)(tmp);
tmp = tmp->next;
}
}
/**
* Returns the minimum value in the Stack.
*
* @param self The stack to investigate
*/
int min(Stack *self) {
if (self->min)
return self->min->data;
if (self->head) {
int min = self->head->data;
Node *tmp = self->head->next;
while (tmp) {
if (tmp->data < min)
min = tmp->data;
tmp = tmp->next;
}
return min;
}
return (int)NULL;
}
/**
* Pops off the item from the top of the Stack.
*
* @param self The stack to pop an item off of.
*/
int pop(Stack *self) {
if (!self->head)
return (int)NULL;
Node *current = self->head;
int data = current->data;
if (data == self->min->data)
self->min = self->min->next;
self->head = current->next;
self->size--;
current->next = NULL;
free(current);
return data;
}
/**
* Prints a visual representation a Node in the linked list.
*
* @param node The node to print.
*/
void print_node(Node *node) { printf("[%d]", node->data); }
/**
* A helper function to print out a visual representation of a Stack.
*
* @param stack the Stack to print out.
*/
void inspect(Stack *stack) {
printf("\t");
each(stack->head, &print_node);
printf("\n");
}
|
