[자료구조] 스택(Stack)

 

 

스택(Stack)의 특징

  1. LIFO 구조
    • 후입선출(Last In, First Out) 방식으로 동작한다.
    • 나중에 삽입된 데이터가 가장 먼저 제거된다.
  2. 단일 접근점
    • 데이터의 삽입과 제거는 한쪽 끝에서만 이루어집니다(보통 top 또는 head라 부릅니다).
  3. 주요 용어
    • push: 데이터를 스택의 맨 위에 삽입.
    • pop: 스택의 맨 위 데이터를 제거.
    • peek: 스택의 맨 위 데이터를 제거하지 않고 확인.
    • isEmpty: 스택이 비어 있는지 확인.

 

스택의 장점

  1. 간단한 구현
    • 자바에서는 단순히 메서드만 사용하면 금방 구현이 가능하다.
  2. 재귀 문제 해결에 유용
    • 함수 호출 기록을 저장하고 복원하는 데 사용된다.
    • DFS(깊이 우선 탐색) 같은 알고리즘에 필수적이다.
  3. 일시적인 데이터 저장
    • 데이터를 임시 저장하고 나중에 처리하는 데 적합하다.
    • ex) 괄호 검사, 문자열 뒤집기.
  4. 빠른 데이터 접근
    • 스택의 맨 위 데이터에 대한 접근이 시간복잡도 O(1)로 빠르고 효율적이다.

 

스택의 단점

  1. 제한된 데이터 접근
    • 스택은 맨 위(top) 외의 데이터에 직접 접근할 수 없다.
    • 중간 데이터를 읽으려면 다른 자료구조가 필요하다.
  2. 고정 크기(배열 기반 스택)
    • 배열을 사용해 구현할 경우 스택 크기를 미리 정의해야 하며, 크기를 초과하면 Stack Overflow가 발생한다.
  3. 메모리 사용 문제
    • 재귀 호출에서 깊이가 너무 깊으면 스택 메모리가 부족해 Stack Overflow Error가 발생할 수 있다.

 

스택 사용 사례

  1. 알고리즘과 문제 해결
    • DFS(깊이 우선 탐색)
    • 괄호 짝 검사
    • 문자열 뒤집기
    • 이진 트리 순회 (후위/전위 순회)
  2. 시스템 프로세스 관리
    • 함수 호출 및 복귀를 관리하는 콜 스택.
  3. 문서 편집기
    • 실행 취소(Undo) 및 재실행(Redo) 기능 구현.
  4. 수식 계산기
    • 중위(Infix), 후위(Postfix), 전위(Prefix) 표기법의 변환과 계산.

 

JAVA에서 스택 구현 예제

 

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Stack 생성
        Stack<Integer> stack = new Stack<>();

        // push 연산: 데이터 삽입
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // 현재 스택 상태 출력
        System.out.println("Stack after pushes: " + stack);

        // peek 연산: 맨 위 데이터 확인
        System.out.println("Top element: " + stack.peek());

        // pop 연산: 맨 위 데이터 제거
        int removedElement = stack.pop();
        System.out.println("Removed element: " + removedElement);

        // 현재 스택 상태 출력
        System.out.println("Stack after pop: " + stack);

        // isEmpty 연산: 스택 비어있는지 확인
        System.out.println("Is stack empty? " + stack.isEmpty());
    }
}

 

실행결과

 

Stack after pushes: [10, 20, 30]
Top element: 30
Removed element: 30
Stack after pop: [10, 20]
Is stack empty? false

 

 

근데 이제 기본제공하는 구조체 안쓰고 해보기

 

 

public class MyStack {

    private int[] stack;
    private int top;

    /**
     * 기본 생성자
     * stack 크기 = 10
     */
    public MyStack() {
        stack = new int[10];
        top=-1;
    }
    /**
     * 기본 생성자 2
     * stack 크기 받아서 생성
     */
    public MyStack(int size) {
        stack = new int[size];
        top=-1;
    }

    /** stack에 값 넣기 = push
     *  정수를 stack에 넣음
     *
     *  top에 1을 더하고
     *  stack의 길이 이상으로 push 하려하면 배열 늘려주고 push
     *
     * @param x
     */
    public void push(int x) {
        top = top+1;
        if(size() < stack.length) {
            stack[top] = x;
        } else {
            increaseStack();
            stack[top] = x;
        }
    }

    /** stack에서 값 빼기  = pop
     *  제일 마지막에 push된 정수를 반환
     * top 위치의 정수를 빼고 top을 -1 해주고 해당값 반환
     * @return
     */
    public int pop() {

        if(size() >= 0) {
            int temp = stack[top];
            stack[top--]=0;
            return temp;
        }
        else return -1;
    }
    /** stack이 비었는지 확인
     *  top이 0보다 작으면 비어있는것 return true
     *  top이 0보다 크거나 같으면 비어있지 않은것 return false
     * @return
     */
    public boolean isEmpty() {
        return top < 0;
    }

    /** stack의 크기 확인
     *  크기를 int로 반환
      * @return
     */
    public int size() {
        return top;
    }

    /**
     * 스택의 내용을 출력해주는 함수
     */
    public void print() {
        System.out.println("┌─────┐");
        for(int i=top; i>=0; i--) {
            System.out.println("│  "+stack[i]+"  │");
            if (i == 0) {
                System.out.println("└─────┘");
            } else {
                System.out.println("├─────┤");
            }
        }
    }

    /**
     * stack 꽉차면 한칸 늘리는 함수
     */
    public void increaseStack() {
        int[] temp = new int[stack.length+1];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack = temp;
    }

}

 

 

스택 활용

 

중위표기식 -> 후위표기식 전환

후위표기식 계산

문자열 뒤집기

 

 

메인함수

public class Main {
    public static void main(String[] args) {
        // 계산식 넣기
        String str = "((9-(2*1))-8)+4";

        // String을 stack으로
        MyStack myStack = UseStack.stringToStack(str);

        // 뒤집기
        myStack = UseStack.resverseStack(myStack);
        // 뒤집은거 출력
        myStack.print();
        // postfix 변환
        myStack = UseStack.convert(myStack);
        // 변환된 스택 출력
        myStack.print();

        // 변환된거 뒤집기
        myStack = UseStack.resverseStack(myStack);

        // string으로 옮기기
        StringBuilder sb = new StringBuilder();
        while(!myStack.isEmpty()) {
            char temp = (char) myStack.pop();
            System.out.print(temp+ " ");
            sb.append(temp);
        }

        // string으로 옮긴 계산식 계산하기
        System.out.println();
        System.out.println(UseStack.calc(sb.toString()));
    }
}

 

MyStack.javaint가 아닌 char stack으로 변경

public class MyStack {

    private char[] stack;
    private int top;

    /**
     * 기본 생성자
     * stack 크기 = 10
     */
    public MyStack() {
        stack = new char[10];
        top=-1;
    }
    /**
     * 기본 생성자 2
     * stack 크기 받아서 생성
     */
    public MyStack(int size) {
        stack = new char[size];
        top=-1;
    }

    /** stack에 값 넣기 = push
     *  정수를 stack에 넣음
     *
     *  top에 1을 더하고
     *  stack의 길이 이상으로 push 하려하면 배열 늘려주고 push
     *
     * @param x
     */
    public void push(char x) {
        top = top+1;
        if(size() < stack.length) {
            stack[top] = x;
        } else {
            increaseStack();
            stack[top] = x;
        }
    }

    /** stack에서 값 빼기  = pop
     *  제일 마지막에 push된 문자를 반환
     * top 위치의 정수를 빼고 top을 -1 해주고 해당값 반환
     * 뺄수없으면 null 반환
     * @return
     */
    public Object pop() {

        if(size() >= 0) {
            char temp = stack[top];
            top = top - 1;
            return temp;
        }
        else return null;
    }

    /**
     *  stack top 확인 = peek
     *  비어있지않다면 top의 값 보여줌 실제 pop X
     */
    public Object peek() {
        if(size() >= 0) {
            return stack[top];
        }
        else {
            return null;
        }
    }


    /** stack이 비었는지 확인
     *  top이 0보다 작으면 비어있는것 return true
     *  top이 0보다 크거나 같으면 비어있지 않은것 return false
     * @return
     */
    public boolean isEmpty() {
        return top < 0;
    }

    /** stack의 크기 확인
     *  크기를 int로 반환
      * @return
     */
    public int size() {
        return top;
    }

    /**
     * 스택의 내용을 출력해주는 함수
     */
    public void print() {
        System.out.println("┌─────┐");
        for(int i=top; i>=0; i--) {
            System.out.println("│  "+stack[i]+"  │");
            if (i == 0) {
                System.out.println("└─────┘");
            } else {
                System.out.println("├─────┤");
            }
        }
    }

    /**
     * stack 꽉차면 한칸 늘리는 함수
     */
    public void increaseStack() {
        char[] temp = new char[stack.length+1];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack = temp;
    }

}

 

 

UseStack.java

 

import java.util.ArrayList;
import java.util.List;

public class UseStack {

    /**
     * String을 stack으로
     * String을 charArray로 바꾸고 stack에 넣기
     * @param str
     * @return
     */
    static public MyStack stringToStack(String str) {
        MyStack stack = new MyStack();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            stack.push(chars[i]);
        }
        return stack;
    }

    /**
     * 스택 뒤집기
     * 새로운 스택 하나 생성해서
     * 기존 스택 pop한걸 새로운 스택에 push
     * @param stack
     * @return
     */
    static public MyStack resverseStack(MyStack stack) {
        MyStack newStack = new MyStack(stack.size());
        for (int i = stack.size(); i >= 0; i--) {
            newStack.push((char) stack.pop());
        }
        return newStack;
    }

    /**
     * 중위표기식을 후위표기식으로 변환
     *
     * @param stack
     * @return
     */
    static public MyStack convert(MyStack stack) {
        // 결과 스택
        MyStack newStack = new MyStack(stack.size());
        // 연산자 스택
        MyStack opStack = new MyStack(stack.size());

        // 후위표기식으로 변환
        for(int i = stack.size(); i >= 0; i--) {
            char c = (char) stack.pop();
                switch (c) {
                    // 피연산자는 바로 결과배열에 추가
                    // 연산자는 경우에 따라 달라짐
                    case '(' -> {
                        opStack.push(c);
                    }
                    case ')' -> {
                        // ( 가 나올때까지 연산자스택에서 pop해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.pop();
                            if(temp == '(') {
                                break;
                            }
                            newStack.push(temp);
                        }
                    }
                    case '+', '-' -> {
                        // 자기보다 낮은거 만날때까지 연산자스택에서 pop 해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.peek();
                            if(temp == '(' ) {
                                break;
                            } else {
                                newStack.push((char) opStack.pop());
                            }
                        }
                        opStack.push(c);
                    }
                    case '*', '/' -> {
                        // 자기보다 낮은거 만날때까지 연산자스택에서 pop 해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.peek();
                            if(temp == '+' || temp == '-' || temp == '(') {
                                break;
                            } else {
                                newStack.push((char) opStack.pop());
                            }
                        }
                        opStack.push(c);
                    }

                    // c가 알파벳이면 바로 결과스택에 추가
                    default -> {
                        newStack.push(c);
                    }
                }

        }
        // 남은 연산자가 있으면 다 pop해서 결과스택에 넣어주고 결과스택을 return
        while(!opStack.isEmpty()) {
            newStack.push((char)opStack.pop());
        }
        return newStack;
    }

    /**
     * 후위표기식을 계산
     * 피연산자는 stack에 저장
     * 연산자가 나오면 stack에서 피연산자 2개 빼서 연산하고 다시 stack에 저장
     * 마지막 stack에 남은 숫자가 계산결과이므로 return
     * @param str
     * @return
     */
    static public int calc(String str) {
        List<Character> op = new ArrayList<Character>();
        op.add('+');
        op.add('-');
        op.add('*');
        op.add('/');
        char[] chars = str.toCharArray();
        MyStack stack = new MyStack();
        for (char aChar : chars) {
            if (op.contains(aChar)) {
                int b = (char) stack.pop() - '0';
                int a = (char) stack.pop() - '0';

                switch (aChar) {
                    case '+' -> {
                        stack.push((char) ((a + b) + '0'));
                    }
                    case '-' -> {
                        stack.push((char) ((a - b) + '0'));
                    }
                    case '*' -> {
                        stack.push((char) ((a * b) + '0'));
                    }
                    case '/' -> {
                        stack.push((char) ((a / b) + '0'));
                    }
                }
            } else {
                stack.push(aChar);
            }
        }
        return (char)stack.pop() - '0';
    }
}

 

'알고리즘공부 > 자료구조' 카테고리의 다른 글

[자료구조] Avl Tree  (0) 2025.01.17
[자료구조] 이진트리  (0) 2025.01.17
[자료구조] B+ tree  (0) 2025.01.17
[자료구조] LinkedList  (0) 2025.01.16
[자료구조] 큐(Queue)  (0) 2024.11.28