스택의 일반 구현과 응용

 1  데이터 삽입 과정

스택에서 데이터를 삽입하는 함수를 만들어 손쉽게 삽입할 수 있다.

하지만 데이터를 삽입할 때 스택이 이미 꽉 찼는지 확인해야 하는데 스택이 다 찼다면 더는 삽입하지 말아야 한다.

스택이 꽉 찼는지 확인하는 방법은 top 값이 스택 크기 -1과 같다면 스택이 꽉 찬 상태이다.

## 스택이 꽉 찼는지 확인하는 함수 ##
def isStackFull() :
    global SIZE, stack, top
    if (top >= SIZE - 1) :
        return True
    else :
        return False
    
SIZE = 5
stack = ['커피', '녹차', '꿀물', '콜라', '환타']
top = 4

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

 

스택에 데이터를 삽입할 여유 공간이 있다는 것을 확인했다면 스택에 데이터를 삽입하자

 ## 스택에 데이터를 삽입하는 함수 ##
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("게토레이")

데이터를 삽입하는 원리와 과정은 간단 구현에서 했던 것과 같다.

 

 2  데이터 추출 과정

스택에서 데이터를 추출하는 함수를 만들어 효율적으로 추출할 수 있도록 한다.

이것도 마찬가지로 데이터를 추출하기 전엔 먼저 스택에 데이터가 있는지 확인해야 한다.

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() )

 

스택에 추출할 데이터가 있다는 것을 알았다면 데이터를 추출한다.

## 스택에서 데이터를 추출하는 함수 ##
def isStackEmpty() :
    global SIZE, stack, top
    if (top == -1) :
        return True
    else :
        return False
    
def pop() :
    global SIZE, stack, top
    if(isStackEmpty()) :
        print("스택이 비었습니다.")
        return True
    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()

 

위 코드에서 isStackEmpty() 함수를 없애고, pop() 함수만으로 구현해 보았다.

def pop() :
    global SIZE, stack, top
    if(top == -1) :
        print("스택이 비었습니다.")
        return True
    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()

 

 3  데이터 확인

데이터를 삭제하지 않고 해당 데이터만 확인하고 스택에 그대로 두는 것을 peek라고 한다.

top위치의 데이터만 확인하고 값 변경 없이 그대로 두는 것이다.

## 스택에서 데이터를 확인하는 함수 ##
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)

 

 4  스택 완성

앞서 작정한 걸 모두 합쳐 코드를 만든다.

## 스택 통합 코드 ##
## 함수 선언 부분 ##
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 True
    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  스택의 응용

웹 브라우저 왼쪽 위에 있는 이전 페이지 버튼을 스택으로 구현해보자

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()) :
        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("방문 종료")

 

괄호가 여러 개 사용된 수식에서 짝이 올바른지 스택으로 확인해보자.

여는 괄호를 만나면 push하고 닫는 괄호를 만나면 pop 한다는 규칙을 적용한다.

그럼 최종적으로 마지막엔 스택이 비어 있어야 한다.

## 힘수 선언 부분 ##
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()) :
        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))