파이썬으로 스택, 큐, 덱 구현

파이썬으로 스택 구현하기 (by 리스트)

class Stack :
    def __init__(self) :
        self.items = []
    
    def push(self, item) :
        self.items.append(item)

    def pop(self) :
        if not self.isEmpty() :
            return self.items.pop()
        else :
            print("Stack underflow")
            exit()
    
    def peek(self) :
        return self.items[-1]

    def isEmpty(self) :
        return not self.items

    def size(self) :
        return len(self.items)
    
    def clear(self) :
        self.items = []

 

---

파이썬으로 큐 구현하기 (by 리스트)

class Queue :
    def __init__(self) :
        self.items = []
    
    def push(self, item) :
        self.items.append(item)

    def pop(self) :
        if not self.isEmpty() :
            object = self.items[0]
            self.items = self.items[1:]
            return object
        else :
            print("Que underflow")
            exit()
    
    def front(self) :
        if not self.isEmpty() :
            return self.items[0]
        else :
            print("Que underflow")
            exit()
    
    def back(self) :
        if not self.isEmpty() :
            return self.items[-1]
        else :
            print("Que underflow")
            exit()

    def isEmpty(self) :
        return not self.items

    def size(self) :
        return len(self.items)
    
    def clear(self) :
        self.items = []

 

---

파이썬으로 덱 구현하기 (by deque 클래스)

파이썬에는 collections라는 모듈에 deque라는 클래스가 이미 존재하기 때문에 이를 활용하면 된다. from collections import deque를 코드 맨 처음에 넣어주면 된다. deque의 메서드는 다음과 같다. 

 

deque.append(item) : 오른쪽 끝에 새로운 원소를 삽입한다.
deque.appendleft(item) : 왼쪽 끝에 새로운 원소를 삽입한다.
deque.pop() : 오른쪽 끝의 원소를 제거 후 반환한다.
deque.popleft() : 왼쪽 끝의 원소를 제거 후 반환한다.
deque.extend(array) : 주어진 array 배열을 순환하며 오른쪽에 추가한다.
deque.extendleft(array) : 주어진 array 배열을 순환하며 왼쪽에 추가한다.
deque.insert(n, item) : n번 index에 원소를 추가한다.
deque.remove(item) : 입력한 원소를 삭제한다. 같은 원소가 있을 경우 왼쪽부터 삭제된다.
deque.rotate(n) : n만큼의 원소의 위치를 회전한다. (양수: 시계방향, 음수: 반시계방향)
deque.clear() : 모든 원소를 제거한다.
deque.reverse() : 원소의 위치를 좌우 반전시킨다.

 

참고로 duque은 list처럼 사용도 가능하다고 한다. 하지만 list보다 훨씬 효율적으로 작동한다. list의 시간복잡도는 O(n)인데 deque의 시간복잡도는 O(1)이라고 한다. list에서 맨앞 원소를 제거하려면 원소를 제거하고 나머지 원소들을 한칸씩 옮겨야 하기 때문에 그런 것 같다. 

 

---

 

[출처 및 참고]

https://gorokke.tistory.com/129

https://wikidocs.net/192069

https://somjang.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack

https://somjang.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90-Queue

https://cocobi.tistory.com/202