스택과 큐 /백준 1874

1. 스택

스택(Stack)은 데이터를 저장하고 검색하는 데 사용되는 추상 데이터 구조 중 하나로, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어지는 선형 자료 구조입니다. 스택은 후입선출(Last-In-First-Out, LIFO) 원칙을 따릅니다. 이것은 스택에 삽입한 가장 최근의 요소가 먼저 제거됨을 의미합니다.
스택은 다양한 컴퓨터 과학 및 소프트웨어 개발 분야에서 유용하게 활용됩니다. 예를 들어, 함수 호출 스택(call stack)은 함수 호출 및 반환 순서를 관리하는 데 사용됩니다. 재귀 함수 호출 시에도 스택을 사용하여 각 함수 호출을 추적하고 반환 순서를 관리합니다.
스택은 간단하면서 효율적인 자료 구조로, 데이터를 일시적으로 저장하고 추적하는 데 유용합니다. 많은 프로그래밍 언어 및 자료구조 라이브러리에서 스택을 지원하며, 스택을 직접 구현하거나 활용하는 방법을 익히는 것은 중요합니다.

1-1. 파이썬에서의 스택

파이썬에서 스택(Stack)을 구현하려면 리스트(List)를 사용할 수 있습니다. 리스트는 데이터를 저장하고 관리하는 데 사용되며, 스택의 push 및 pop 연산을 리스트의 내장 함수로 간단하게 구현할 수 있습니다. 

Push 연산 (요소 추가)

stack.append(item)

 

Pop 연산 (요소 제거 및 반환)

if len(stack) > 0:
    item = stack.pop()
else:
    print("스택이 비어있습니다.")

Peek (Top) 연산 (맨 위 요소 확인, 제거하지 않음)

if len(stack) > 0:
    top_item = stack[-1]
    print("맨 위 요소:", top_item)
else:
    print("스택이 비어있습니다.")

파이썬의 리스트는 동적 배열로 구현되어 있으므로 스택을 구현하기에 매우 효과적입니다. 리스트의 `append` 메서드를 사용하여 요소를 스택에 push하고, `pop` 메서드를 사용하여 맨 위 요소를 제거하고 반환할 수 있습니다. `[-1]` 인덱스를 사용하여 스택의 맨 위 요소를 쉽게 확인할 수 있습니다.

파이썬에서는 스택을 직접 구현할 필요가 없는 경우, `collections.deque`와 같은 덱(Deque) 자료 구조도 사용할 수 있으며, 이것은 스택 및 큐(Queue)와 관련된 연산을 모두 지원합니다.

from collections import deque

stack = deque()

# Push 작업
stack.append(1)
stack.append(2)
stack.append(3)

# 스택 출력: deque([1, 2, 3])

# Pop 작업
item = stack.pop()  # 스택에서 3을 제거하고 반환
print(item)  # 출력: 3

# 스택 출력: deque([1, 2])

2. 큐

큐(Queue)는 데이터를 저장하고 관리하는 선형 자료 구조로, 데이터의 삽입(Enqueue)과 삭제(Dequeue)가 서로 다른 끝에서 이루어지는 구조입니다. 큐는 선입선출(First-In-First-Out, FIFO) 원칙을 따릅니다. 이것은 큐에 삽입된 데이터가 먼저 들어온 데이터가 먼저 나가는 것을 의미합니다.

큐에 사용되는 주요 연산은 다음과 같습니다:
Enqueue (Push): 큐에 데이터를 추가하는 작업을 Enqueue 또는 Push라고 합니다. 이 작업은 큐의 뒤쪽(또는 한 쪽 끝)에 데이터를 추가합니다.
Dequeue (Pop): 큐에서 데이터를 제거하는 작업을 Dequeue 또는 Pop이라고 합니다. 이 작업은 큐의 앞쪽(또는 다른 쪽 끝)에서 데이터를 제거하고 반환합니다.
Front (Peek): 큐의 맨 앞에 있는 데이터를 반환하지만 제거하지 않는 작업을 Front 또는 Peek라고 합니다.
Rear (또는 Back): 큐의 맨 뒤에 있는 데이터를 반환하지만 제거하지 않는 작업을 Rear 또는 Back이라고 합니다.

2-1. 파이썬에서 큐

파이썬에서는 리스트를 사용하여 큐를 구현할 수 있으며, `append` 메서드를 사용하여 Enqueue(데이터 추가)하고, `popleft()` 메서드를 사용하여 front부분의 데이터를 Dequeue(데이터 제거)할 수 있습니다. 또한 리스트[0] 인덱스를 통해 맨 앞의 데이터를 삭제없이 확인할 수 있습니다.
큐 자료구조 역시 `collections.deque`를 사용하여 구현될 수 있습니다.

from collections import deque

queue = deque()

# Enqueue 작업
queue.append(1)
queue.append(2)
queue.append(3)

# 큐 출력: deque([1, 2, 3])

# Dequeue 작업
item = queue.popleft()  # 큐에서 1을 제거하고 반환
print(item)  # 출력: 1

# 큐 출력: deque([2, 3])

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

<풀이>

N = int(input())
A = [(int(input())) for i in range(N)]

stack = []
num = 1
result = True
answer = ""

for i in range(N):
    target = A[i]
    
# 타겟이 자연수보다 크다면 값이 같아질 때까지 append 실행
    if target >= num:
        while target >= num:
            stack.append(num)
            num += 1
            answer += "+\n"
# append가 완료되면 값이 같아졌기 때문에 pop을 실생
        stack.pop()
        answer += "-\n" 
    else:
    # n은 스택의 가장 마지막 숫자
        n = stack.pop()
    # n이 target보다 크다면 수열은 완성될 수 없음
        if n > target:
            print('No')
            result = False
            break
    # 스택의 마지막 숫자가 타겟보다 작거나 같다면 pop한 결과에 따라 -추가
        else:
            answer += '-\n'
if result:
    print(answer)