Repository navigation
Expand file tree
/
Copy pathSimpleStack.java
More file actions
174 lines (154 loc) · 5.02 KB
/
Copy pathSimpleStack.java
File metadata and controls
174 lines (154 loc) · 5.02 KB
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/*
* Implementation of simple stack using an array to store the data.
* Author - Aakash "Ash" Jain.
* Contact - [email protected].
*/
package Stacks;
public class SimpleStack implements Stack {
// This array stores the data. Data can be anything strings, integers, floats and so on
// Custom objects using private classes can be also be created to suit organizational needs.
private Object[] data;
// Length of the stack. (Total number of nodes on the stack)
private int len;
// Size of the array.
private static int size;
static {
// Can be set differently according to the needs.
size = 25;
}
// Constructor.
public SimpleStack() {
// Initialize the array.
this.data = new Object[size];
this.len = 0;
}
// Add object to the top of the stack. O(1) / O(n) if array is overflown.
public int push(Object obj) {
try {
// Initialize if not done already.
if (this.data == null) {
data = new Object[size];
this.len = 0;
}
// If data being pushed exceeds the current size of the array.
else if (this.len == size)
this.extend();
// Set the data at last place in the array and increment the length.
this.data[this.len++] = obj;
return 0;
} catch (Exception e) {
return 1;
}
}
// Increase the size of the stack dynamically. O(n)
private int extend() {
try {
// Double the size, make a copy of the data.
size *= 2;
Object[] olddata = this.data;
// Create new array with twice the size.
this.data = new Object[size];
// Set all the values in copy to current array indices respectively.
for (int i = 0; i < this.len; i++)
this.data[i] = olddata[i];
return 0;
} catch (Exception e) {
return 1;
}
}
// Return topmost node on the stack. O(1)
public Object peek() {
try {
if (this.isEmpty())
return null;
return this.data[this.len-1];
} catch (Exception e) {
return -1;
}
}
// Remove and return topmost node on the stack. O(n)
public Object pop() {
try {
if (this.isEmpty())
return null;
// Copy the data, remove it from the array and then return the value(s).
Object obj = this.data[this.len-1];
remove(this.len-1);
return obj;
} catch (Exception e) {
return -1;
}
}
// Remove node at specified index. Does NOT support negative or overflowing indexes. O(n)
public int remove(int index) {
try {
// Check for invalid index.
if (index < 0 || index >= this.len)
return 1;
// Shift over the next nodes in the array.
for (int i = index; i < this.len; i++)
this.data[i] = this.data[i+1];
this.len--;
return 0;
} catch (Exception e) {
return -1;
}
}
// Delete the stack. O(1)
public int clear() {
try {
// Set data to null and restore all variables to initial states.
this.data = null;
this.len = 0;
SimpleStack.size = 25;
return 0;
} catch (Exception e) {
return 1;
}
}
// Return true if the stack is empty, false otherwise.
public boolean isEmpty() {
return this.data == null && this.len == 0;
}
// Return the length of the stack. O(1)
public int getLength() {
return this.len;
}
// Stringify the stack data. O(n)
@Override
public String toString() {
try {
if (this.isEmpty())
return "\n-------\n| |\n-------\n";
// TODO Add dashes dynamically based on the longest element on the stack.
String result = "\n-------\n";
for (int i = 0; i < this.len; i++) {
// Add quotes if the object is a string.
if (this.data[i] instanceof String)
result += "| \"" + this.data[i] + "\" |\n";
else
result += "| " + this.data[i] + " |\n";
}
// Remove 2 unnecessary characters from the last node.
return result + "-------\n";
} catch (Exception e) {
return null;
}
}
// Print the stack data.
@Deprecated
public int printStack() {
if (this.isEmpty()) {
System.out.print("\nSTACK IS EMPTY.\n");
return -1;
}
System.out.println("\nCURRENT STACK IS: \n-------");
for (int i = 0; i < this.len; i++)
System.out.println("| " + this.data[i] + " |");
System.out.println("-------\n");
return 0;
}
// Tests.
public static void main(String[] args) {
}
}