스택(stack)은 데이터를 일시적으로 쌓아 놓는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO:Last In First Out)이다. 즉, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.
일상생활에서 브라우저의 뒤로가기와 앞으로가기 버튼을 생각하면 된다.
WebPage1 → WebPage2 → 뒤로가기 → WebPage1 → 앞으로가기 → WebPage2
스택에 데이터를 넣는 작업을 푸시(push)라하고 꺼내는 것을 팝(pop)이라 한다.
또, 푸시와 팝이 이루어지는 쪽을 탑(top)이라하고, 그 반대쪽인 스택의 가장 아랫부분을 바텀(bottom)이라고 한다.
피크(peek) 메소드는, 스택의 최상위 요소를 반환하지만, 제거하지는 않는다.
따라서 스택의 최상위 요소를 확인할 때 유용하게 사용된다.
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
int top = stack.peek(); // top = 3
출처 : java2blog.com
하나의 배열을 공유하여 2개의 스택 구현
그림으로 표현하면 위와 같은 형식이다.
아래는 java코드로 예시 구현해본 것이다 (Chat-GPT)
public class TwoStacks {
private int[] arr; // 공유 배열
private int top1; // 첫 번째 스택의 top
private int top2; // 두 번째 스택의 top
private int size; // 스택의 크기
public TwoStacks(int size) {
this.arr = new int[size];
this.top1 = -1;
this.top2 = size;
this.size = size;
}
// 첫 번째 스택에 데이터를 push하는 메소드
public void push1(int data) {
if (top1 < top2 - 1) {
arr[++top1] = data;
} else {
System.out.println("Stack Overflow");
}
}
// 첫 번째 스택에서 데이터를 pop하는 메소드
public int pop1() {
if (top1 >= 0) {
int data = arr[top1--];
return data;
} else {
System.out.println("Stack Underflow");
return -1;
}
}
// 두 번째 스택에 데이터를 push하는 메소드
public void push2(int data) {
if (top2 > top1 + 1) {
arr[--top2] = data;
} else {
System.out.println("Stack Overflow");
}
}
// 두 번째 스택에서 데이터를 pop하는 메소드
public int pop2() {
if (top2 < size) {
int data = arr[top2++];
return data;
} else {
System.out.println("Stack Underflow");
return -1;
}
}
public static void main(String[] args) {
TwoStacks ts = new TwoStacks(6);
ts.push1(1);
ts.push1(2);
ts.push1(3);
ts.push2(4);
ts.push2(5);
ts.push2(6);
System.out.println(ts.pop1()); // 3
System.out.println(ts.pop2()); // 6
}
}
스택의 메소드
push(value) : Stack의 맨 위에 새로운 항목을 추가한다.
pop() : Stack의 맨 위에 있는 항목을 제거하고 반환한다.
peek() : Stack의 맨 위에 있는 항목을 반환합니다. 제거하지 않는다.
is_empty() : Stack이 비어 있는지 여부를 반환한다.
size() : Stack의 크기를 반환한다.
contains() : Stack 내에 특정 값이 존재하는지 확인한다.
팝(pop)하는 값 출력하기
팝pop되는 값이 뭔지 출력하면서 팝 진행하기
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack);
System.out.println(stack.pop()); // 팝되는 값이 무엇인지 출력
System.out.println(stack); // 팝이 완료된 후 출력
}
}출력결과
[1, 2, 3]
3
[1, 2]🌌 Chat-GPT가 준 예제
스택 활용 예제 1
문자열에서 가장 마지막으로 등장하는 문자의 인덱스 찾기
import java.util.Stack;
public class Main {
public static int lastIndexOf(String str, char c) {
if (str == null || str.length() == 0) {
return -1;
}
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == c) {
stack.push(i);
}
}
if (stack.isEmpty()) {
return -1; // 없는 경우 -1 반환
}
return stack.pop();
}
public static void main(String[] args) {
String str = "Hello, World!";
char c1 = 'o';
char c2 = 'x';
int lastIndex1 = lastIndexOf(str, c1);
int lastIndex2 = lastIndexOf(str, c2);
System.out.println("Last index of '" + c1 + "' in \"" + str + "\" is " + lastIndex1);
System.out.println("Last index of '" + c2 + "' in \"" + str + "\" is " + lastIndex2);
}
}
출력 결과
Last index of 'o' in "Hello, World!" is 8 // 8번째
Last index of 'x' in "Hello, World!" is -1 // 없다는 뜻이 코드에서는 Stack을 사용하여 주어진 문자열에서 가장 마지막으로 등장하는 문자의 인덱스를 찾는 lastIndexOf() 메소드를 정의한다. 이 메소드에서는 문자열을 한 글자씩 읽어들이면서, 주어진 문자와 일치하는 문자가 나타날 때마다 해당 인덱스를 Stack에 추가한다.
모든 문자를 읽은 후, Stack이 비어 있지 않은 경우 가장 마지막에 추가된 인덱스를 반환한다.
위 코드의 main() 메소드에서는 예제로 주어진 문자열에서 'o'와 'x' 문자의 마지막 등장 인덱스를 찾아 출력한 것이다.
스택 활용 예제 2
덧셈, 뺄셈, 곱셈, 나눗셈 연산 수행
import java.util.Stack;
public class Main {
public static int calculate(String expression) {
if (expression == null || expression.length() == 0) {
return 0;
}
Stack<Integer> stack = new Stack<>();
int num = 0;
char op = '+';
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == expression.length() - 1) {
if (op == '+') {
stack.push(num);
} else if (op == '-') {
stack.push(-num);
} else if (op == '*') {
stack.push(stack.pop() * num);
} else if (op == '/') {
stack.push(stack.pop() / num);
}
num = 0;
op = c;
}
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
public static void main(String[] args) {
String expression1 = "3+3*3"; // 12
String expression2 = " 3/2 "; // 1 - 소수 버림
String expression3 = " 3+5 / 2 "; // 3+(5/2) = 3+2 = 5
System.out.println(expression1 + " = " + calculate(expression1));
System.out.println(expression2 + " = " + calculate(expression2));
System.out.println(expression3 + " = " + calculate(expression3));
}
}
출력 결과
3+3*3 = 12
3/2 = 1
3+5 / 2 = 5이 코드에서는 Stack을 사용하여 주어진 수식의 덧셈, 뺄셈, 곱셈, 나눗셈 연산을 수행하는 calculate() 메소드를 정의하고, 수식 문자열을 한 글자씩 읽어들이면서, 숫자일 경우 현재 값을 계속 곱하고 더해나가며, 연산자일 경우 Stack에 현재 값을 저장한다.
모든 문자열을 읽은 후, Stack에서 값을 하나씩 꺼내서 덧셈을 수행한다.
스택 활용 예제 3
문자열 뒤집기
import java.util.Stack;
public class ReverseString {
public static String reverse(String s) {
if (s == null || s.length() == 0) {
return s;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
stack.push(s.charAt(i));
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
public static void main(String[] args) {
String s = "Hello, World!";
System.out.println("Original string: " + s);
System.out.println("Reversed string: " + reverse(s));
}
}
출력 결과
Original string: Hello, World!
Reversed string: !dlroW ,olleH
위 코드에서는 Stack을 사용하여 문자열을 뒤집는 reverse() 메소드를 정의한다.
주어진 문자열을 한 글자씩 Stack에 추가하고, Stack이 비어 있지 않은 경우 가장 위에 있는 글자를 StringBuilder에 추가하여 문자열을 뒤집는다.
