# 1. 스택과 큐 (Stack and Queue)

스택과 큐라고 하면 무엇이 떠오르는가? 

 

 

지금은.. 나서스의 스택을 안떠올렸으면 좋겠다. (스택의 의미가 아닌것은 아니지만..) 이 포스트를 통해 스택의 개념을 익히면 나서스가 왜 스택을 쌓는다고 표현할지 알것이다.

 

스택과 큐

 

우선 직관적으로 접근하기 위해서는 그림을 그려보자. 스택과 큐를 유리컵에 비유하자면, 스택은 바닥이 막혀있는 유리컵이고 큐는 바닥이 뚫려있는 유리컵이다. 그리고 우리가 물건을 넣은 모습은 다음과 같다.

 

push

 

둘다 물건을 위에서 집어넣었다고 생각해보자. 그럼 물건을 어떻게 꺼낼까?

 

pop

 

스택은 마지막에 넣은 물건을 먼저 꺼내야하고, 큐는 가장 처음에 넣었던 물건을 먼저 꺼낼 수 있다.

 

[정리]

• 스택은 선입후출(FILO: First In Last Out, 먼저 들어온게 마지막에 나감)
• 큐는 선입선출(FIFO: First In First Out, 먼저 들어온게 먼저 나감)

 

필자가 생각하는 스택과 큐에서 키포인트는 다음과 같다. "스택은 들어온 구멍으로만 나갈 수 있고, 큐는 들어오는 구멍과 나가는 구멍이 반대편에 있다."

 

이제 코드로 구현을 해보자.

 

[스택]

스택 클래스를 구현하기 위한 메소드들은 다음과 같다.

• is_empty() : 스택이 비어있는지 확인한다.
• push() : 스택의 맨 위에 데이터를 넣는다.
• pop() : 스택이 비어있는지 확인한 뒤에 맨 위의 데이터를 꺼낸다.
• top() : 스택의 맨 위의 데이터를 꺼내지 않고 return만 한다.

class Stack:
    """
    구현해야할 함수
    push()
    pop()
    top()
    is_empty()
    """

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

    def push(self, value):
        self.stack.append(value)

    def pop(self):
        return None if self.is_empty() else self.stack.pop()

    def top(self):
        return None if self.is_empty() else self.stack[-1]

    def is_empty(self):
        return False if len(self.stack) > 0 else True


if __name__ == '__main__':
    stack = Stack()
    stack.push(3)
    stack.push(4)
    stack.push(5)

    print(stack.top())  # 5 <- [3, 4, 5]
    print(stack.pop())  # 5 <- [3, 4]
    print(stack.top())  # 4 <- [3, 4]

 

[큐]

큐 클래스를 구현하기 위한 메소드들은 다음과 같다.

• is_empty() : 큐가 비어있는지 확인한다.
• enqueue() : 데이터를 맨 위에 넣는다.
• dequeue() : 큐가 비어있는지 확인한 뒤에 맨 아래의 데이터를 꺼낸다.
• peek() : 큐의 맨 아래의 데이터를 꺼내지 않고 return 만 한다.

class Queue:
    """
    구현해야할 함수
    enqueue()
    dequeue()
    peek()
    is_empty()
    """
    def __init__(self):
        self.queue = []

    def enqueue(self, value):
        self.queue.append(value)

    def dequeue(self):
        return None if self.is_empty() else self.queue.pop(0)

    def peek(self):
        return None if self.is_empty() else self.queue[0]

    def is_empty(self):
        return False if len(self.queue) > 0 else True


if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(3)
    queue.enqueue(4)
    queue.enqueue(5)

    print(queue.peek())     # 3 <- [3, 4, 5]
    print(queue.dequeue())  # 3 <- [4, 5]
    print(queue.peek())     # 4 <- [4, 5]

 

이로써 나서스가 왜 스택을 쌓는다고 표현했는지 이해했 가장 간단한 자료구조인 스택과 큐에 대해서 알아보았다. 다음 포스트에서는 데크에 대해서 알아보겠다.