[자료구조] Stack - 스택

일상 회고록·2024년 7월 6일

stack 스택 자료구조

자료구조 모음집

목록 보기

3/7

안녕하세요!!

오늘의 주제는 스택 자료구조입니다!

그래도 배열, 리스트, 스택까지는 많은 개발자분들이 익숙하고, 많이 사용해보셨을거라고 생각합니다!
원래 알던 부분은 좀 더 확실하게, 몰랐던 부분은 새롭게 가져가는 포스트이길 바랍니다ㅎㅎ

그럼 시작하겠습니다!

1. 개념

Stack - 스택은 ‘쌓아놓은 더미’라는 뜻으로, 데이터들을 아래부터 위로 쌓아놓은 선형 자료구조입니다.

스택의 가장 큰 특징은 후입선출, 즉, Last In First Out - LIFO 입니다.

아래에서부터 쌓아올린 구조이기 때문에 먼저 저장된 데이터는 위에 쌓여진 데이터들을 모두 꺼낸 후에 꺼낼 수 있습니다.

반대로 말하면 가장 나중에 저장된 데이터를 가장 먼저 꺼내게 됩니다.

스택은 후입선출을 유지하는 선형리스트라고도 할 수 있습니다.

(개인적으로 프링글스 예시가 가장 와닿았습니다.💨💨💨)

위와같은 특징을 가지고 있는 스택은 ‘되돌리기’ 기능에 많이 사용됩니다.

웹 뒤로가기
문서 작업 중 컨트롤+Z로 되돌리기
JVM에서의 스택 메모리

이외의 작업에도 많은 곳에 스택 자료구조가 사용됩니다.

1-1. 구조

스택의 구조는 추상화하자면 위와 같이 생겼습니다.

하나하나 구분지어 설명하자면,

Stack Top - 스택의 가장 위부분을 의미합니다.
Stack Bottom - 스택의 가장 아래부분을 의미합니다
Element - 스택에 저장되는 데이터를 의미합니다.
Empty Stack - 저장된 데이터가 없는 빈 스택을 의미합니다.
Full Stack - 스택이 모두 차서 공간이 없는 풀 스택을 의미합니다.

2. 장단점

장점

구조가 단순해서 구현이 쉽습니다
데이터의 삽입과 조회가 빠릅니다

단점

후입선출의 특성으로 문제를 해결하는 것이 제한적일 수 있습니다 (장점이 되기도 합니다)
배열로 스택을 구현하는 경우 크기를 미리 결정해야 합니다.

3. 구현

3-1. Java

자바에서의 스택을 깊게 이해하기 위해선 자바의 컬렉션 프레임워크를 이해하는 것이 좋습니다.

하지만 다뤄야할 내용이 많고, 중요한 내용이다보니 따로 정리해서 업데이트 하겠습니다!

아무튼, 자바에서의 Stack 클래스는 Vector 클래스를 상속받고 있습니다.

사용할 수 있는 메소드로는,

push() - 스택의 가장 위에 데이터 추가
pop() - 스택의 가장 위의 데이터를 꺼내고 반환
peek() - 스택의 가장 위의 데이터를 꺼내지 않고 값만 반환
empty() - 스택이 비어있는지 확인
search(Object o) - 스택에 들어있는 특정 값의 위치를 반환, 없다면 -1 반환 (인덱스가 0 이아닌 1부터 시작)

// 스택 객체 생성 
Stack stack = new Stack<>();
Stack<String> stack1 = new Stack<>();

// 스택에 데이터 저장
stack.push(99);
stack.push(3);
stack1.push('Hello');

int topItemPop = (int) stack.pop();
// 출력 -> 99

int topItemPeek = (int) stack.peek();
// 출력 -> 3

boolean emptyStack = stack.isEmpty();
// 출력 -> false

int idx = stack1.search("Hello");
// 출력 -> 1

위와같이 스택을 만들고 메소드를 통해 사용할 수 있습니다.

조금 더 자바의 스택에 대해 알아볼까요?

자바의 Stack 클래스를 들어가보면 가장 상단에 위와같은 설명이 있습니다.

요약하자면, LIFO의 특성을 잘 활용하기 위해 Stack 보단 Deque의 사용을 권장하고 있습니다.

오잉? 위에 잔뜩 설명했는데 사용하지 말라니나요???

그 이유는 Vector 클래스를 상속하고 있기 때문입니다.

자바에서 Vector는 굉장히 오래된 (자바1부터) 어르신입니다. 따라서 여러가지 취약점이 많고, 상속하는 경우 Vector의 메소드를 그대로 사용할 수 있기 때문에 잘못 사용하는 경우가 발생합니다.

대표적으로 Stack 클래스는 Vector의 add() 메소드를 사용할 수 있습니다.

해당 메소드를 사용하면 스택의 특성인 가장 위에서만 데이터를 저장하고, 꺼내는 특성이 사라지게 됩니다.

사용할 이유가 없어지는 것이죠!

그래서 Deque의 사용을 권장하고 있습니다. (Deque는 곧 다룰 예정입니다🫡)

그렇게 중요한 부분은 아니지만, 자바 사용자라면 한번쯤 짚고 넘어갈 부분인 것 같습니다.

3-2. Python

파이썬은 스택을 따로 제공하고 있지 않고, 리스트를 활용하고 있습니다.

# 스택 객체 생성 
stack = []

# 스택에 데이터 저장
stack.append(99);
stack.append(3);

topItemPop = stack.pop();
// 출력 -> 99

직접 클래스를 정의해서 사용할 수도 있습니다.

# Stack Clas
class stack:
    def __init__(self):  
        self.items = []

	  # 스택에 데이터 추가
    def push(self, item): 
        self.items.append(item)

    # 스택 가장 위 데이터 꺼내고 반환
    def pop(self): 
        return self.items.pop()

    # 스택 가장 위 데이터 꺼내지 않고 반환
    def peek(self): 
        return self.items[-1]

    # 스택이 비었는지 확인
    def isEmpty(self):
        return not self.items

stack = stack()
stack.push(99);
stack.push(3);

print(stk.pop())  # 99
print(stk.peek())  # 3
print(stk.isEmpty())  # False