스택과 큐 - Python 3

개요

C에 이어 Python 3으로도 스택과 큐를 작성해 보았습니다. 사실 Python 3에서 내장형으로 제공하는 리스트는 강력한 기능으로 무장하고 있어 스택과 큐를 완전히 대체 가능합니다. 다만, 자료구조에 대한 이해 차원에서 간단한 구현 한 번 쯤은 해 볼 만하다고 생각했습니다.

일부 생략된 내용이 있을 수 있으므로 이전 게시글과 함께 읽으실 것을 권해드립니다.

• 스택 (Stack) - C
• 큐 (Queue) - C
• 동적 스택과 큐 - C

스택

C와의 차이점

스택의 최상위 인덱스를 나타내는 Top 변수가 삭제되었습니다.
Python 3에서 인덱스 i를 통해 리스트 List에 접근할 때, 음수를 사용할 수 있습니다. 이 때 인덱스 i는 len(List) + i로 치환됩니다. 따라서 인덱스가 -1일 경우, len(list) - 1이 되어 리스트의 끝에 위치한 원소를 참조하게 됩니다. Top 변수가 필요 없어지는 이유입니다.

>>> nums = [1, 2, 3]
>>> nums[-1]
3
>>> nums[-2]
2

Pop을 구현할 필요가 없습니다.
리스트 클래스에는 pop([i]) 메소드가 이미 구현되어 있습니다. 이 메소드는 인덱스 [i]에 해당하는 원소를 Pop합니다. 인덱스 [i] 는 생략 가능하며, 이 경우 기본값인 -1로 설정되어 자동으로 리스트의 끝에 위치한 원소를 Pop하게 됩니다.

>>> nums = [1, 2, 3, 4, 5]
>>> nums.pop() # nums.pop(-1)과 같음
5
>>> nums
[1, 2, 3, 4]
>>> nums.pop(2)
3
>>> nums
[1, 2, 4]

스택 크기에 제한이 없습니다.
C로 구현된 CPython에서 리스트는 동적 배열입니다. 공간이 부족할 경우 배열 크기를 확장하여 재할당합니다. 동적 스택과 큐 - C 게시물에서의 확장 원리와 동일합니다. 스택이 가득 찰 걱정은 덜어두고 마음껏 Push하면 됩니다.

구현

class Stack:
    Arr = []

    def IsEmpty(self):
        return True if len(self.Arr) == 0 else False

    def Pop(self):
        return self.Arr.pop() if self.IsEmpty() is False else None

    def Push(self, Input):
        self.Arr.append(Input)

    def Peek(self):
        return self.Arr[-1] if self.IsEmpty() is False else None

    def HowMany(self):
        return len(self.Arr)

큐

C와의 차이점

Front와 Rear 변수가 삭제되었습니다.
스택을 설명하면서 pop([i]) 메소드는 인덱스를 입력으로 받을 수 있다고 했습니다. Front의 경우 0을, Rear의 경우 -1(또는 인자 없이)을 인덱스로 설정해 Pop하면 됩니다.

큐 크기에 제한이 없습니다.
큐 역시 스택처럼 리스트를 활용해 구현했습니다. 따라서 크기에 제한이 없는 것도 똑같습니다.

구현

class Basic:
    Arr = []

    def IsEmpty(self):
        return True if len(self.Arr) == 0 else False

    def Size(self):
        return len(self.Arr)

    def Push(self, N):
        self.Arr.append(N)

    def Front(self):
        return self.Arr[0] if self.IsEmpty() == 0 else None

    def Back(self):
        return self.Arr[-1] if self.IsEmpty() == 0 else None

    def Pop(self):
        return self.Arr.pop(0) if self.IsEmpty() == 0 else None