핵심 자료구조

스택

스택은 대표적인 후입선출 (LIFO) 자료구조입니다.

스택에 값을 넣고 뺄 때는 먼저 들어간 것이 가장 나중에 나옵니다.
그렇기 때문에 그 과정은 상당히 번거롭습니다.

그렇다면 이 번거로운 자료구조인 스택을 사용하는 이유는 무엇일까요?

프로그래밍 언어를 학습하면 변수 선언과 변수가 저장되는 위치인 전역, 힙, 스택 등을 배우게 됩니다.
이때 말하는 스택이란 현재 코드를 실행하는 프로세스 또는 스레드의 메모리 영역입니다.

함수에 지역 변수를 선언하면 바로 이 스택 영역에 변수가 저장됩니다.

또 함수를 호출하면 함수가 실행된 다음 다시 원래 위치로 돌아와야 하는데, 이 돌아올 위치를 저장하는 데도 스택이 필요합니다.
좀 더 쉽게 말하면 방금 실행한 작업을 되돌리는 실행 취소 단축키인 Ctrl + Z와 같다고 볼 수 있습니다.

동작 방식

스택 자료구조는 push pop top size empty 등의 기능을 제공하며 다음과 같은 역할을 합니다.

push

push는 스택에 값을 저장합니다.
이때 가장 최근에 들어간 값이 가장 먼저 나오게 됩니다. (그렇다면 가장 먼저 들어간 값이 가장 늦게 나오겠죠?)

pop

pop은 가장 최근에 저장한 값을 스택에서 제거합니다.

top
스택의 최상위 값을 확인합니다.

size
스택에 들어있는 원소의 개수를 확인합니다.

empty
스택이 비어있는지 여부를 boolean으로 반환합니다.

코드로의 구현

스택은 동작이 간단한 만큼 구현 코드도 간단합니다.

def __init__(self):
	self.data = []
    
def push(self, x):
	self.data.append(x)

def pop(self):
	if not self.data:
    	return -1
    return self.data.pop()

def size(self)
	return len(self.data)

def empty(self)
	if not self.data:
    	return 1
    return 0

def top(self)
	if not self.data
    	return -1
    return self.data[-1]
    

큐

큐는 선입선출 (FIFO) 구조의 자료구조입니다.
먼저 들어온게 먼저 나간다는 지극히 상식적인(?) 자료구조입니다.

동작 방식

큐는 enqueue size dequeue 기능을 제공합니다.

enqueue

큐에 원소를 추가합니다. 이때 스택의 push와 다른점은 추가되는 원소가 맨앞에 위치한다는 점입니다.

size

비어 있는 큐에 원소를 가져오라고 요청하면 null이거나 에러 메시지가 뜨기 때문에 큐가 비어있는지 확인해야 합니다. 그때 사용하는 연산이 size입니다.

dequeue
큐에 원소를 제거합니다.
enqueue를 통해 추가된 원소는 맨 앞에 위치한다고 하였습니다.
dequeue는 맨 뒤의 원소를 제거합니다.
이렇게 기능함으로서 선입선출을 지킬 수 있습니다

이 3개의 기본 연산을 제외하고도 가장 앞에 위치한 원소를 보는 peek, 큐가 비었는지 확인하는 empty도 있지만 위 3가지 연산으로 대부분의 기능을 구현할 수 있습니다.

큐의 종류

큐는 구현 방식에 따라 선입선출을 보장하기 위해 선형 방식으로 큐를 운형하는 원형 큐, 순환 큐가 있고 원소의 개수에 따라 큐의 크기가 달라지는 가변 크기 큐가 있습니다.

가변크기 큐는 보통 연결 리스트로 구현합니다.
우선 원형 큐부터 하나씩 살펴보겠습니다.

---

원형 큐

enqueue를 실행할 때, 기존에 존재하던 값이 한칸씩 이동한다고 하였습니다.
큐가 크면 커질수록 연산하는 시간이 길어지기에(O(N)), 이런 비효율을 제거하기 위해 고안된 것이 바로 원형 큐입니다.

원형 큐에서는 front와 rear라는 포인터 개념이 존재합니다.

front가 가리키는 위치에 값을 추가하고, rear가 가리키고 있는 위치에서 값을 획득(dequeue)합니다.

큐에 원소가 없을 때는 front와 rear 둘 다 첫 번째 위치(인덱스 0의 위치)를 가리키고 있습니다.

즉, front와 rear가 같은 곳을 가리킬 때에는 큐가 빈 상태입니다.

원형큐를 설계할 때의 주의점은 1개의 공간을 버퍼(여분)로 추가 할당해야 합니다.
3개의 원소를 저장하는 원형 큐를 설계하고 싶다면, 큐가 사용할 버퍼의 크기를 3이 아니라 +1을 한 4로 설정해야 합니다.

즉 3개의 원소를 저장해야 할 때에는 버퍼의 크기를 3으로 설정하는 것이 아닌 +1을 한 값인 4로 설정해야 한다는 뜻입니다.

원형 큐에서는 큐가 가득 찼는지를 알려주는 is_full 함수를 정의해야 합니다.

코드로의 구현

class CircularQueue:
	def __init__(self, k: int):
    	self.n = k + 1
        self.data = [0] * self.n
        self.front = 0
        self.rear = 0
        
    def enqueue(self, value: int) -> bool:
    	if self.is_full():
        	return False
            
        self.data[self.front] = value
        self.front = (self.front + 1) % self.n
        return True
        
    def dequeue(self) -> bool:
    	return False
        
        self.rear = (self.rear + 1) % self.n
        return True
        
    def front(self) -> int:
    	if self.is_empty():
    		return -1
        return self.data[self.rear]
    
    def is_empty(self) -> bool:
    	return self.front == self.rear
    
    def is_full(self) -> bool:
    	return (self.front + 1) & self.n == self.rear

[0] * n 이 괴상한(?) 축약형은 리스트 초기화로 리스트 동적 선언하는 방법이라고 합니다.

파이썬에서 리스트의 동적 선언은 다음과 같이 리스트 초기화로 수행할 수 있습니다.

data = [0 for _ in range(n)]

하지만 이 방법은 늘 n번의 루프를 수행해야 하고, 리스트 초기화 표현식을 작성해야 한다는 단점이 있습니다.

따라서 파이썬에서는 다음과 같이 * 연산을 사용해 배열을 동적으로 선언하고 초기화할 수 있습니다.

data = [0] * n

단 여러 객체를 리스트로 선언하면 모두 같은 객체에 대한 레퍼런스임에 주의해야 합니다.

data = [Node()] * 3

data[0].value = 1

// data[1].value, data[2].value 모두 1이 됩니다.

위 구현을 하나씩 뜯어 보겠습니다.

enqueue

def enqueue(self, value: int) -> bool:
	if self.is_full()
    	return False
        
        self.data[self.front] = value
        self.front = (self.front + 1) % self.n
        return True

포인터 front를 찾아 값을 넣어주고, 프론트의 위치를 이동시켜줍니다.