[자료구조] 스택 (Stack)

💁‍♀️ 스택

스택은 데이터를 순서대로 쌓는 자료구조이다. 데이터를 저장하는 방법은 배열과 비슷한데, 세 가지 제약이 있다.

• 데이터는 스택의 끝에만 삽입할 수 있다.
• 데이터는 스택의 끝에서만 읽을 수 있다.
• 데이터는 스택의 끝에서만 삭제할 수 있다.

원통에 든 과자 프링글스를 상상하면 모양새가 비슷하다. 스택 자료구조의 특징은 다음과 같다.

• LIFO(Last In First Out)/후입선출

		stack.push(1);
        stack.push(2);
        stack.push(3);
        ---순서대로 1, 2, 3 입력---
        System.out.println(stack.pop()); // 3
        System.out.println(stack.pop()); // 2
        System.out.println(stack.pop()); // 1

스택은 끝에서만 삽입과 삭제를 할 수 있으므로 입출력의 순서도 선입선출이 아닌, 후입선출이다.

• 데이터는 하나씩 넣고 뺄 수 있다.
  데이터는 하나씩만 넣고 뺄 수 있다. 한 번에 여러 개씩 넣고 뺄 수는 없다.

• 하나의 입출력 방향을 가지고 있다.
  입출력 방향이 같기 때문에, 여러 개의 입출력 방향을 가진 자료구조는 스택이라고 볼 수 없다.

스택 클래스의 대표적인 메서드는 다음과 같다.

메서드	설명
push()	스택에 데이터 추가
pop()	가장 나중에 추가된 데이터를 스택에서 삭제, 삭제한 데이터 리턴
size()	스택에 추가된 데이터의 크기 리턴
peek()	가장 나중에 추가된 데이터 리턴
clear()	현재 스택에 포함된 모든 데이터 삭제
empty()	스택이 비어있는지 확인 (비었으면 true)
contains(int value)	스택에 값이 있는지 확인 (있다면 true)

✨ 스택 구현

class StackPracticeTest {
    ArrayList<Integer> arrayStack = new ArrayList<>();

    public void push(int num) {
        arrayStack.add(num);
    }
    public Integer pop() {
        if(arrayStack.size() == 0) return null;

        return arrayStack.remove(arrayStack.size()-1);
    }
    public String show() {
        return arrayStack.toString();
    }
    public Integer peek() {
        return arrayStack.get(arrayStack.size()-1);
    }

}
public class StackPractice {
    public static void main(String[] args) {
        Stack stack = new Stack();

        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);

        System.out.println(stack.search(3)); // 3
        System.out.println(stack.size()); // 5

        System.out.println(stack.peek()); // 5

        System.out.println(stack.pop()); // 5
        System.out.println(stack.pop()); // 4
        System.out.println(stack.pop()); // 3


    }
}

참고 자료
『 누구나 자료 구조와 알고리즘』