스택(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에 추가하여 문자열을 뒤집는다.

profile
I'm still hungry.

0개의 댓글