[알고리즘/Python] 스택(Stack) /큐(Queue)

📌 관련 문제 풀이 모음 (계속 추가추가..)

• 2024.10.17 - [분류 전체보기] - [프로그래머스/Python] 알고리즘고득점Kit-스택/큐-프로세스
• 2024.10.17 - [코딩테스트/프로그래머스] - [프로그래머스/Python] 알고리즘고득점Kit-스택/큐-올바른 괄호
• 2024.10.17 - [코딩테스트/프로그래머스] - [프로그래머스/Python] 알고리즘고득점Kit-스택/큐-기능개발
• 2024.10.12 - [코딩테스트/프로그래머스] - [프로그래머스/Python] 알고리즘고득점Kit-스택/큐-같은숫자는 싫어

 

📌 1. 스택 (Stack)

• 후입 선출 구조 Last In First Out(LIFO)로 나중에 들어간 것이 먼저 나오는 구조이다.
• 파이썬에서는 별도의 라이브러리 사용 없이 기본 리스트를 사용하여 스택을 구현할 수 있다.

stack = []

stack.append(1) # 삽입 O(1)
stack.pop() # 삭제 O(1)

stack[-1] # 삭제 하지 않고 최상단 원소 가져오기
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) #최상단 원소부터 출력

 

 

📌 2. 큐 (Queue)

• 선입 선출 구조 First In First Out(FIFO)로 먼저 들어간 것이 먼저 나오는 구조이다.
• 별도의 라이브러리 없이 리스트를 사용하여 pop(0) or insert(0, x) 통해서도 구현할 수 있지만 시간복잡도가 O(n)이기 때문에 불리한 연산이다. 그렇기 때문에 별도의 라이브러리를 사용해서 구현하는 것이 좋다.
• 파이썬에서는 collections에서 제공하는 deque를 활용하는 것이 좋다. deque는 스택과 큐의 장점을 모두 채택한 것으로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조로, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해서 효율적이다.

from collections import deque

queue = deque() # 리스트를 변수로 사용 가능
queue = deque([1,2,3,4]) # 바로 선언도 가능

queue.append(1) # 삽입 O(1)
queue.popleft() # 삭제 O(1) - i = 0 삭제 
queue.pop() 	# i = n-1 삭제 

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력