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

  • 선형 구조를 갖는다.

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

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

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


  • 배열 사용 가능

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

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

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

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

  • peek : top에 있는 item 반환

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

  • isEmpty : 스택 비었는지 확인


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

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 & 오른쪽 괄호와 일치하는지 확인

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

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


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

함수 호출 발생

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

함수 실행 종료

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

전체 수행 및 종료

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