스택

먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다.

• 스택(stack)의 어원은 "쌓는다."
• 선입후출(FILO; First In Last Out): 먼저 들어간 것이 마지막에 나오는 규칙
• 푸시(PUSH): 데이터를 삽입하는 연산
• 팝(POP): 데이터를 꺼내는 연산

---

스택 ADT

• ADT(Abstract Data Type; 추상 자료형): 인터페이스만 있고 실제로 구현은 되지 않은 자료형
  - 파이썬에서는 스택을 제공하지 않지만 리스트 메서드인 append(), pop() 메서드로 스택을 대체할 수 있다.
  - 덱(deque)은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 달리 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료 구조이다. 이런 덱의 특징을 조금만 응용하면 스택처럼 사용할 수 있다.

스택에는 푸시(push), 팝(pop), 가득 찼는지 확인(isFull), 비었는지 확인(isEmpty)과 같은 연산 정의해야 한다.
그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 탑(top)도 있어야 한다.

구분	정의	설명
연산	boolean isFull()	스택에 들어있는 데이터 개수가 maxsize인지 확인해 boolean값 반환한다. 가득 차 있다면 True, 아니면 False
연산	boolean isEmpty()	스택에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다. 데이터가 하나라도 있으면 False, 아니면 True
연산	void push(Item Type item)	스택에 데이터를 푸시한다.
연산	ItemType pop()	스택에서 최근에 푸시한 데이터를 팝하고, 그 데이터를 반환한다.
상태	int top	스택에서 최근에 푸시한 데이터의 위치를 기록한다.
상태	ItemType data[maxsize]	스택의 데이터를 관리하는 배열이다. 최대 maxsize개의 데이터를 관리한다.

---

스택 구현하기

stack = []  # 스택 리스트 초기화
max_size = 10  # 스택의 최대 크기 정의


# 가득 찼는지 확인하는 함수
def isFull(stack):
    return len(stack) == max_size


# 비었는지 확인하는 함수
def isEmpty(stack):
    return len(stack) == 0


# 푸시 함수
def push(stack, item):
    if isFull(stack):
        print("Full")
    else:
        stack.append(item)
        print("Pushed")


# 팝 함수
def pop(stack):
    if isEmpty(stack):
        print("Empty")
        return None
    else:
        return stack.pop()