7. Stack, Queue, Dequeue

7. Stack, Queue, Dequeue

1. 스택 (Stack) 이란?

• Last In, First Out (LIFO) 구조
• 나중에 들어온 데이터가 먼저 나간다
• 접시 쌓기라고 생각하면 됨

1.1 주요 연산:

연산	설명
push(x)	x를 스택에 넣는다
pop()	스택에서 가장 위의 값을 제거하고 반환
peek() / [-1]	가장 위의 값 확인만 함
empty()	비었는지 확인

1.2 예제 1

stack = []
stack.append(1) # push
stack.append(2)
print(stack.pop()) # 2
print(stack[-1])   # 1

---

2. 큐 (Queue)

• First In, First Out (FIFO) 구조
• 먼저 들어온 데이터가 먼저 나간다
• 은행 줄 서기처럼 앞사람이 먼저 처리됨

2.1 주요 연산:

연산	설명
enqueue(x)	x를 큐에 넣는다
dequeue()	큐에서 가장 앞의 값을 제거하고 반환
peek() / [0]	맨 앞 값을 확인
empty()	비었는지 확인

2.2 예제 1 :

from collections import deque

queue = deque()
queue.append(1) # enqueue
queue.append(2)
print(queue.popleft()) # 1
print(queue[0])        # 2

---

3. 덱 (Deque, Double-ended Queue)

• 양쪽 끝에서 데이터를 넣고 뺄 수 있는 구조
• 스택처럼도, 큐처럼도 사용 가능

3.1 주요 연산:

연산	설명
append(x)	오른쪽에 삽입
appendleft(x)	왼쪽에 삽입
pop()	오른쪽 값 제거
popleft()	왼쪽 값 제거

3.2 예제 1 :

from collections import deque

dq = deque()
dq.append(1)     # 오른쪽에 추가
dq.appendleft(2) # 왼쪽에 추가
print(dq.pop())  # 오른쪽 제거 -> 1
print(dq.popleft()) # 왼쪽 제거 -> 2

---

4.스택, 규, 덱 핵심 요약

구조	특성	주요 연산
스택	LIFO	append(), pop()
큐	FIFO	append(), popleft()
덱	양방향	append(), appendleft(), pop(), popleft()

---

5. 실전 문제

문제 1. 괄호 짝 검증기

📘 문제 설명

프로그래밍 언어에서 괄호는 짝이 맞아야 합니다. 다음 조건을 만족해야 괄호 짝이 맞다고 봅니다:

• 여는 괄호 (는 반드시 닫는 괄호 )로 닫혀야 한다.
• 닫는 괄호보다 여는 괄호가 먼저 나와야 한다.
• 모든 괄호는 짝이 맞아야 한다.

입력 문자열이 이러한 올바른 괄호 문자열(VPS) 인지 판별하시오.

📥 입력 형식

• 문자열 s (1 ≤ 길이 ≤ 100)

📤 출력 형식

• 올바른 괄호 문자열이면 YES, 아니면 NO 출력

입력 예시 1

(()())()

출력 예시 1

YES

입력 예시 2

())(()

출력 예시 2

NO

💡 힌트

• 여는 괄호면 push
• 닫는 괄호면 pop (비었으면 NO)
• 마지막에 stack이 비어있어야 함

해설

def ans(input_str):
    stack = []
    for ch in input_str:
        if ch == '(':
            stack.append(ch)
        else:
            if not stack:
                return 'NO'
            stack.pop()
    if not stack:
        return 'YES'

test_case = (
    ('(()())()', 'YES'),
    ('())(()','NO'),
    ('()))()', 'NO'),
    ('()', 'YES'),
    ('(()))', 'NO')
)

for i, (input_str, answer) in enumerate(test_case, 1):
    result = answer == ans(input_str)
    if result:
        print(f'#{i} OK')
    else:
        print(f'${i} FAIL - input_str:{input_str} answer:{answer} result:{result}')


''' 출력
#1 OK
#2 OK
#3 OK
#4 OK
#5 OK
'''

---

문제 2. 프린터기

📘 문제 설명

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다.

하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다.

예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

📥 입력 형식

• 첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

• 테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다.

• 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

📤 출력 형식

• 각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

입력 예시

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

출력 예시

1
2
5

💡 힌트

• (idx, 중요도)로 큐에 넣고,
• 현재 문서보다 높은 게 뒤에 있으면 뒤로 보냄
• 인쇄될 때마다 count++
• idx == m이면 그게 정답

해설

from collections import deque

def printer_software(test_case):
    n, m = test_case[0]
    priorities = test_case[1]

    queue = deque([idx, pri] for idx, pri in enumerate(priorities))
    count = 0

    while queue:
        current = queue.popleft()
        if any(current[1] < itr[1] for itr in queue):
            queue.append(current)

        else:
            count+=1
            if m == current[0]:
                return count


test_case = {
    (((1, 0), (5,)), (1)),
    (((4, 2), (1, 2, 3, 4)), (2)),
    (((6, 0), (1, 1, 9, 1, 1, 1)), (5)),
    (((6, 0), (1, 1, 9, 3, 2, 5)), (5))
}

for idx, (case, answer) in enumerate(test_case, 1):
    result = printer_software(case)
    if answer == result:
        print(f'#{idx} OK')

    else:
        print(f'#{idx} FAIL - inputs:{case} answer: {answer} result: {result}')


''' 출력
#1 OK
#2 OK
#3 OK
#4 OK
'''