자료구조 #1 Stack

Stack 자료구조의 개념

---

1. Stack 의 특성

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

• 스택에 저장된 자료는 선형구조를 가진다

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

• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다

• 마지막에 삽입한 자료를 가장 먼저 꺼냄

• 후입선출 (LIFO, Last-In-Last_Out) 이라고 부름

  
  

2. Stack 의 구현

자료구조

• 자료를 선형으로 저장할 저장소가 필요하다

• 파이썬에서는 리스트를 사용할 수 있다

• 저장소 자체를 스택이라 부르기도 한다

• 마지막에 삽입된 원소의 위치를 top 이라 부름

연산

• 삽입
    저장소에 자료를 저장하고 보통 push 라고 부른다

• 삭제
    저장소에서 자료를 꺼낸다
    꺼낸 자료는 삽입한 자료의 역순으로 꺼낸다
    보통 pop 이라고 부른다

• isEmpty
    스택이 공백인지 아닌지를 확인하는 연산

• peek
    스택의 top 에 있는 item 을 반환하는 연산

3. Stack 의 연산

삽입 / 삭제 연산 과정

빈 스택에 원소 A, B, C 를 차례로 삽입 후 한 번 삭제하는 연산 과정

push 알고리즘

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

pop 알고리즘

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

구현하기

• 스택을 구현하기

• 구현한 스택을 이용하여 3개의 데이터를 스택에 저장하고 다시 3번 꺼내서 출력하기

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

def pop() :
    if len(s) == 0 :
        # underflow
        print("stack is empty")
        return
    else :
        return s.pop(-1)

s = []
push(1)
push(2)
push(3)

print("pop item =>", pop())
print("pop item =>", pop())
print("pop item =>", pop())

스택 구현 고려사항

• 리스트를 사용하여 스택을 구현하는 경우

  • 장점 : 구현이 용이하다는 장점

  • 단점 : 리스트의 크기를 변경하는 작업은 내부적으로 큰 overhead 발생 작업으로 많은 시간이 소요된다

  • 해결방법
      리스트의 크기가 변동되지 않도록 배열처럼 크기를 정해놓고 사용하는 방법
      동적 연결리스트를 이용하여 저장소를 동적으로 할당하여 스택을 구현하는 방법

4. Stack 의 응용

괄호 검사

조건

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

알고리즘

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

  • 2-1 왼쪽 괄호를 만나면 스택에 삽입

  • 2-2 오른쪽 괄호를 만나면 스택에서 top 괄호를 삭제한 후 오른쪽 괄호와 짝이 맞는지 확인

    • 3-1 스택이 비어있음 : 조건 1 또는 조건 2에 위배
    • 3-2 괄호의 짝이 맞지 않음 : 조건 3에 위배
    • 3-3 문자열 끝까지 조사한 후에도 스택에 괄호가 남아있음 : 조건 1에 위배

Function call

함수 호출 관리

프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리

• 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조 이므로,
  후입선출 구조의 스택을 이용하여 수행순서 관리

• 함수 호출이 발생하면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입

• 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)을 삭제(pop) 하면서
  프레임에 저장되어있던 복귀주소를 확인하고 복귀

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

함수 호출 수행 순서

재귀 호출

• 자기 자신을 호출하여 순환 수행되는 것

• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성 할수 있다

• 디버깅이 어렵고 잘못 작성하게 되면 수행 시간이 많이 소요된다

factorial

• n에 대한 factorial :
    1부터 n까지의 모든 자연수를 곱하여 구하는 연산

• n! = n x (n-1)!
  (n-1)! = (n-1) x (n-2)!
  (n-2)! = (n-2) x (n-3)!
  ...
  2! = 2 x 1!
  1! = 1

• 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 작업을 반복

• factorial 함수에서 n = 4 인 경우의 실행

• 

• def factorial(n) :  
    if n == 1 :
        return 1
    return n * factorial(n-1) 

•