Stack

스택(Stack)의 개념

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조

스택의 연산

• pop() : 스택에서 가장 위에 있는 항목 제거
• push(item) : item 하나를 스택의 가장 윗부분에 추가
• peek() : 스택의 가장 위에 있는 항목 반환
• isEmpty() : 스택이 비어 있을 때 true 반환

스택의 구현

스택은 배열이나 연결리스트로 구현할 수 있으며 Java에서 Stack 클래스 제공

public class Stack {
    int top;
    int[] stack;
    int size;

    public Stack(int size) {
        top = -1;
        stack = new int[size];
        this.size = size;

    }
    public void push(int value) {
        stack[++top] = value;
    }

    public int pop() {
        return stack[top--];
    }

    public int peek() {
        return stack[top];
    }

    public boolean isEmpty() {
        if (top < 0) {
            return true;
        } else {
            return false;
        }
    }
}

스택의 성질

1. 원소의 추가 : O(1)
2. 원소의 제거 : O(1)
3. 제일 상단의 원소 확인 : O(1)
4. 제일 상단이 아닌 나머지 원소들의 확인 및 변경 불가능

Reference

• https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html
• https://blog.encrypted.gg/933