📌 스택(Stack)이란?

스택의 사전적 의미는 ‘쌓다’입니다. 쌓여있는 박스와 같이 차곡차곡 쌓아 올린 형태의 구조를 스택(stack)이라 부릅니다. 이러한 스택의 개념을 추상화하여 자료구조로 만든 것이 스택 자료구조입니다.

특징

• 데이터의 삽입과 삭제는 top이라고 일컫는 한 쪽 끝에서만 이루어지도록 제한하여 만든 자료구조입니다. 즉, 통과할 수 있는 문이 하나 뿐인 자료구조입니다.
• LIFO(Last In Firtst Out, 후입선출) : 먼저 들어간 것이 밑에 위치하기 때문에 나중에 나오게 되고 나중에 들어간 것이 위에 위치하기 때문에 먼저 나오는 형태의 자료구조

관련 용어

• Top(peek): 스택의 최상단을 의미, 가장 최근에 들어온 데이터
• Push: 스택에 top에 데이터를 넣는 행위
• Pop: 스택의 top에서 데이터를 빼는 행위
• empty/full: 스택이 비었는지 가득 찼는지 검사
• size(level): 스택의 크기 리턴

시간복잡도

• 삽입: Insertion O(1)
• 삭제: Deletion O(1) (pop) / O(N) (remove)
• 검색: Search O(N)

📌 스택(Stack) 구현

public class ArrayStack {
    int top;    //인덱스
    int size;    //스택 배열의 크기
    int [] stack;
    public ArrayStack(int size) {
        this.size = size;
        stack = new int[size];
        top = -1;
    }

    public void push(int item) {
        stack[++top] = item;
        System.out.println(stack[top] + " Push!");
    }
    public void pop() {
        System.out.println(stack[top] + " Pop!");
        int pop = stack[top];
        stack[top--] = 0;
    }
    public void peek() {
        System.out.println(stack[top] + " Peek!");
    }
}

📌 스택(Stack) 사용

Stack<Integer> stack = new Stack<>(); //int형 스택 선언
stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.peek();     // stack의 가장 상단의 값 출력
stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)
stack.pop();       // stack에 값 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

참고

• https://gyoogle.dev/blog/computer-science/data-structure/Stack%20&%20Queue.html
• https://go-coding.tistory.com/5

피드백 및 개선점은 댓글을 통해 알려주세요😊