[Python] 스택(Stack)

스택(Stack)

스택(Stack)

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

 

스택의 간단 구현

• 스택은 배열 형태로 구현할 수 있다.
• 스택은 초기에 크기를 지정하고 배열로 생성할 수 있다.
• 스택의 맨 위쪽을 표현하는 top은 아직 데이터가 없으므로 -1로 초기화한다.
  • top이 -1이라는 것은 스택이 비었다는 의미로 해석하면 된다.

stack = [None, None, None, None, None]
top = -1

 

데이터 삽입 : push

stack = [None, None, None, None, None]
top = -1
 
top += 1
stack[top] = "커피"
top += 1
stack[top] = "녹차"
top += 1
stack[top] = "꿀물"
 
print("---- 스택 상태 ----")
for i in range(len(stack)-1, -1, -1) :
    print(stack[i])

None
None
꿀물
녹차
커피

 

데이터 추출 : pop

stack = ["커피", "녹차", "꿀물", None, None]
top = 2
 
print("--- 스택 상태-----")
for i in range(len(stack)-1, -1, -1) :
    print(stack[i])
 
print("-------------------")
data = stack[top]
stack[top] = None
top -= 1
print("pop -->", data)
 
data = stack[top]
stack[top] = None
top -= 1
print("pop -->", data)
 
data = stack[top]
stack[top] = None
top -= 1
print("pop -->", data)
print("-------------------")
 
print("--- 스택 상태-----")
for i in range(len(stack)-1, -1, -1) :
    print(stack[i])

--- 스택 상태-----
None
None
꿀물
녹차
커피
-------------------
pop --> 꿀물
pop --> 녹차
pop --> 커피
-------------------
--- 스택 상태-----
None
None
None
None
None

 

스택의 일반 구현

① 스택의 초기화

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
프로그램 종료!

 

스택의 활용 

① 웹 서핑에서 이전 페이지 돌아가기

• 웹 서핑을 할 때, 여러 웹 페이지를 방문하다가 웹 브라우저 왼쪽 위에 있는 [이전 페이지] 버튼을 클릭하면, 마지막 방문한 웹 페이지부터 차례대로 다시 방문한다.
• 이를 간단하게 스택으로 구현할 수 있다.
  • 웹 브라우저로 여러 웹 사이트를 방문하면, 방문한 URL을 스택에 push 해 놓는다.
  • 그리고 [이전 페이지] 버튼을 클릭한 개념으로 pop 해서 방문한 URL을 역순으로 재방문한다.

 

프로그램 구현

import webbrowser
import time
 
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 = 100
stack = [ None for _ in range(SIZE) ]
top = -1
 
if __name__ == "__main__" :
    urls = [ 'naver.com', 'daum.net', 'nate.com']
 
    for url in urls :
        push(url)
        webbrowser.open('http://'+url)
        print(url, end = '-->')
        time.sleep(1)
 
    print("방문 종료")
    time.sleep(5)
 
    while True :
        url = pop()
        if url == None :
            break
        webbrowser.open('http://'+url)
        print(url, end = '-->')
        time.sleep(1)
    print("방문 종료")

naver.com-->daum.net-->nate.com-->방문 종료
nate.com-->daum.net-->naver.com-->방문 종료

 

② 괄호의 매칭 검사

• 스택을 활용하여 간단하게 괄호의 매칭 검사를 수행할 수 있다.
• 여는 괄호를 만나면 push 하고, 닫는 괄호를 만나면 pop 한다 는 규칙을 적용한 후, push 또는 pop 하는 과정에서 다음의 조건을 확인하면 된다.

① 닫는 괄호를 만났을 때 스택은 비어 있지 않아야 한다.
② 닫는 괄호를 만났을 때 추출한 괄호는 여는 괄호여야 한다.
③ ②를 만족해도 두 괄호의 종류(소괄호, 중괄호, 대괄호)가 같아야 한다.
④ 모든 수식의 처리가 끝나면 스택은 비어 있어야 한다.

 

• 열린 괄호라면 무조건 push 한다.
• 닫는 괄호일 때는 스택에서 하나를 꺼내서 현재 괄호와 짝이 맞는지 확인한다.

if '(', '[', '{', '<' 중 하나면
    push()
elif ')', ']', '}', '>' 중 하나면
    열린 괄호 pop()
    if 두 괄호의 쌍이 맞으면
        통과
    else
        오류

 

• 그리고 모든 수식의 글자를 처리한 후, 다음과 같이 스택이 비었는지 확인한다.

if 스택이 비었으면
    정상
else
    오류

 

프로그램 구현

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]
 
def checkBracket(expr) :
    for ch in expr:
        if ch in '([{<':
            push(ch)
        elif ch in ')]}>':
            out = pop()
            if ch == ')' and out == '(':
                pass
            elif ch == ']' and out == '[':
                pass
            elif ch == '}' and out == '{':
                pass
            elif ch == '>' and out == '<':
                pass
            else:
                return False
        else :
            pass
    if isStackEmpty() :
        return True
    else :
        return False
 
SIZE = 100
stack = [ None for _ in range(SIZE) ]
top = -1
 
if __name__ == "__main__" :
 
    exprAry = ['(A+B)', ')A+B(', '((A+B)-C', '(A+B]', '(<A+{B-C}/[C*D]>)']
 
    for expr in exprAry :
        top = -1
        print(expr, '==>', checkBracket(expr))

(A+B) ==> True
스택이 비었습니다.
)A+B( ==> False
((A+B)-C ==> False
(A+B] ==> False
(<A+{B-C}/[C*D]>) ==> True