제모옥은 스택과 큐로 하겠습니다 근데 이제 연결 리스트를 곁들인

https://koreanraichu.tistory.com/798

스택과 큐를 구현해보자

여기서 간단하게 스택과 큐를 구현해봤는데, 이걸 연결 리스트로도 한번 구현해보자.

 

제목이 익숙하다고요? 록셰프 맞음... 요즘 냉부에 안나오시는데 돌아와요 록셰프... 어록 남겨줘요...

---

스택

기본 골자는 다들 아시죠? 아이 이전 글 읽었으면 알 수 있어... 거기에 다 있어... 

 

# 노드
class Node:
    def __init__ (self, _value):
        # 값
        self.value = _value
        # 내 밑에
        self.prevnode = None

이거 큐도 비슷한데, 스택이나 큐에 들어갈 노드와 스택, 큐를 생성하는 클래스가 다르다.

 

# 누가 맨 위냐
def __init__ (self): 
    self.topnode = None
    # 스택의 크기 
    self.stacksize = 0

init도 뭐 없다. 그냥 다른 메소드 봅시다.

 

# 스택에 접시를 쌓는다 
def push(self, _value):
    # 제가 바로 새 노드입니다
    new_node = Node(_value)
    # 장바구니에 넣어보자 
    new_node.prevnode = self.topnode
    self.topnode = new_node

    # 스택 크기 + 1
    self.stacksize += 1

# 쌓여있던 접시를 꺼낸다 
def pop(self): 
    # 스택이 비었나 확인 
    if self.stacksize == 0:
        print('비어있어서 뭐 꺼낼 게 없습니다. ')
        return
    # 맨 위에 거기! 나와봐요! 
    else: 
        popped_value = self.topnode.value
        self.topnode = self.topnode.prevnode
        self.stacksize -= 1 # 나갔으니까 사이즈도 줄여줍니다
        return popped_value

위는 푸시(스택에 넣는 것), 아래는 팝(스택에서 빼는 것). 장바구니에 물건을 담는 건 푸시, 빼는 건 팝이다. 연결 리스트에서처럼 포인터가 있는 건 맞는데, 얘는 포인터가 막 그렇게 복잡시럽지는 않다. 그냥 맨 위에 있는 애를 가리키기만 하면 된다.

 

# 다 까봐 
def stack_show(self):
    # 비었음? 
    if self.stacksize == 0:
        print('스택이 비어있습니다. ')
        return 
    # 아니면 줘봐 
    else: 
        # 내용만 보는거지, 빼는 게 아닙니다. 
        temp_node = self.topnode
        # 다음이 비어있지 않다면 빌때까지 출력 
        while temp_node is not None: 
            print(temp_node.value)
            # 다음
            temp_node = temp_node.prevnode
    return

이거는 넣어도 그만, 안 넣어도 그만이긴 한데 스택의 내용을 건드리지 않고 그냥 보기만 하는거다. 그래서 스택의 조회를 위한 임시 포인터가 따로 있다.

 

큐

class Node:
    def __init__(self, _value):
        # 큐값
        self.value = _value
        # 포인터가 가리킬 무언가
        self.nextorder = None

여기도 걍 노드 생성하는거니까 넘어갑시다.

 

def __init__ (self):
    # 포인터 두 개(front, rear)
    self.frontpointer = None
    self.rearpointer = None
    # 큐 크기
    self.queuesize = 0

보니까 얘는 포인터가 두 개 있네? 왜 그렇죠? 큐는 들어오는 건 뒤로 들어오는데 나가는 건 앞으로 나가서 그렇다. 어디 오픈런같은 거 할 때 줄 어디로 서요? 줄 뒤로 가죠. 그럼 어디로 나옵니까? 줄 앞으로요. 프론트 포인터는 나갈 애가 누구인지, 리어 포인터는 들어갈 애가 누군지를 가리킨다.

 

# 인큐
def enqueue(self, _value):
    # 인큐: 줄을 섬 
    new_node = Node(_value) # 커피 주문하는 손님
    # 프론트 포인터가 None->마수걸이(첫 손님)
    if self.frontpointer is None: 
        # 일단 하나까지는 같은 곳을 가리킴
        self.frontpointer = new_node
        self.rearpointer = new_node
    else: 
        # 인큐일때는 리어가 이동합니다 
        self.rearpointer.nextorder = new_node
        self.rearpointer = new_node
    # 사이즈 추가
    self.queuesize += 1
    return

# 디큐
def dequeue(self):
    # 디큐: 커피 나와서 받고 갈 길 감
    # 이거는 값 표시용입니다. 
    dequeue_pointer = self.frontpointer
    # 대기열이 없으면 디큐 못해요 
    if self.queuesize == 0:
        print('큐가 비었습니다!')
        return
    # 큐가 비지 않았다면 디큐를 하면 됨
    else: 
        # 디큐를 할 때는 프론드 포인터가 한칸 이동합니다
        self.frontpointer = self.frontpointer.nextorder
        self.queuesize -= 1
        # 큐가 비면 두 포인터가 다시 None을 가리키게 해 줘야 한다 
        if self.frontpointer is None: 
            self.rearpointer = None
    return dequeue_pointer.value

위에서 큐는 포인터가 두 개라고 했는데, 두 포인터가 각각 움직이는 시점이 다르다. 이 큐를 커피 대기줄이라고 해 보면, 인큐는 커피 주문이 새로 들어온 것이다. 주문이 한개일때까지는 두 포인터가 다른 곳을 가리키지만, 두개 이상이 되면 리어 포인터가 새로 들어오는 주문쪽으로 이동하게 된다. 이 상태에서 누군가가 커피를 받으면 디큐가 되죠? 그러면 프론트 포인터가 다음으로 나갈 주문을 가리킨다. 그러니까 새로 누군가 줄을 서면 리어가, 누군가 주문한 걸 받으면 프론트가 움직인다.

 

# 큐 좀 봅시다
def queue_show(self):
    # 큐 비었으면 비었다고 하고
    if self.queuesize == 0:
        print('큐가 비었습니다! ')
        return
    # 아니면 쫙 보여줘
    else: 
        # 큐 안 건드리고 내용만 볼겁니다. 
        temp_pointer = self.frontpointer
        # 다음이 비어있나요? 
        while temp_pointer is not None:
            print(temp_pointer.value)
            # 오키 넥스트
            temp_pointer = temp_pointer.nextorder
    return temp_pointer

큐 내용에 손대지 않고 전체 큐를 다 보는 메소드. 얘도 임시 포인터가 있다.