Python3 Data Structure 2-1

지난 포스팅에서 built-in data structure를 알아보았고, 이번 포스팅에서는 추상 데이터 타입(Abstarct data type)으로 분류되는 자료구조에 대해 포스팅할 것이다.

Stack(스택)

Definition

Stack은 배열의 끝에서만 데이터에 접근할 수 있는 선형 자료구조를 뜻한다.
인덱스 접근이 제한되며 후입선출(LIFO, Last-In & First-Out) 구조이다.
파이썬에서 자체적으로 Stack module을 제공해주지 않기 때문에 외부 모듈을 다운받아 사용하거나, 제차적으로 class만들 수도 있고, list의 내장 method를 사용해 구현할 수 있다.

Method

1. push
2. pop
3. peek(또는 top)
4. empty
5. size

Stack은 위 다섯가지의 동작(method)들을 가지고 있으며 시간복잡도는 다섯개 모두 O(1)이다.

1. push

push는 stack 맨 끝에 item(항목)을 삽입한다.

class Stack:
    
    def push(self, value):
        self.items.append(value)

2. pop

pop은 stack 맨 끝의 항목(item)을 반환(return)하며 동시에 stack에서 제거한다.

class Stack:
    
    def pop(self):
        return self.items.pop()

3. peek

peek는 맨 끝의 항목을 조회한다는 점에서 pop과는 차이점이 있다.

class Stack:
    
    def peek(self):
        if self.is_empty():
            return print("Empty Stack")
        else:
            return self.items[-1]

4. empty

empty는 stack이 비어있는지 조회하는 method로 boolean값(Ture/False)을 반환한다.

class Stack:

    def is_empty(self):  # restful convention에 맞춰 동사(verb)형태로 작성한다.
        return not bool(self.items)

5. size

size는 스택의 크기(항목의 갯수)를 확인한다.

class Stack():

    
    def size(self):
        return len(self.items)

Code

모든 코드를 하나로 합쳐보면 다음과 같다.

class Stack:
    
    def __init__(self) -> None:
        self.items = []
    
    def size(self) -> int:
        return len(self.items)
    
    def is_empty(self) -> bool:
        return not bool(self.items)
    
    def push(self, value) -> None:
        self.items.append(value)
    
    def pop(self):
        if self.is_empty():
            print("Empty Stack")
        else:
            return self.items.pop()
    
    def peek(self):
        if self.is_empty():
            return print("Empty Stack")
        else:
            return self.items[-1]
    
    def __repr__(self):
        return repr(self.items)

스택은 깊이 우선 탐색(DFS)에서 사용된다.

큐

Definition

Queue는 Stack과 다르게 선입 선출(FIFO, First-In & First-Out)구조로 배열에 들어온 순서대로 접근하는 선형 자료구조를 뜻한다. 그리고 Stack과 다르게 python에서 제공해주는 Queue module이 있다.
Queue와 Stack의 공통점은 인덱스 접근이 제한되는 것이다.

from queue import Queue
queue = Queue()

Method

1. enqueue
2. dequeue
3. peek(또는 front)
4. empty
5. size

Queue method 중 enqueue는 list의 insert method를 사용해 구현해 시간복잡도가 O(n)이라는 단점이 있다. 하지만 Queue module을 사용할 경우 이러한 단점이 없어지게 된다.

1. enqueue

enqueue는 queue 맨 끝에 item을 삽입한다.
python queue 모듈에서는 append method를 사용하지만 dequeue 방법의 차이가 있다.

class Queue:
    
    def enqueue(self, item) -> None:
        self.items.insert(0, item)

2. dequeue

dequeue는 queue 맨 앞의 item을 반환하고 제거한다.

class Queue:

    def dequeue(self):
        if self.is_empty():
            return self.items.pop()
        else:
            print("Empty Queue")

3. peek

peek는 stack과 동일하게 queue 맨 앞의 항목을 조회한다.

class Queue:

    def peek(self):
        if self.is_empty():
            return self.items[-1]
        else:
            print("Empty Queue")

4. empty

empty는 stack과 동일하게 queue가 비어있는지 조회하는 method로 boolean값(Ture/False)을 반환한다.

class Queue:

    def is_empty(self):
        return not bool(self.items)

5. size

size는 stack과 동일하게 queue의 크기(항목의 갯수)를 확인한다.

class Queue:

    def size(self):
        return len(self.items)

CODE

모든 코드를 하나로 합치면 다음과 같다.

class Queue:
    
    def __init__(self) -> None:
        self.items = []
    
    def is_empty(self):
        return not bool(self.items)
    
    def enqueue(self, item) -> None:
        self.items.insert(0, item)
    
    def dequeue(self):
        if self.is_empty():
            print("Empty Queue")
        else:
            return self.items.pop()
    
    def peek(self):
        if self.is_empty():
            print("Empty Queue")
        else:
            return self.items[-1]
    
    def size(self) -> int:
        return len(self.items)
    
    def __repr__(self) -> str:
        return repr(self.items)

큐는 너비 우선 탐색(BFS)에서 사용된다.