스택과 큐

#기본리스트로 구현

for i in range(n):
	random_nums.pop(0)
    
#deque로 큐 구현

for i in range(n):
queue.popleft()

 

스택(Stack)

• 먼저 들어 온 데이터가 나중에 나가는 형식(후입선출, LIFO)의 자료구조입니다.

• 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있습니다

stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) # 최하단 원소부터 출력

 

stack의 함수들은 리스트가 크더라도 O(n)이다.  

stack과 같은 경우는 작은 프로젝트보다 굉장히 큰 프로젝트에 주로 쓰인다.

 

(문제1) 유효한 괄호

스택에 맨마지막에 들어 온것과 나가야 하는 괄호가 맞아야 짝이 맞는 문제

스택 문제 중에 가장 쉬운 문

def is_vald_parentheses(s):
	stack = []
    table = {
    	')':')',
        '}':'{',
        ']':'[',
        }
        
        # 스택 이용 예외 처리 및 일치 여부 판별
        for char in s:
        	if char not in table:
            	stack.append(char)
            elif not stack or table[char] != stack.pop()
            	return False
        retrun len(stack) == 0
print(is_vald_parentheses('{}[]()'))

큐(queue)

• 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출, FIFO)의 자료구조입니다.

• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있습니다.

• 큐 자료구조는 BFS 문제에서 활용된다.

 

from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

 

 

**파이썬 기본 리스트를 큐로 대체 하여 사용하면 안된다 !

• a 가 파이썬 리스트인경우

a.pop(): O(1)

a.pop(0): O(N) # 매우 느리다

 

• a가 deque인 경우

a.pop(): O(1)

a.popleft(): O(1)