[자료구조] 스택(Stack)

스택이란 ?

stack의 뜻을 사전에서 찾아보니 쌓이다, 채우다, 무더기 라는 뜻이 나온다.

그럼 자료구조에서 스택이란 무엇일까 ?

 

바로 데이터를 순서대로 쌓는 자료구조이다.

 

음 .. 간단하게 예시를 들어보자면 스택은 박스다.

박스에 물품들을 차곡차곡 쌓다보면 마지막에 저장한 물품을 가장 먼저 꺼내게 된다.

스택도 동일한 구조이다.

 

스택의 특징

• 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out) 구조이다.
  • 즉, 스택은 박스와 같은 구조로 양 옆과 바닥이 막혀 있어서 한 방향으로만 뺄 수 있는 구조이다.

• 넣은 순서와 꺼낸 순서가 역순이 된다
  • 예를 들자면 스택에 0, 1, 2의 순서로 데이터를 넣고 꺼낸다면 2, 1, 0 순서로 꺼내게 된다.

• 파이썬에서 스택은 리스트로 쉽게 구현할 수 있다.
• 데이터는 하나씩 넣고 뺄 수 있다.
• 하나의 입출력 방향을 가지고 있다. 

 

스택의 특징

1. 원소의 추가의 시간복잡도는 O(1)이다.
2. 원소의 제거가 시간복잡도는 O(1)이다.
3. 제일 상단의 원소 확인하는데 시간복잡도는 O(1)이다.
4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다.

 

 

스택 구현

# 파이썬으로 스택 구현
stack = []


# Push 연산 구현
def push(x):
    stack.append(x)


# Pop 연산 구현
def pop():
    if not is_empty():
        stack.pop()


# Top 연산 구현
def top():
    if not is_empty():
        return stack[-1]


# Is_Empty 연산 구현
def is_empty():
    return len(stack) == 0


# test 함수 구현
def test():
    push(5)  # [5]
    push(4)  # [5, 4]
    push(3)  # [5, 4, 3]
    print(top())  # 3
    pop()  # [5, 4]
    pop()  # [5]
    print(top())  # 5
    push(10)  # [5, 10]
    push(12)  # [5, 10, 12]
    print(top())  # 12
    pop()  # [5, 10]
    print(top())  # 10


# main 함수
def main():
    test()


if __name__ == "__main__":
    main()

 

 

스택의 활용

ex) 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로