스택 구현과 deque

스택이란?

 

데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식입니다. PUSH로 데이터를 스택에 넣고, POP을 통해 데이터를 스택에서 꺼냅니다. 

 

스택 구현하기

 

1. 스택 초기화

스택 배열 stk는 푸시한 데이터를 저장하는 스택 본체인 리스트형 배열입니다. 인덱스가 0인 원소를 스택의 바닥이라고 하며, 데이터가 스택에 추가되는 PUSH 작업이 수행되면 stk[0]에 저장됩니다.

 

그렇다면 고정 길이의 스택 stk 배열을 구현할 때 어떤 인자를 전달해야할까요? 

바로 스택의 최대 크기를 나타내는 capacity와 현재 스택에 쌓여 있는 데이터의 개수를 나타내는 stack pointer입니다. 

그렇다면 고정길이 스택 클래스인 FixedStack의 init 메서드를 구현해보겠습니다.

# FixedStack Class
	# 스택 초기화
    def __init__(self, capacity: int = 256) -> None:
    	self.stk = [None] * capacity
        self.capacity = capacity
        self.ptr = 0

 

2. push() 함수

push() 함수는 스택에 데이터를 추가합니다. 하지만 스택이 가득 차서 더 이상 푸시를 할 수 없는 경우(ptr == capacity)에는 FixedStack.Full을 통해 예외 처리를 내보냅니다. 

 

스택이 가득 차지 않은 경우, 전달 받은 value를 원소 stk[ptr]에 저장하고 ptr += 1을 수행합니다.

def push(self, value: Any) -> None:
    if self.ptr >= self.capacity:
    	raise FixedStack.Full
    self.stk[self.ptr] = value
    self.ptr += 1

 

3. pop() 함수

pop() 함수는 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환합니다. 그러나 스택이 비어서 pop할 수 없는 경우 FixedStack.Empty를 통해 예외 처리를 내보냅니다.

 

스택이 비어 있지 않은 경우, 스택의 ptr - 1의 인덱스의 값을 반환합니다.

def pop(self) -> Any:
    if self.ptr = 0:
    	raise FixedStack.Empty
    self.ptr -= 1
    return self.stk[self.ptr]

 

4. 스택의 꼭대기 데이터를 확인하는 peek() 함수

peek() 함수는 스택의 꼭대기 데이터를 들여다봅니다. 그러나 스택이 비어있는 경우 FixedStack.Empty를 통해 예외 처리를 내보냅니다. 비어있지 않다면 peek으로 확인만 하는 것입니다.

def peek(self) -> Any:
    if self.ptr = 0:
    	raise FixedStack.Empty
    return self.stk[self.ptr - 1]

 

5. 스택의 모든 데이터를 삭제하는 clear() 함수

스택을 비우는 함수입니다. 스택에 쌓여있는 모든 데이터를 삭제하는 것입니다. 이때 스택 포인터 ptr을 0으로 하면 끝납니다. 스택의 배열 원소를 일일이 변경할 필요가 없습니다. 스택에서 push(), pop() 등 모든 작업은 ptr을 바탕으로 이루어지기 때문입니다.

def clear(self) -> None:
    self.ptr = 0

 

6. 데이터를 검색하는 find() 함수

find() 함수는 스택 배열 stk 안에 인자로 넣을 value라는 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열의 어디에 들어있는지를 검색합니다. 배열의 맨 꼭대기인 ptr - 1에서부터 순차적으로 -1씩 선형 검색을 수행합니다.

def find(self, value: Any):
    for i in range(self.ptr - 1, -1, -1):
    	if self.stk[i] == value:
        return i
    return -1

 

7.  데이터의 개수를 세는 count() 함수

count() 함수는 스택에 쌓여 있는 특정 value 데이터의 개수를 반환합니다.

def count(self, value: Any) -> int:
    c = 0
    for i in range(self.ptr):
    	if self.stk[i] == value:
        	c += 1
    return c

 

collections.deque로 스택 구현하기

 

collections의 deque 모듈을 사용하면 스택을 간단하게 구현할 수 있습니다. collection.deque는 맨 앞과 맨 끝 양쪽에서 원소를 추가·삭제하는 자료구조인 deque(덱)을 구현하는 컨테이너입니다.

 

deque에서 양쪽 끝(맨 앞, 맨 끝)의 데이터를 인덱스로 접근하는 것은 O(1)로 빠르지만, 가운데 부분의 데이터를 접근한느 것은 O(n)으로 느립니다. 그러므로 인덱스를 사용하여 임의의 원소를 무작위로 접근하는 것은 효율적이지 않습니다. 

 

다음은 deque에서 사용하는 함수입니다.