[자료구조] Queue & Stack - Python으로 구현하기

Queue  

List기반

list의 append 메서드로 구현 

# queue 선언
q = []

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]

# dequeue O(n)
q.pop(0) # [2, 3]
q.pop(0) # [3]

Linked List 기반

python에서 이미 구현되어있는 deque(덱)이라는 자료구조가 있음 

Deque 는 Double Ended QUE 의 약자로 양방향으로 enque, deque가 가능하다. 

 

- Deque 메서드 정리 

	맨 앞 (왼쪽)	맨 뒤 (오른쪽)
삽입	appendleft()	append()
제거	popleft()	pop()

 

from collections import deque

# deque 선언
q = deque()

# enqueue O(1)
q.append(1) # [1]
q.append(2) # [1, 2]
q.append(3) # [1, 2, 3]
q.appendleft(0) # [0, 1, 2, 3]

# dequeue O(1)
q.popleft() # [1, 2, 3]
q.popleft() # [2, 3]
q.pop() # [3]

 

 

Stack

LIFO

list로 구현하는 것이 가장 간단

# stack 선언
s = []

# push - O(1)
s.append(1) # [1]
s.append(2) # [1, 2]
s.append(3) # [1, 2, 3]

# pop - O(1)
s.pop() # [1, 2]
s.pop() # [1]

 

LIFO 예시문제 1 

- 괄호 유효성 검사 

Valid Parentheses - LeetCode

def isValid(s):
  stack=[]
  for p in s:
    if p=='(':
      stack.append(')')
    elif p=='{':
      stack.append('}')
    elif p=='[':
      stack.append(']')
    elif not stack or stack.pop()!= p:  #stack이 비어있지 않고
      return False
  return not stack #stack이 비어있으면 True, 아니면 False

 

 

LIFO 예시문제 2

- 온도 리스트를 보고 몇일 기다리면 더 따뜻해지는지 검사하기 

Daily Temperatures - LeetCode

class Solution(object):
    def dailyTemperatures(self,temperatures):
      stack=[]
      ans= [0 for i in range(len(temperatures))]
      i=0
      while i <len(temperatures):
        while stack and stack[-1][0] <temperatures[i] :
          index =stack[-1][1]
          ans[index] = i - index
          stack.pop()
        stack.append((temperatures[i],i))
        i+=1
      return ans