스택은 두 가지 작업(푸시 및 팝)만 허용되는 요소 모음을 나타내는 선형 데이터 구조입니다. 푸시 작업은 스택 맨 위에 요소를 추가하고 팝 작업은 스택 맨 위에서 요소를 제거합니다. 스택은 LIFO(Last In First Out) 원칙을 따릅니다. 즉, 스택에 마지막으로 추가된 요소가 가장 먼저 제거됩니다.
스택의 일상 생활 예 중 하나는 부엌에 있는 접시 스택입니다. 우리는 접시를 씻을 때 공간을 절약하기 위해 종종 접시를 겹쳐 쌓습니다. 우리가 씻는 첫 번째 접시는 더미의 맨 아래에 있고 마지막으로 씻은 접시는 더미의 맨 위에 있습니다. 접시를 사용하고 싶을 때는 스택 맨 위에서 가져옵니다. 이것은 스택의 LIFO 원리를 따르며 스택에 추가된 마지막 플레이트(즉, 맨 위에 있는 플레이트)가 첫 번째로 사용됩니다.
마찬가지로 스택에 새 플레이트를 추가할 때 기존 스택 위에 배치합니다. 이는 스택의 맨 위에 새 요소가 추가되는 스택의 푸시 작업과 유사합니다. 스택에서 플레이트를 제거할 때 맨 위에서 가져오면 스택이 작아집니다. 이는 스택의 맨 위 요소가 스택에서 제거되는 팝 작업과 유사합니다.
전반적으로 주방의 접시 더미는 일상 생활에서 스택 데이터 구조의 단순하고 직관적인 예입니다.
다음은 Java에서 스택 데이터 구조를 사용하는 방법에 대한 두 가지 예입니다.
public class Stack {
private int[] arr;
private int top;
private int size;
public Stack(int size) {
arr = new int[size];
top = -1;
this.size = size;
}
public void push(int num) {
if (top == size - 1) {
System.out.println("Stack overflow");
} else {
arr[++top] = num;
}
}
public int pop() {
if (top == -1) {
System.out.println("Stack underflow");
return -1;
} else {
return arr[top--];
}
}
}
이 코드는 정수 배열을 사용하여 스택을 구현합니다. push() 메서드는 최상위 인덱스를 증가시키고 해당 인덱스에 있는 요소를 새 요소로 설정하여 스택의 맨 위에 요소를 추가합니다. pop() 메서드는 맨 위 인덱스에 있는 요소를 반환하고 맨 위 인덱스를 감소시켜 스택 맨 위에서 요소를 제거합니다.
스택을 사용하여 괄호 문자열이 균형을 이루고 있는지 확인:
public boolean isBalanced(String str) {
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
이 코드는 괄호, 대괄호 및 중괄호 문자열이 문자 스택을 사용하여 균형을 이루는지 확인합니다. 이 코드는 문자열의 각 문자를 반복하고 여는 대괄호를 스택으로 푸시합니다. 닫는 괄호가 있으면 코드는 스택에서 맨 위 문자를 팝하고 해당하는 여는 괄호와 일치하는지 확인합니다. 스택이 비어 있거나 대괄호가 일치하지 않으면 코드는 false를 반환합니다. 반복이 완료되고 스택이 비어 있으면 코드는 true를 반환합니다.
