-
Notifications
You must be signed in to change notification settings - Fork 0
/
StackUtil.java
154 lines (125 loc) · 3.69 KB
/
StackUtil.java
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
package com.aman.data_structures;
import java.util.EmptyStackException;
public class StackUtil {
private ListNode top;
private int length;
private class ListNode{
private int data;
private ListNode next;
public ListNode(int data){
this.data = data;
}
}
public StackUtil(){
top = null;
length = 0;
}
public int length(){
return length;
}
public boolean isEmpty(){
return length == 0;
}
public static void main(String[] args) {
// Stack stack = new Stack();
// stack.push(10);
// stack.push(20);
// stack.push(30);
//
// System.out.println(stack.peek());
// stack.pop();
// System.out.println(stack.peek());
// stack.pop();
// System.out.println(stack.peek());
// calling reverse method & printing the result
// String str = "ABCD";
// System.out.println("Before reverse : " + str);
// System.out.println("After reverse : " + reverse(str));
// calling nextGreaterElement method & displaying the result
// int[] arr = {1, 7, 8, 3, 2, 4, 10};
// int[] temp = nextGreaterElement(arr);
// System.out.println(Arrays.toString(temp));
// calling isValid & printing the result
System.out.println(isValid("({[]})"));
}
// pushes an element
public void push(int data){
ListNode temp = new ListNode(data);
temp.next = top;
top = temp;
length++;
}
// removes the top element
public int pop(){
if(isEmpty()){
throw new EmptyStackException();
}
int result = top.data;
top = top.next;
length--;
return result;
}
// displays the recent added element
public int peek(){
if(isEmpty()){
throw new EmptyStackException();
}
return top.data;
}
// reverse a string
public static String reverse(String str){
StackUtil stack = new StackUtil();
char[] chars = str.toCharArray();
for(char c : chars){
stack.push(c);
}
for(int i = 0; i < str.length(); i++){
chars[i] = (char) stack.pop();
}
return new String(chars);
}
// find next greater element in the array and store it in the new array
public static int[] nextGreaterElement(int[] arr){
int[] result = new int[arr.length];
StackUtil stack = new StackUtil();
for(int i = arr.length - 1; i >= 0; i--){
if(!stack.isEmpty()){
while(!stack.isEmpty() && stack.peek() <= arr[i]){
stack.pop();
}
}
if(stack.isEmpty()){
result[i] = -1;
}
else{
result[i] = stack.peek();
}
stack.push(arr[i]);
}
return result;
}
// valid parentheses problem (Balanced Brackets)
public static boolean isValid(String s){
StackUtil stack = new StackUtil();
for(char c : s.toCharArray()){
if(c == '(' || c == '{' || c == '['){
stack.push(c);
}
else{
if(stack.isEmpty()){
return false;
}
else{
char top = (char) stack.peek();
if((c == ')' && top == '(') || (c == '}' && top == '{') || (c == ']' && top == '[')){
stack.pop();
}
else{
return false;
}
}
}
}
return stack.isEmpty();
}
}