[Algorithm] 스택(Stack)

TOC

• 스택(Stack)
• 스택의 연산
  • 스택 push 알고리즘
  • 스택 pop 알고리즘
• 스택 구현 고려 사항
• 스택의 응용
  • 괄호 검사
  • function call

스택(Stack)

• 물건을 쌓아 올리듯 자료를 쌓아올린 형태의 자료구조

• 선형 구조를 갖는다.

  • 선형구조 : 자료간의 관계가 1:1
  • 비선형구조 : 자료간의 관계가 1:N(ex. 트리)

• 자료를 삽입하거나 꺼낼 수 있다.

• 후입선출(LIFO; Last-In-First-Out)

스택의 연산

• 배열 사용 가능

• 저장소 자체를 스택이라고도 한다.

• 마지막 삽입된 원소의 위치 : top

• push : 스택에 자료 저장(삽입)

• pop : 스택의 자료 꺼냄(삭제)

• peek : top에 있는 item 반환

  • pop은 반환 후 삭제, peek은 반환만!

• isEmpty : 스택 비었는지 확인

스택 push 알고리즘

append 메소드를 통해 리스트의 마지막에 데이터 삽입

def push(item):
    s.append(item)

append()은 파이썬에서 상당히 느린 메서드이다. 왜냐하면 메모리 공간에서 배열의 뒤에 다른 데이터들이 있으면 배열을 더 확장할 수 없어서, 삽입해준 데이터를 수용할 공간을 확보하기 위해 다른 공간에 또다른 배열을 만들기 때문이다. 이 과정에서 불필요한 시간이 발생한다. 때문에 stack을 정의할 때 크기를 같이 결정하여 미리 필요한 배열의 크기를 확보한다.

참고❗ 파이썬 창시자 귀도 반 로섬은 기존에 존재하는 append와 동일한 기능을 가진 다른 이름의 pop을 추가하는 것을 긍정적으로 생각하지 않는다고 한다. 그리고 맨 마지막에 넣고 빼는 것은 append()와 pop() 메서드의 퍼포먼스도 느리지 않다는 교수님의 다른 견해도 있다.

그래도 다른 방식으로 stack의 push를 아래와 같이 표현해보자.

def push(item, size):
    global top
    top += 1
    if top==size:
        print('overflow!')  # 디버깅용
    else:
        stack[top] = item

size = 10
stack = [0]*size
top = -1

push(10, size)
top += 1
stack[top] = 20

스택 pop 알고리즘

def pop():
    if len(s) == 0:
        return  #underflow
    else:
        return s.pop()

pop()은 파이썬에서 상당히 느린 메서드이기 때문에 아래와 같이 표현해보자.

def pop():
    global top
    if top == -1:
        print('underflow!')
        return 0
    else:
        top -= 1
        return stack[top+1]

print(pop())

또는 아래와 같은 방법도 사용할 수 있다.

def pop():
    global top
    if top > -1:
        top -= 1
        print(stack[top])

스택 구현 고려 사항

• 장점 : 구현이 용이

• 단점 : 스택의 크기 변경 어렵다.

• 해결방안 : 저장소를 동적으로 할당하여 스택 구현!!

동적 연결리스트(linked list)

• 단점 : 구현이 복잡
• 장점 : 메모리를 효율적으로 사용

스택의 응용

괄호 검사

괄호 조건

• 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 한다.
• 같은 괄호에서 왼쪽 괄호는 오른쪽 괄호보다 먼저 나와야 한다.
• 괄호 사이에는 포함 관계만 존재한다.

알고리즘

• 문자열에 있는 괄호를 차례대로 조사

• 왼쪽 괄호 만나면 : 스택에 삽입

• 오른쪽 괄호 만나면 : 스택에서 top 괄호 pop & 오른쪽 괄호와 일치하는지 확인

• 스택이 비어있거나 괄호의 짝이 맞지 않으면 오류

• 마지막 괄호까지 조사 후 스택에 괄호가 남아있으면 오류

function call

• 프로그램에서의 함수 호출과 복귀에 따른 수행 순서 관리
• 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하기 때문

함수 호출 발생

• 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보 확인
• 이를 스택 프레임(stack frame)에 저장
• 이를 시스템 스택에 삽입

함수 실행 종료

• 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)
• 프레임에 저장되어 있던 복귀주소를 확인 후 복귀

전체 수행 및 종료

• 함수 호출과 복귀에 따라 이 과정을 반복
• 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택