[Python] 스택(Stack)

스택(Stack)

스택(Stack)

• 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)의 특징을 갖는 자료구조
• 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다.
• 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 데이터를 추출하는 동작을 pop(팝)이라고 한다.
• 스택에서는 top(톱)이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다.

 

구현

① 스택의 초기화

SIZE = 5    # 스택의 크기
stack = [None for _ in range(SIZE)]
top = -1

 

② 데이터 삽입

스택이 꽉 찼는지 확인하는 함수

• 먼저 스택이 꽉 찼는지 확인한 후 스택에 여유 공간이 있을 때 데이터를 삽입해야 한다.
• top 값이 '스택 크기-1' 과 같다면 스택이 꽉 찬 상태이다.

if (top값 == 스택크기-1) :
    스택이 꽉 찼음.

 

함수 완성하기

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

SIZE = 5
stack = ["커피", "녹차", "꿀물", "콜라", "환타"]
top = 4

print("스택이 꽉 찼는지 여부 ==>", isStackFull())

 

스택이 꽉 찼는지 여부 ==> True

 

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

• 먼저 스택이 꽉 찼는지 확인하고, 여유가 있을 경우 데이터를 삽입한다.

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

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

SIZE = 5
stack = ["커피", "녹차", "꿀물", "콜라", None]
top = 3

print(stack)
push("환타")
print(stack)
push("게토레이")

 

['커피', '녹차', '꿀물', '콜라', None]
['커피', '녹차', '꿀물', '콜라', '환타']
스택이 꽉 찼습니다.

 

isStackFull() 함수를 없애고, push() 함수만으로 기능 구현하기

def push(data) :
    global SIZE, stack, top
    if (top >= SIZE - 1):   # *
        print("스택이 꽉 찼습니다.")
        return

    top += 1
    stack[top] = data

SIZE = 5
stack = ["커피", "녹차", "꿀물", "콜라", None]
top = 3

print(stack)
push("환타")
print(stack)
push("게토레이")

 

③ 데이터 추출

• 데이터를 추출하기 전에 먼저 스택에 데이터가 있는지 확인해야 한다.
• 스택에 데이터가 없는데도 데이터를 추출하려고 시도할 때는 별도의 조치를 취해야 한다.

 

스택이 비었는지 확인하는 함수

• top 값이 -1이라면 스택은 비어 있는 상태이다.

if (top값 == -1) :
    스택이 비었음.

 

함수 완성하기

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

SIZE = 5
stack = [None for _ in range(SIZE)]
top = -1

print("스택이 비었는지 여부 ==>", isStackEmpty())

 

스택이 꽉 찼는지 여부 ==> True

 

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

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
    data = stack[top]
    stack[top] = None
    top -= 1
    return data

SIZE = 5
stack = ["커피", None, None, None, None]
top = 0

print(stack)
retData = pop()
print("추출한 데이터 -->", retData)
print(stack)
retData = pop()

 

['커피', None, None, None, None]
추출한 데이터 --> 커피
[None, None, None, None, None]
스택이 비었습니다.

 

isStackEmpty() 함수를 없애고, pop() 함수만으로 기능 구현하기

def pop() :
    global SIZE, stack, top
    if (top == -1) :    # *
        print("스택이 비었습니다.")
        return
    data = stack[top]
    stack[top] = None
    top -= 1
    return data

SIZE = 5
stack = ["커피", None, None, None, None]
top = 0

print(stack)
retData = pop()
print("추출한 데이터 -->", retData)
print(stack)
retData = pop()

 

④ 데이터 확인

• top 위치의 데이터를 확인만 하고 스택에 그대로 두는 것을 Peek(픽)이라고 한다.

 

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

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

SIZE = 5
stack = ["커피", "녹차", "꿀물", None, None]
top = 2

print(stack)
retData = peek()
print("top의 데이터 확인 -->", retData)
print(stack)

 

['커피', '녹차', '꿀물', None, None]
top의 데이터 확인 --> 꿀물
['커피', '녹차', '꿀물', None, None]

 

스택 완성

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

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

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

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

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

SIZE = int(input("스택의 크기를 입력하세요 ==> "))
stack = [ None for _ in range(SIZE) ]
top = -1

if __name__ == "__main__" :
    select = input("삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> ")

    while (select != 'X' and select != 'x') :
        if select=='I' or select =='i' :
            data = input("입력할 데이터 ==> ")
            push(data)
            print("스택 상태 : ", stack)
        elif select=='E' or select =='e' :
            data = pop()
            print("추출된 데이터 ==> ", data)
            print("스택 상태 : ", stack)
        elif select=='V' or select =='v' :
            data = peek()
            print("확인된 데이터 ==> ", data)
            print("스택 상태 : ", stack)
        else :
            print("입력이 잘못됨")

        select = input("삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> ")

    print("프로그램 종료!")

 

스택의 크기를 입력하세요 ==> 5
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 커피
스택 상태 :  ['커피', None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 녹차
스택 상태 :  ['커피', '녹차', None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> I
입력할 데이터 ==> 꿀물
스택 상태 :  ['커피', '녹차', '꿀물', None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> V
확인된 데이터 ==>  꿀물
스택 상태 :  ['커피', '녹차', '꿀물', None, None]
삽입(I)/추출(E)/확인(V)/종  (X) 중 하나를 선택 ==> E
추출된 데이터 ==>  꿀물
스택 상태 :  ['커피', '녹차', None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> E
추출된 데이터 ==>  녹차
스택 상태 :  ['커피', None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X)   하나를 선택 ==> E
추출된 데이터 ==>  커피
스택 상태 :  [None, None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중  나를 선택 ==> E
스택이 비었습니다.
추  된 데이터 ==>  None
스택 상태 :  [None, None, None, None, None]
삽입(I)/추출(E)/확인(V)/종료(X) 중 하나를 선택 ==> X
프로그램 종료!