스택(Stack)과 큐(Queue)

스택(Stack)과 큐(Queue)

 

스택과 큐는 제약을 갖는 배열이다. 제약하는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있으며 문제를 해결하는 새로운 사고방식을 제공한다. 또한, 제약을 제대로 이해해서 작성한 코드는 다른 개발자에게 익숙하고 명쾌하게 읽힌다. 그 알고리즘이 그러한 제약을 가진 채로 동작함을 알게 된다.

 

---

스택(Stack)

 

스택 연산을 묘사하자면 (Last In, First Out) 후입선출을 뜻한다.

처음 들어간 원소가 마지막에 나온다.

 

스택은 다음과 같은 세 가지 제약이 있다.

 

• 데이터는 스택의 끝에만 삽입 가능
• 데이터는 스택의 끝에서만 삭제 가능
• 스택의 마지막 원소만 읽을 수 있음

 

또 한, 스택의 특징은

 

• 스택의 끝을 top
• 스택의 시작을 bottom
• 스택의 top에서 원소를 제거하는 것을 pop
• 스택의 top의 위에 원소를 추가하는 것을 push

 

 

스택 구현

 

스택을 파이썬코드로 구현하였다.

 

stack = []


#push 정수 X를 넣는 연산
def push(X):
    stack.append(X)

#pop 스택에서 가장 위쪽 삭제
def pop():
    #비어 있으면 false
    if(len(stack) == 0):
        print(-1)
    else:
        print(stack.pop())
#size 사이즈 반환     
def size():
    print(len(stack))

#empty 비어있으면 1 아니면 0
def empty():
    #스택이 비어있으면 true
    if(len(stack) == 0):
        print(1)
    #else False
    else:
        print(0)
        
#top 가장 위에있는 정수 출력
def top():
    print(stack[-1])

 

---

큐(queue)

 

큐(queue) 역시 임시 데이터를 처리하기 위해 디자인된 데이터 구조다. 순서만 제외하면 스택과 거의 유사하며 추상 데이터 타입이다.

 

큐의 연산을 묘사하자면 (First In, First Out) 선입선출을 뜻한다.

처음 들어간 원소가 처음으로 나온다.

 

스택과 마찬가지로 큐도 세 가지 제약이 있다.

 

• 데이터는 큐의 끝에만 삽입
• 데이터는 큐의 앞에서만 삭제 가능
• 큐의 앞에 있는 원소만 읽을 수 있다.

 

또한, 큐의 특징은

 

• 큐의 시작을 front
• 큐의 끝을 back
• 큐의 front에서 원소를 제거하는 것을 pop
• 큐의 back에서 원소를 추가하는 것을 push

 

큐 구현

 

큐의 구현은 파이썬으로 작성 하였으며, 백준사이트에 제출한 코드를 사용하였다. collection 모듈의 deque를 사용하여 쉽게 구현하였다.

 

from collections import deque
import sys


T = int(sys.stdin.readline().rstrip())

fque = deque()

for i in range(T):
    cs = sys.stdin.readline().rstrip().split()
    if len(cs) == 2:
        cs[1] = int(cs[1])
    
    # push X: 정수 X를 큐에 넣는 연산이다.
    if cs[0] == 'push':
        fque.append(cs[1])

    # pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    elif cs[0] == 'pop':
        if len(fque) == 0:
            print(-1)
        else:
            print(fque.popleft())

    # size: 큐에 들어있는 정수의 개수를 출력한다.
    elif cs[0] == 'size':
        print(len(fque))

    # empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
    elif cs[0] == 'empty':
        if len(fque) == 0:
            print(1)
        else:
            print(0)

    # front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    elif cs[0] == 'front':
        if len(fque) == 0:
            print(-1)
        else:
            print(fque[0])

    # back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
    elif cs[0] == 'back':
        if len(fque) == 0:
            print(-1)
        else:
            print(fque[-1])