[자료구조] 큐, 스택

자료 구조: 데이터를 표현하고 관리하고 처리하기 위한 구조이다.

 그 중 스택과 큐는 자료구조의 기초 개념 ! 

 

 

스택과 큐에서의 핵심 함수는 삽입(Push), 삭제(pop)이며 오버 플로와 언더 플로를 주의해야한다. 

오버 플로: 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 찬 상태에서 삽입 연산 수행

언더 플로: 데이터가 들어 있지 않은 상태에서 삭제 연산 수행

 

 

1. 스택 

first in first out 이다. 박스를 쌓았다가 내리는 상황을 생각하면된다. 

파이썬에서는 스택을 이용할 때 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop()을 이용하면 된다.

 

stack = []
stack.append(5)
stack.append(4)
stack.append(3)
stack.append(2)
stack.pop()
stack.append(1)
stack.pop()

# 최하단 원소부터 출력
print(stack)
#[5,4,3]

# 최상단 원소부터 출력
print(stack[::-1])
#[3,4,5]

 

 

2. 큐

first in first out이다. (놀이동산에서 줄 서기를 생각하면되고, 줄의 입구와 출구가 다른 것이 핵심이다.)

파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. 

deque는 스택과 큐의 장점을 모두 활용한 것인데, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해서 효율적이고, queue 라이브러리를 이용하는 것보다 간단하다.  

 

(대부분의 코테에서 collection 모듈은 사용 가능하다.)

 

from collections import deque

queue = deque()

queue.append(5)
queue.append(4)
queue.append(3)
queue.append(2)
queue.popleft()
queue.append(1)
queue.popleft()

# 먼저 들어온 순서대로 출력
print(queue)
# deque([5,4,3])

# 나중에 들어온 순서대로 출력
queue.reverse()
print(queue)
# deque([3,4,5])

# 리스트 자료형으로 변경
list(queue)

 

3. 우선순위 큐

우선순위 큐는 일반적인 큐와 비슷한 구조를 가지지만 제거될 때 가장 작은 값을 지우게된다. (데이터 추가는 어떤 순서로 해도 상관이 없다.) 내부적으로 데이터를 정렬한 상태로 보관하고있다.

 

from queue import PriorityQueue
queue = PriorityQueue()

#삽입
queue.put(4)
queue.put(1)
queue.put(7)
queue.put(3)

#삭제
print(queue.get()) # 1출력
print(queue.get()) # 3출력

 

 

4. 재귀함수

자기 자신을 다시 호출하는 함수

-> 언제 끝날지 종료 조건을 꼭 명시해야한다.

def recursive_function(i):
	if i==100:
    	return
    recursive_fuction(i+1)
    
recursive_function(1)

 

재귀함수는 내부적으로 스택 자료구조와 동일해서 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. 

대표적인 예시로 팩토리얼 문제가 있다. 반복적으로 구현한 방식과 재귀적으로 구현한 방식을 비교해보자.

 

# 반복으로 구현
def factorial_iterative(n):
    result = 1
    for i in range(1,n+1):
        result *= i
    return result

# 재귀로 구현 
def factorial_recursive(n):
    if n<=1:
        return 1
    return n*factorial_recursive(n-1)

print("반복으로 구현:", factorial_iterative(5))
print("재귀로 구현", factorial_recursive(5))

 

재귀의 장점은? 

점화식을 쓸 수 있어 간결하다. (점화식이란 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.)

 

팩토리얼의 점화식

n이 0혹은 1일 때:  factorial(n)=1

n이 1보다 클 때: factorial(n) = n X factorial(n-1)

 

점화식이 재귀함수의 소스 코드와 점화식이 매우 닮아있다. 다시 말해 재귀함수는 반복문을 이용하는 것과 비교했을 때 더욱 간결한 형태이다.