스택과 큐를 구현해보자

스택

여러분들 한번씩은 다 그런 경험이 있을 것이다. 다른 사람이랑 장을 보건, 혼자서 장을 보건 집에 오면서 먹을 간식을 하나 사게 되는데, 계산을 마치고 간식을 먹으려고 봤더니 에엥? 간식이 장바구니 맨 밑에 들어가서 안보여요! 장바구니가 일종의 스택 역할을 해서 그런거다.

 

예? 그게 무슨 말이죠? 스택은 먼저 들어간 게 나중에 나온다. 그 간식을 맨 처음으로 장바구니에 넣고 다른 물건들을 넣었다면, 먼저 들어간 간식이 다른 물건에 묻히게 된다. 그렇다고 이동중에 장바구니를 들어낼 수는 없고… 씁. 이럴때는 간식을 따로 빼두자.

 

스택을 만들어보자-상자 만들기

스택은 장바구니, 혹은 상자, 혹은 부페 접시(그 부페가면 접시 쌓여있는)다. 그리고 여기서는 상자를 만들고, 상자 안에 물건을 적재하고, 꺼내고 할 것이다. 그러려면 상자가 있어야겠죠?

 

class stack:
    # 스택(부페 접시 탑)
    def __init__ (self):
        self.items = []

이게 상자다. 혹은 장바구니가 되기도 하고, 부페 접시가 되기도 하는데 아무튼 쌓을 수 있는거면 된다.

 

상자에 물건을 넣고 빼기

# 빈 공간에 접시를 쌓아보자. 
def push(self, data):
    self.items.append(data)

부페에 가면 테이블에 접시를 두는 공간이 있다. 그 공간 중 하나에 접시들을 차곡차곡 쌓는 코드다.

 

# 손님이 접시를 하나씩 가져간다. 
def pop(self): 
    pop_object = None
    # 접시 스택이 없다면 없다고 해
    if self.isEmpty():
        print("스택이 비었습니다.")
    # 아니면 접시 하나 줘 
    else: 
        pop_object = self.items.pop()
    return pop_object

여기는 왜 코드가 길어요? 우리가 부페에서 접시를 왜 쓰는지를 생각해보자. 부페는 접시 스택이 여러 줄인데, 손님들이 접시를 가져가다보면 중간에 비는 줄이 나오게 될 것이다. 이 경우에는 비었다는 게 눈에 보이니까 아, 비었구나. 하고 다른 줄에서 접시를 가져가겠지만, 이게 뚜껑이 닫혀있는 상자라면? 아니면 프링글스 통이라면? 누군가가 그거 빈 상자야, 혹은 그거 다 먹은거야라고 얘기를 해 줘야겠죠? 그거다.

 

보자… 안에 뭐가 들었나…?

def peek(self):
    top_object = None
    # 접시 스택이 없다면 없다고 해
    if self.isEmpty():
        print("스택이 비었습니다.")
    # 아니면 뭐가 있는지 보여줘 
    else: 
        top_object = self.items[-1]
    
    return top_object

이건 또 뭔가... 손님은 부페 접시를 당연히 가져가서 음식 담는 용도로 쓰지만, 내가 부페 직원이라면 접시 스택을 확인하는 목적이 접시가 부족한가를 보고 부족하면 리필하기 위해서일 것이다. 여기서 접시가 부족한가? 를 보는 코드가 이거다. 역시나 접시가 없으면 확인하고 채워야 하기 때문에 그 역할을 하는 코드가 있는 것 뿐이다.

 

isEmpty(): 어어 비었다

def isEmpty(self):
    # 기본 플래그: 안비었어
    is_empty = False
    # 스택의 길이가 0이라면 플래그가 바뀐다 
    if len(self.items) == 0:
        is_empty = True
    return is_empty

이건 일종의 플래그인데, 디폴트값은 안 비었다이다. 그리고 스택의 길이가 0이면 비었다로 바뀐다.

 

써보자 스택

# stack
stack_1 = stack()

# 아이템 적재
stack_1.push("이상해씨")
stack_1.push("미끄메라")
stack_1.push("날개치는머리")
stack_1.push("두두")
stack_1.push("아라리")

print(stack_1)

이렇게 하면 스택 안에 든 게 안 나오고 <__main__.stack object at 0x1008f0980>라고 뭐가 튀어나온다. 아니 이게 머여? 

def show(self):
    if self.isEmpty():
        print("스택이 비었습니다.")
    else:
        print(self.items)

는 클래스 안에 스택 전체를 볼 수 있는 것도 추가함… 저게 반복문으로 될 것 같죠? 응 아니야.

 

큐

큐는 스택과 달리 먼저 온 사람이 먼저 나가는 구조다. 스택이 부페 접시, 프링글스였다면 큐는 대기열(게임이나 이런데 있는), 출근시간대 메가커피 앞에 있는 줄(미리 안 시키면 똥줄타요…), 수강신청 대기열이다. 근데 구현하려고 찾아보니 다 리스트 아니면 모듈이라 지피티한테 버스터콜함… ㅋㅋ

 

대기장소(?) 만들기

def __init__(self): 
    self.items = []

큐가 줄을 서는거지 우리 보통 줄 서는 장소는 정해져 있습니다. 메가커피에서 커피 기다리는 사람들은 커피가 나오는 곳 앞에 줄을 서 있고, 수강신청이나 콘서트 예매같은 거 하는 사람은 사이트에서 기다리잖음. 그런겁니다.

 

인큐&디큐

# 큐에 뭘 넣는거(줄서는것)=인큐
def enqueue(self,data):
    self.items.append(data)

일단 인큐, 디큐가 뭔지 설명을 해주겠다. 아 뭔지 아세요? 그럼 여기 왜 오신ㄱ……

 

출근길에 메가커피에서 커피를 주문하는 건 인큐다. 왜죠? 커피를 받기 위한 대기열에 줄을 선 거니까요. 그리고 내 커피가 나와서 커피를 받아가는 건 디큐다. 왜죠? 커피를 받고 대기열에서 나와서 내 갈 길 가는거니까요. 그리고 위에 있는 코드는 메가커피에 커피를 주문하고 대기열에 줄을 선 거다.

 

# 큐에서 빼는것(커피 받았다 회사가자)=디큐
def dequeue(self):
    # 큐가 비었나요? (대기열이 없나요?)
    if self.isEmpty():
        print("큐가 비었습니다!")
        return None
    # 대기열이 있다면 맨 앞 손님의 주문을 해결하자 
    else: 
        return self.items.pop(0)

이건 디큐다. 스택처럼 디큐 코드에도 뭔가 있는데... 메가커피가 항상 붐비는 게 아니라 상대적으로 한산한 시간대가 있다. 뭐 예를 들자면 오후 한 2~3시쯤... 그때는 대기열이 없기때문에 주문도 안 들어오고, 커피를 내 갈 필요도 없다. 하지만 대기열이 있다면 맨 앞의 손님이 주문한 커피를 해결해서 큐에서 내보내야 한다.

 

대기열이 얼마나 있나?

# 보자... 지금 주문이 얼마나 밀렸지? 
def peek(self): 
    # 손님이 있나? 
    if self.isEmpty():
        print("큐가 비었습니다!")
        return None
    # 아, 있네. 
    return self.items[0]

이건 사실 대기열이라기보다는 먼저 온 주문이 뭔지를 파악하는 것에 가깝다. 봐봐요. 5번 고객이 라떼를 시켰는데 6번 고객이 아아를 시켰어, 그러면 라떼 먼저 처리해야 할 거 아님. 고객의 시간과 인내심은 유한하잖아요. 그래서 손흥민 골 넣는 날은 메가커피 갈 때 각오해야됩니다…

 

주문 있냐?

def isEmpty(self):
    # 기본 플래그: 안비었어
    is_empty = False
    # 스택의 길이가 0이라면 플래그가 바뀐다 
    if len(self.items) == 0:
        is_empty = True
    return is_empty

스택에 썼던 그 코드 맞는데, 큐에서는 약간 의미가 달라서 접시탑 비었냐? 가 아니라 대기열 비었냐?가 된다.

 

주문 얼마나 있음?

# 대기열 얼마나 있음? 
def size(self):
    return len(self.items)

스택에 넣어도 될듯. 이 코드는 말 그대로 큐의 크기를 반환한다.

 

큐 전체 보여줘

# 큐 전체를 볼 수 있다. 
def show(self):
    if self.isEmpty():
        print("큐가 비었습니다!")
    else:
        print(self.items)

스택에도 있는 그거 맞다. 전체를 보여주는.

 

써보자 큐

# 커피 대기열
coffee = queue()

coffee.enqueue("(HOT)카페라떼")
coffee.enqueue("(HOT)아메리카노")
coffee.enqueue("(HOT)헤즐넛라떼")
coffee.enqueue("(ICE)유니콘프라페")
coffee.enqueue("(HOT)연유라떼")

coffee.show()

여기서 디큐를 하게 되면 뭐가 제일 먼저 나가는가… 이게 스택이었으면 연유라떼가 먼저 나갔겠지만 큐는 카페라떼가 먼저 나간다.

# 손님 주문하신 카페라떼 나왔습니다
coffee.dequeue()
# 뱅쇼 주문 받았습니다
coffee.enqueue("(HOT)뱅쇼")
coffee.show()

하나를 디큐했더니 하나가 인큐된 상황. 큐에서 카페라떼가 나가고 뱅쇼가 들어오게 된다.