[이론] 스택 Stack, 큐 Queue

스택 Stack 이란?

• Stack은 데이터를 한쪽에서만 넣고 빼는 자료구조이다.
• LIFO(Last-in First-out) 후입선출 방식이다. (들어온 순서와 반대로 나감)
• push, pop으로 데이터를 삽입하고 가져온다.

왜 스택을 써야할까?

• 뒤집기, 되돌리기, 되돌아가기 기능

데이터를 반대로 정렬하거나 뒤집히는 형태를 만들 때 주로 사용된다.

스택은 들어온 순서와 반대이기 때문에 이 점을 활용한다. 

 

예를 들어, 브라우저의 뒤로가기, 워드의 ctrl + z 등과 같은 원리이다.

 

• 마무리 되지 않은 일을 임시 저장

어떤 작업이 마무리되지 않은 상황이지만, 추후에 다시 작업을 해야하는 상황일 때

마무리 되지 않은 작업을 일단 스택에 넣어둔다. 다시 돌아와서 마지막에 작업했던 것 부터 꺼내서 작업하기에 용이하기 때문이다. 

괄호 매칭, 함수 호출, 백트래킹, DFS(깊이 우선 탐색) 문제에서 주로 사용된다. 

 

스택 활용

• 리스트로 간편하게 활용한다.

스택 리스트

스택을 리스트로 표현하자면 오른쪽의 이미지와 같다. 

리스트에 새로운 데이터를 넣을 때는 .append()를 사용한다. 

 

• 예문

stack = []

for _ in range(int(input())):
	number = int(input())
    
    if number == 0:
    	stack.pop()
    else:
    	stack.append(number)

print(sum(stack))

stack 리스트를 생성한 후,

.pop()과 append()를 사용하여 데이터 삽입, 제거를 한다. 

 

 

 

큐 Queue 란?

• 한쪽 끝에서 데이터를 넣고, 다른 한쪽에서만 데이터를 뺄 수 있는 자료구조이다.
• 가장 먼저 들어온 데이터가 가장 먼저 나가므로 FIFO(First-in First-out, 선입선출) 방식이다.

 

* dequeue: 큐의 맨 앞 데이터를 가져오는 것 

* enqueue: 큐의 맨 뒤 데이터를 삽입하는 것

 

큐 활용

• 큐 또한 리스트로 활용 가능하다. 

• 예문

n = int(input())
queue = list(range(1, n + 1))

while len(queue) > 1:
	print(queue.pop(0), end=" ")
    queue.append(queue.pop(0))

print(queue[0])

 

큐 자료구조의 단점

• 데이터를 뺄 때 데이터가 많은 경우 비효율적이다.
• 맨 앞 데이터가 바뀌면서 리스트의 인덱스가 당겨지기 때문이다.

 

덱 dequeue (Double-Ended Queue)

• 양방향으로 삽입과 삭제가 자유로운 Queue이다. 
• 상수시간 (O(1))으로 삽입, 추출이 모두 큐보다 빠르다. 
• 왼쪽에서 데이터를 뺄 때 appendleft(), popleft()를 사용한다. 

 

# Queue

n = int(input())
queue = list(range(1, n + 1))

while len(queue) > 1:
    print(queue.pop(0), end=" ")
    queue.appened(queue.pop(0))


print(queue[0])

 

 

# Dequeue

from collections import deque

n = int(input())
queue = deque(list(range(1, n + 1))

while len(queue) > 1:
    print(queue.popleft(), end=" ")
    queue.appened(queue.popleft())


print(queue[0])

 

큐와 덱의 예문을 통해 차이를 확인해보자면, 

덱을 이용하기 위해서는 'from collections import deque' 로 dequeue을 불러와야하며, 

'queue = deque(list(range(1, n + 1)) ' list 앞에 deque으로 감싸주며

'queue.popleft() ' 왼쪽으로 데이터를 제거하는 기능을 사용할 수 있다.