자료구조 스택과 큐

개요

1. 알고리즘에 대해 알아보자
2. 스택에 대해 알아보고 구현
3. 큐에 대해 알아보고 구현

---

1. 알고리즘

• 문제 해결 방법을 정의한 일련의 단계적 절차이자 어떠한 문제를 해결하기 위한 동작들의 모임이다.

이번 알고리즘 파트에서는 코딩으로 자료구조를 공부한다.

코딩으로 유명한 백준을 통해 아래 그림처럼 자료구조 문제가 준비되어있고 이를 풀어보고 분석하도록 한다.

2. 스택(Stack)

자료구조 하면 가장 처음 배우는게 스택과 큐이다.

그 중에서 스택에 대해 알아보고 스스로 구현을 해본다.

그리고 다른 사람들의 코드와 비교해서 부족한 점을 채워가도록 하자.

---

• 스택(Stack)은 “쌓다”라는 의미로, 데이터를 쌓아 올린 형태의 자료구조이다.

• LIFO(Last In First Out)으로 후입 선출의 구조를 가진다.

이해가 안된다면 아래 그림을 통해 자세히 알아보도록 하자.

데이터를 넣을 수 있는 입구가 위에만 존재한다.

push를 통해 데이터를 쌓고 pop()을 통해 데이터를 빼는 모습이다.

즉 가장 마지막에 입력된 데이터가 가장 먼저 삭제되는 구조를 가진다. ( 후입 선출 )

실제 사용 사례

• ctrl + z로 사용되는 실행 취소
• 웹 브라우저 뒤로가기

3. 스택(Stack) 구현

백준 자료구조 문제집을 통해 풀어 보자.

문제는 10828번으로 다음과 같다.

예제 입력은 두가지로 다음과 같다.

다음은 구현한 전체 코드이다.

import sys

# 첫번째 주어지는 명령의 수
n = int(input())

# 스택 만들기
stack = []

for i in range(n):
    # 반복문 안에서는 시간 초과로 인해서 input 대신해 sys.stdin.readline을 사용
    l = list(sys.stdin.readline().split())

    # 스택에 데이터를 넣음
    if "push" in l:
        stack.append(int(l[-1]))

    # 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력
    # 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력
    elif "pop" in l:
        if len(stack) == 0:
            print(-1)
        else:
            pop_data = stack[-1]
            del stack[-1]
            print(pop_data)
        
    # 스택의 가장 위에 있는 정수를 출력
    # 스택에 들어있는 정수가 없는 경우에는 -1 출력
    elif "top" in l:
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

    # 스택에 들어있는 정수의 개수를 출력
    elif "size" in l:
        print(len(stack))

    # 스택이 비어있으면 1, 아니면 0
    elif "empty" in l:
        if len(stack) == 0:
            print(1)
        else:
            print(0)

push, pop, top, size, empty로 구성되어 있고 각각은 주석으로 설명이 되어있다.

다른 코드와 비교한 결과 python에서는 pop을 지원해서

위 코드에서 pop을 구현할 때

pop_data = stack[-1]
del stack[-1]
print(pop_data)

보다

print(stack.pop())

한줄이면 가능하다.

4. 큐(Queue)

• 큐는 한쪽 끝에서만 삽입이 이루어지고, 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트이다.

• FIFO(First in First Out)으로 선입선출이다.

아래의 그림으로 정확히 알아보도록 하자.

각각 rear로 데이터 삽입(insert)이 이루어지고 front로 데이터 삭제(delete)가 이루어집니다.

큐의 사용 사례

• 대기열 등 우선 순위 작업 예약
• 프로세스 관리

4. 큐 구현

이 또한 백준으로 알아보도록 하자.

문제는 10845번으로 다음과 같다.

예제 입력은 두가지로 다음과 같다.

다음은 구현한 전체 코드이다.

# 백준 10845
import sys

# 첫번째 주어지는 명령의 수
n = int(input())

# 큐 만들기
queue = []

for i in range(n):
    l = list(sys.stdin.readline().split())

    # 큐에 데이터를 넣음
    if "push" in l:
        queue.append(l[-1])

    # 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력
    # 큐에 들어있는 정수가 없는 경우에는 -1 출력
    elif "pop" in l:
        if len(queue) == 0:
            print(-1)
        else:
            queue_data = queue[0]
            del queue[0]
            print(queue_data)

    # 큐에 들어있는 정수의 개수를 출력
    elif "size" in l:
        print(len(queue))

    # 큐가 비어있으면 1, 아니면 0을 출력
    elif "empty" in l:
        if len(queue) == 0:
            print(1)
        else:
            print(0)

    # 큐의 가장 앞에 있는 정수를 출력
    # 큐에 들어있는 정수가 없는 경우에는 -1 출력
    elif "front" in l:
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])

    # 큐의 가장 뒤에 있는 정수를 출력
    # 큐에 들어있는 정수가 없는 경우에는 -1 출력
    elif "back" in l:
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])

push, pop, size, empty, front, back으로 구성되어 있고 각각 주석으로 설명 되어있다.

이거 또한 스택과 똑같이 pop 부분을 stack.pop을 활용해서 변경 가능하다.

이상으로 백준 코딩 사이트를 이용해서 스택과 큐에 대해 알아보았다.