-
Notifications
You must be signed in to change notification settings - Fork 0
/
stack.hpp
154 lines (139 loc) · 3.19 KB
/
stack.hpp
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#pragma once
namespace strukdat {
namespace stack {
/**
* @brief Node linked list berisi nilai bertipe `T` yang disimpan pada `data`
*/
template <typename T>
struct Node {
T data;
Node *next;
};
/**
* @brief Tipe pointer dari node
*/
template <typename T>
using pointer = Node<T>*;
template <typename T>
using Stack = pointer<T>;
template <typename T>
Stack<T> Top;
/**
* @brief Membuat dan menginisialisasi stack baru
* @param Top pointer ke puncak stack
*
* @return pointer ke puncak stack
*/
template <typename T>
Stack<T> createStack(Stack<T> Top) {
Top = nullptr;
return Top;
}
/**
* @brief Membuat dan menginisialisasi element baru untuk dimasukan ke stack
* @param newElement pointer ke element baru
* @param data data yang akan dimasukan
*/
template <typename T>
void createElement(pointer<T>& newElement, T data) {
newElement = new Node<T>;
newElement->data = data;
newElement->next = nullptr;
}
/**
* @brief Mengambil data pada element yang berada di puncak stack
* @param Top pointer ke puncak stack
*
* @return data pada element puncak stack
*/
template <typename T>
T peek(Stack<T> Top) {
return Top->data;
}
/**
* @brief Mengecek apakah suatu stack kosong atau sudah mempunyai element
* @param Top pointer ke puncak stack
*
* @return 'true' jika stack kosong dan 'false' jika stack tidak kosong
*/
template <typename T>
bool isEmpty(Stack<T> Top) {
if (Top == nullptr){
return true;
}
else{
return false;
}
}
/**
* @brief Memasukan element ke puncak stack (push / insert first)
* @param Top pointer ke puncak stack
* @param newElement pointer ke element baru
*
* @return pointer ke puncak stack
*/
template <typename T>
Stack<T> push(Stack<T> Top, pointer<T> newElement) {
if (Top == nullptr){
Top = newElement;
}
else{
newElement->next = Top;
Top = newElement;
}
return Top;
}
/**
* @brief Mengeluarkan element dari puncak stack (pop / delete first)
* @param Top pointer ke puncak stack
* @param delElement pointer ke element yang dihapus
*
* @return pointer ke element yang dihapus
*/
template <typename T>
Stack<T> pop(Stack<T>& Top, pointer<T> delElement) {
if (Top == nullptr){
delElement = nullptr;
Top = nullptr;
}
else{
delElement = Top;
Top = Top->next;
delElement->next = nullptr;
}
return delElement;
}
/**
* @brief Mengambil element terdalam / element dasar / element terakhir pada stack
* @note Gunakan algoritma traversal sebagai referensi
* @param Top pointer ke puncak stack
*
* @return pointer ke element terdalam
*/
template <typename T>
Stack<T> lastNode(Stack<T> Top) {
pointer<T> ptrResult = nullptr;
if (Top == nullptr){
ptrResult = nullptr;
}
else{
pointer<T> pHelp = Top;
if (pHelp->next == nullptr){
Top = nullptr;
ptrResult = pHelp;
}
else{
pHelp = Top->next;
pointer<T> temp = Top;
while (pHelp->next != nullptr){
pHelp = pHelp->next;
temp = temp->next;
}
temp->next = nullptr;
ptrResult = pHelp;
}
}
return ptrResult;
}
} // namespace stack
} // namespace strukdat