덱

덱 (Deque)

스택과 큐를 합친 자료구조로 양쪽 끝에서 자료의 삽입, 삭제가 가능하다.

추상 자료형

create() /* 덱을 생성 */
init(d) /* 덱을 초기화 */
is_empty(d) /* 덱이 공백 상태인지 검사 */
add_front(d, e) /* 덱의 앞에 요소를 추가 */
add_rear(d, e) /* 덱의 뒤에 요소를 추가 */
delete_front(d) /* 덱의 앞에 있는 요소를 반환한 다음 삭제 */
delete_rear(d) /* 덱의 뒤에 있는 요소를 반환한 다음 삭제 */
get_front(d) /* 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환 */
get_rear(d) /* 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환 */

구현

class Node():
    def __init__(self, llink, item, rlink):
        self.item = item
        self.llink = llink # left link
        self.rlink = rlink # right link

class Deque():
    def __init__(self):
        self.front = None
        self.rear = None

    def is_empty(self):
        return self.front == None

    def add_front(self, item):
        new = Node(None, item, self.front)
        if self.is_empty():
            self.rear = new
        else:
             self.front.llink = new
        self.front = new

    def add_rear(self, item):
        new = Node(self.rear, item, None)
        if self.is_empty():
            self.front = new
        else:
             self.rear.rlink = new
        self.rear = new

    def delete_front(self):
        if self.is_empty():
            return -1
        else:
            item = self.front.item
            self.front = self.front.rlink

            if self.front == None:
                self.rear = None
            else:
                self.front.llink = None

            return item

    def delete_rear(self):
        if self.is_empty():
            return -1
        else:
            item = self.rear.item
            self.rear = self.rear.llink

            if self.rear == None:
                self.front = None
            else:
                self.rear.rlink = None

            return item        

    def get_front(self):
        if self.is_empty():
            return -1
        else:
             return self.front.item

    def get_rear(self):
        if self.is_empty():
            return -1
        else:
             return self.rear.item

    def display(self):
        p = self.front # pointer
        while p != None:
            print(p.item, end=' ')
            p = p.rlink

if __name__ == "__main__":
    # create deque
    d = Deque()

    d.add_front(10)
    d.add_front(20)
    d.add_rear(30)
    d.display()

    print('')

    d.delete_front()
    d.delete_rear()
    d.display()

출력

20 10 30
10