연결 스택과 큐

연결 스택

• 톱에서 노드 삽입/삭제 용이
• top : 스택의 톱 노드를 가리키는 전용 데이터 멤버
• 초기엔 top을 0으로 설정

class ChainNode:
    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedStack:

    def __init__(self):
        self.top = ChainNode(0, None)

    def Push(self, new):
        self.top = ChainNode(new, self.top)

    def Pop(self):
        if self.isEmpty():
            raise Exception('Empty')

        delNode = self.top
        self.top = self.top.next

        del delNode

    def isEmpty(self) :
        if self.top.next is None:
            return True
        else:
            return False

    def PrintAll(self):
        temp = self.top
        while True:
            if temp.next is None:
                print()
                break
            else:
                print(temp.data, end=" ")
            temp = temp.next

    def Top(self):
        return self.top.data

 

연결 큐

• 리어에서 노드 삽입 용이
• 프런트에서 삽입 삭제 용이
• front : 큐의 처음 노드를 가리키는 전용 데이터 멤버
• rear : 큐의 마지막 노드를 가리키는 전용 데이터 멤버
• 초기엔 front와 rear를 0으로 설정

class ChainNode:
    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedQueue:
    def __init__(self):
        self.rear = ChainNode(0, 0)
        self.front = ChainNode(0, self.rear)
        self.chain = 0 # chain 개수 세기 위함

    def isEmpty(self):
        if self.chain == 0:
            return True
        else:
            return False

    def Front(self):
        return self.front.next.data

    def Rear(self):
        return self.rear.data

    def Push(self, new):
        if self.isEmpty():
            self.rear = ChainNode(new, 0)
            self.front.next = self.rear
            self.chain += 1
        else:
            self.rear.next = ChainNode(new, 0)
            self.rear = self.rear.next
            self.chain += 1

    def Pop(self):
        if self.isEmpty():
            raise Exception('Empty')

        delNode = self.front.next
        self.front.next = self.front.next.next

        self.chain -= 1

        del delNode

    def PrintAll(self):
        temp = self.front.next

        while True:
            if temp == self.rear:
                print(temp.data)
                break
            else:
                print(temp.data, end=" ")
            temp = temp.next