스택

개념

--> 스택 자료구조는 한쪽 끝이 막힌 형태다.
--> 입구가 하나이기 때문에, 먼저 들어간 것이 가장 나중에 나오는 구조
--> 빠져나오는 순서는 들어간 순서의 역순이다.

원리

삽입과 추출이 한쪽에서만 진행된다.
push: 스택에 데이터를 삽입
pop: 스택에서 데이터를 추출
top: 스택에 들어있는 가장 위의 데이터 위치 (초기값: -1)

데이터 삽입: push

데이터가 비어있는 상태 (top: -1) -> top 1 증가 (top: 0) -> 데이터 삽입

데이터 추출: pop

top 위치의 데이터 추출 -> top 1 감소

간단 구현

--> 배열 형태로 구현

1. 스택 생성

stack = [None, None, None, None, None] ## 크기가 5인 스택
top = -1 # -1이면 스택이 비어있다는 뜻

2. 데이터 삽입: push

top += 1
stack[top] = 'coffee'
top += 1
stack[top] = 'greentea'
top += 1
stack[top] = 'honey'

3. 데이터 추출: pop

stack[top] = None # 데이터 삭제
top -= 1
stack[top] = None
top -= 1
stack[top] = None
top -= 1

일반 구현

1. 스택 초기화

SIZE = 5 # 스택 크기 설정
stack = [None for _ in range(SIZE)] # SIZE크기의 빈 스택 생성
top = -1 # 스택이 비어있는 상태

2. 데이터 삽입 과정

스택이 꽉 찬 상태인지 먼저 확인하는 함수를 선언해야 한다.
top의 값이 (스택의 크기 - 1) 과 같으면 꽉 찬 상태이다.

def isStackFull():
    global SIZE, stack, top
    if (top >= SIZE -1):
        return True # top의 값이 사이즈 -1 이면 꽉 찬 상태로 True 반환
    else:
        return False

* 스택에 데이터를 삽입하는 함수

def push(data):
    global SIZE, stack, top
    if (isStackFull()):
        print('스택이 꽉 찼습니다.')
        return
    top += 1
    stack[top] = data

3. 데이터 추출 과정

스택이 비어있는지 먼저 확인하는 함수를 선언해야 한다.
top의 값이 -1이면 스택이 빈 상태이다.

def isStackEmpty():
    global SIZE, stack, top
    if (top == -1):
        return True
    else:
        return False

* 스택에서 데이터를 추출하는 함수

def pop():
    global SIZE, stack, top
    if (isStackEmpty()):
        print('스택이 비어있습니다.')
        return None
    stack[top] = None
    top -= 1
    return data

4. 데이터 확인

peek: top 위치의 데이터를 확인만 하고 스택에 그대로 두는 것

def peek():
    global SIZE, stack, top
    if (isStackEmpty()):
        print('스택이 비었습니다.')
        return None
    return stack[top]