[자료구조/알고리즘] 스택(Stack)

스택(Stack)

• 정의
  - 후입선출(Last in First out -> LIFO) 자료구조
  • 가장 마지막에 들어온 데이터가 먼저 나가는 구조
• 용도
  - 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용
  ex) 함수 콜 스택, 수식 계산, 인터럽트 처리
  

이 때 가장 마지막으로 들어온 데이터를 Top, 가장 처음 들어온 데이터를 Bottom이라고 한다

시간복잡도

• 탐색: O(n)
• 삽입, 삭제: O(1)
  - Top에서만 데이터 출입이 일어나기 때문
  

구현

• 별도의 라이브러리를 사용하지 않고 구현
• 가변배열 형태로 구현
• 자바의 Stack 클래스와 동일하게 구현

// 배열을 이용한 기본 스택 직접 구현

class CustomStack {
    int[] arr;
    int top = -1;

    CustomStack(int size) {
        arr = new int[size];
    }

    public boolean isEmpty() {
        if (this.top == -1) {
            return true;
        } else {
            return false;
        }
    }

    public void push(int data) {
        this.top += 1;

        if (this.top == arr.length) {
            int[] newArr = new int[this.top + 1];
            for (int i = arr.length - 1; i >= 0; i--) {
                newArr[i] = arr[i];
            }
            newArr[this.top] = data;
            arr = newArr;
        } else {
            this.arr[this.top] = data;
        }
    }

    public Integer pop() {
        if (this.isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }

        Integer data = this.arr[this.top];
        int[] newArr = new int[this.top];
        this.top -= 1;

        for (int i = 0; i <= top; i++) {
            newArr[i] = this.arr[i];
        }
        arr = newArr;
        return data;
    }

    public Integer peek() {
        if (this.isEmpty()) {
            System.out.println("Stack is empty!");
            return null;
        }

        return this.arr[this.top];
    }

    public void printStack() {
        for (int i = 0; i < this.top + 1; i++) {
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        // Test code
        CustomStack myStack = new CustomStack(5);
        myStack.isEmpty();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.push(6);
        myStack.printStack();               // 1, 2, 3, 4, 5

        System.out.println(myStack.peek()); // 5
        myStack.printStack();               // 1, 2, 3, 4, 5

        System.out.println(myStack.pop());  // 5
        myStack.printStack();               // 1, 2, 3
        System.out.println(myStack.pop());  // 4
        myStack.printStack();               // 1, 2, 3

        System.out.println(myStack.pop());  // 3
        System.out.println(myStack.pop());  // 2
        System.out.println(myStack.pop());  // 1
        myStack.printStack();
    }
}

이미지 출처

https://yoongrammer.tistory.com/45