[자료구조] [python] Stack(스택)

 

LIFO (후입 선출)구조를 따르는 자료 구조 

즉, 나중에 삽입된 데이터가 가장 먼저 꺼내지는 구조.

 

스택 연산 종류

1. push() : 스택에 원소를 추가.

2. pop() : 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.

3. peek() : 스택 가장 위에 있는 원소를 반환한다.  * python에서는 stack[-1]을 사용!

4. isEmpty() : 스택이 비어있다면 1, 아니면 0을 반환한다.

5. clear() : 강제 초기화, 비어있는지 여부 확인

6. isFull() : 가득 찼는지 여부 확인

7. size(): 스택에 저장되어 있는 데이터 개수 반환

 

 

**파이썬에서 스택 사용할 때, 라이브러리 필요없음.

---

예시

stack = []

# 스택에 데이터 삽입
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼내기
print(stack.pop())  # 3
print(stack.pop())  # 2
print(stack.pop())  # 1

 

n = int(input())

stack = []

for i in range(n):

    command = sys.stdin.readline().split()

    order = command[0]

    if order == 'push':
        data = command[1]
        stack.append(data)

    elif order == 'pop':
        if len(stack) == 0:
            print(-1)

        else:
            print(stack[-1])
            stack.pop(-1)

    elif order == 'size':
        print(len(stack))

    elif order == 'empty':

        if len(stack) == 0:
            print(1)

        else:
            print(0)

    elif order == 'top':
        if len(stack) == 0:
            print(-1)

        else:
            print(stack[-1])

---

collection.deque 라이브러리 활용

리스트보다 양쪽에서의 삽입/삭제가 효율적

#리스트로 구현
stack = []

stack.append(1)  # 삽입
stack.append(2)

print(stack.pop())  # 반환 및 삭제

#deque로 구현
from collections import deque

stack = deque()

stack.append(1)  # 삽입
stack.append(2)

print(stack.pop())  # 반환 및 삭제