[자료구조] : 스택(Stack) & 재귀함수(recursive function) 동작방법

스택(Stack)
-  데이터를제한적으로 접근할 수 있는 구조
    → 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
    → LIFO & FILO(Last-In, First-Out & First-In, Last-Out) 데이터 관리 방식을 따른다.
        ▶ LIFO : 마지막에 넣은 데이터를 먼저 추출
        ▶ FILO : 처음에 넣은 데이터를 먼저 추출
    → 대표적인 스택의 활용
        ▶ 컴퓨터 내부 프로세스 구조의 함수 동작 방식

- 장단점
→ 장점 :
        ▶ 구조가 단순하여 구현이 쉽다.
        ▶ 데이터 저장/읽기 속도가 빠르다.
→ 단점 :
        ▶ 데이터 최대 갯수를 미리 정해야 한다.
             파이썬의 경우 재귀 함수는 1000번까지만 호출 가능
        ▶ 저장 공간의 낭비가 발생할 수 있다.
             미리 사용할 최대 갯수만큼 저장 공간을 확보해야 한다

-  용어
    → push() : 스텍에 데이터를 넣는 기능
    → pop() : 스텍에서 데이터를 꺼내는 기능

 

push() : 
스택에 데이터가 들어갈 때

pop() : 
스택에서 데이터가 나갈 때

 

 

---

Python 구현

class stack:
    def __init__(self):
        """
        --Stack을 리스트로 구현--
        비어있는 리스트 생성
        """
        self.list_ = []
        
    def push(self, data):
        """
        --Stack에 data를 넣는 기능--
        data : 넣을 값 입력
        """
        self.list_.append(data)
        
    def pop(self):
        """
        --Stack에 data를 꺼내는 기능--
        마지막에 들어온 값 바인딩 및 리스트에서 삭제
        """
        self.get = self.list_[-1]
        del self.list_[-1]
        return self.get
    
    def top(self):
        """
        --Stack의 가장 윗 데이터를 반환--
        Stack이 비어있다면 사용 불가능
        """
        self.get = self.list_[-1]
        return self.get
    
    def empty(self):
        """
        --Stack이 비어있는지 확인--
        비어있다면 1, 그렇지 않다면 0
        """
        if len(self.list_) == 0  :
            return 1
        else:
            return 0

 

# stack 생성
data = stack()

 

→ empty()를 사용하여 생성된 Stack이 비어있는지 확인

# 생성된 stack이 비어있는지 확인
data.empty()

1

 

→ push()을 사용하여 생성된 Stack에 데이터 넣기

# 생성된 stack에 데이터 입력
for i in range(10):
    data.push(i)

 

→ empty()를 사용하여 생성된 Stack이 비어있는지 확인

# 생성된 stack이 비어있는지 확인
data.empty()

0

 

→ top()를 사용하여 생성된 Stack의 맨위에 있는 데이터 확인

# top()를 사용하여 stack 맨 위 데이터 확인
data.top()

9

 

→ pop()를 사용하여 생성된 Stack안의 데이터 꺼내기

# stack에 입력된 데이터 꺼내기
data.pop()

9

---

생략

---

→ pop()를 사용하여 생성된 Stack안의 데이터 꺼내기

# stack에 입력된 데이터 꺼내기
data.pop()

0

 

 

---

재귀함수(recursive function)
- 선언한 함수에서 자신을 다시 호출하여 작업을 수행하는 방식
    → return 조건을 잘 정의해야 한다.

- 참고
    → 하늘색 배경 : 스텍에 넣어진 데이터
    →     흰색 배경 : 실행된 코드

 

Python 구현

def recursive(n):
    if n == 0:
    	return
    else:
    	recursive(n-1)
        print(n)

 

recursive(4)

1
2
3
4

 

 

---

재귀함수 동작
return을 만나기 까지 

재귀함수 동작
return 이후

 

 

---

코드로 보는 재귀 함수

 

함수 선언 

def recursive(n):
    if n == 0:
    	return
    else:
    	recursive(n-1)
        print(n)

 

함수에 4를 입력

recursive(4)

 

- 함수 내부

def recursive(n):  # n = 4
    if n == 0:  # (1) 4는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (2) else구문
        recursive(n-1)  # (3) 4-1 = 3, 함수에 3을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 4인 값이 스택(Stack)에 쌓인다.'''

 

- 스택(Stack) 내부

#--------------------------------------Stack--------------------------------------#

def recursive(n):  # n = 4
    if n == 0:  # (1) 4는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (2) else구문
        recursive(n-1)  # (3) 4-1 = 3, 함수에 3을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 4인 값이 스택(Stack)에 쌓인다.'''

 

함수내부에서 함수에 3을 입력

def recursive(n):  # n = 3
    if n == 0:  # (4) 3은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (5) else구문
        recursive(n-1)  # (6) 3-1 = 2, 함수에 2를 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 3인 값이 스택(Stack)에 쌓인다.'''

 

- 스택(Stack) 내부

#--------------------------------------Stack--------------------------------------#

def recursive(n):  # n = 3
    if n == 0:  # (4) 3은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (5) else구문
        recursive(n-1)  # (6) 3-1 = 2, 함수에 2를 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 3인 값이 스택(Stack)에 쌓인다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 4
    if n == 0:  # (1) 4는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (2) else구문
        recursive(n-1)  # (3) 4-1 = 3, 함수에 3을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 4인 값이 스택(Stack)에 쌓인다.'''

 

함수내부에서 함수에 2를 입력

def recursive(n):  # n = 2
    if n == 0:  # (7) 2는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (8) else구문
        recursive(n-1)  # (9) 2-1 = 1, 함수에 1을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 2인 값이 스택(Stack)에 쌓인다.'''

 

- 스택(Stack) 내부

#--------------------------------------Stack--------------------------------------#

def recursive(n):  # n = 2
    if n == 0:  # (7) 2는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (8) else구문
        recursive(n-1)  # (9) 2-1 = 1, 함수에 1을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 2인 값이 스택(Stack)에 쌓인다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 3
    if n == 0:  # (4) 3은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (5) else구문
        recursive(n-1)  # (6) 3-1 = 2, 함수에 2를 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 3인 값이 스택(Stack)에 쌓인다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 4
    if n == 0:  # (1) 4는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (2) else구문
        recursive(n-1)  # (3) 4-1 = 3, 함수에 3을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 4인 값이 스택(Stack)에 쌓인다.'''

 

함수내부에서 함수에 1을 입력

def recursive(n):  # n = 1
    if n == 0:  # (10) 1은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (11) else구문
        recursive(n-1)  # (12) 1-1 = 0, 함수에 0을 입력 (다음 스택에서 작동)
        print(n) '''(...) n = 1인 값이 스택(Stack)에 쌓인다.'''

 

- 스택(Stack) 내부

#--------------------------------------Stack--------------------------------------#

def recursive(n):  # n = 1
    if n == 0:  # (10) 1은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (11) else구문
        recursive(n-1)  # (12) 1-1 = 0, 함수에 0을 입력 (다음 스택에서 작동)
        print(n)   '''(...) n = 1인 값이 스택(Stack)에 쌓인다.'''
        
#---------------------------------------------------------------------------------#        

def recursive(n):  # n = 2
    if n == 0:  # (7) 2는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (8) else구문
        recursive(n-1)  # (9) 2-1 = 1, 함수에 1을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 2인 값이 스택(Stack)에 쌓인다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 3
    if n == 0:  # (4) 3은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (5) else구문
        recursive(n-1)  # (6) 3-1 = 2, 함수에 2를 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 3인 값이 스택(Stack)에 쌓인다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 4
    if n == 0:  # (1) 4는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (2) else구문
        recursive(n-1)  # (3) 4-1 = 3, 함수에 3을 입력 (다음 스택에서 작동)
        print(n)  '''(...) n = 4인 값이 스택(Stack)에 쌓인다.'''

 

함수내부에서 함수에 0을 입력, return 만남

def recursive(n):  # n = 0
    if n == 0:  # (13) 0은 0과 같다.
        return  '''(14) return'''
    else:
        recursive(n-1)
        print(n)

 

스택(Stack)에서 꺼내기

- return이후 재귀가 멈춰짐에 따라 스택에 쌓인 데이터가 꺼내진다.

#--------------------------------------Stack--------------------------------------#

def recursive(n):  # n = 0
    if n == 0:  # (13) 0은 0과 같다.
        return  # (14) return
    else:
        recursive(n-1)
        print(n)
#---------------------------------------------------------------------------------# 

def recursive(n):  # n = 1
    if n == 0:  # (10) 1은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (11) else구문
        recursive(n-1)  # (12) 1-1 = 0, 함수에 0을 입력 (다음 스택에서 작동)
        print(n)  '''(15) n = 1인 값이 스택(Stack)에서 나간다.'''
        
#---------------------------------------------------------------------------------#        

def recursive(n):  # n = 2
    if n == 0:  # (7) 2는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (8) else구문
        recursive(n-1)  # (9) 2-1 = 1, 함수에 1을 입력 (다음 스택에서 작동)
        print(n)  '''(16) n = 2인 값이 스택(Stack)에서 나간다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 3
    if n == 0:  # (4) 3은 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (5) else구문
        recursive(n-1)  # (6) 3-1 = 2, 함수에 2를 입력 (다음 스택에서 작동)
        print(n)  '''(17) n = 3인 값이 스택(Stack)에서 나간다.'''
        
#---------------------------------------------------------------------------------#   

def recursive(n):  # n = 4
    if n == 0:  # (1) 4는 0과 다르기 때문에 else구문으로 이동
        return
    else:  # (2) else구문
        recursive(n-1)  # (3) 4-1 = 3, 함수에 3을 입력 (다음 스택에서 작동)
        print(n)  '''(18) n = 4인 값이 스택(Stack)에서 나간다.'''

1
2
3
4