[자료구조, 파이썬] Queue과 Stack의 개념과 구현

1. Queue 개념과 구현

Queue는 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다. queue의 rear에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front에서 데이터를 꺼내는 것을 dequeue라고 합니다.

 

더블링크드리스트를 파이썬으로 아래와 같이 구현해보았습니다.(직접 구현한 것이므로 버그가 있다면 지적 부탁드립니다.)

Array list로 구현한 큐는 선출할 때, O(n)의 시간복잡도가 걸리므로(배열 길이만큼 한칸씩 앞으로 땡겨주어야 함) O(1)로 처리가능한 링크드리스트로 구현하는 것이 좋습니다.(head 값만 바꿔주면 됨)

class Node:
    def __init__(self, value = 0, prev = None, next = None):
        self.value = value
        self.next = next
        self.prev = prev
    
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
    def insert(self, value = 0):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
    def pop(self):
        if self.head != None:
            print(self.head.value, "pop")
            self.head = self.head.next
        else:
            print("Nothing in Queue!!!")


q = Queue()
q.insert(5)
q.insert(1)
q.insert(2)
q.pop() # 5 pop
q.pop() # 1 pop
q.pop() # 2 pop
q.pop() # Nothing in Queue!!!

2. deque ( Linked List based Queue)

사실 파이썬에서는 queue가 이미 링크드리스트로 deque로 구현되어 있습니다.

deque는 doubly ended queue의 약자로, 앞뒤로 삽입/삭제가 가능합니다.

한마디로 파이썬 deque는 front에서도 enqueue를 할 수 있고, rear에서도 dequeue를 할 수 있습니다.

from collections import deque
queue = deque()
# enqueue() O(1)
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)

# dequeue() O(1)
queue.popleft()
queue.popleft()
queue.popleft()

3.  Stack 개념과 구현

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장하는 자료구조입니다. stack의 top에 데이터를 추가하는 것을 push라고 하고 stack의 top에서 데이터를 추출하는 것을 pop이라고 합니다.

class Stack:
    def __init__(self):
        self.li = []

    def insert(self, value = 0):
        self.li.append(value)
    def pop(self):
        if len(self.li):
            print(self.li.pop())
        else:
            print("Nothing in Stack!!!")
        

q = Stack()
q.insert(5)
q.insert(1)
q.insert(2)
q.pop() # 5 pop
q.pop() # 1 pop
q.pop() # 2 pop
q.pop() # Nothing in Stack!!!

파이썬 리스트에 append와 pop 연산을 해주기만 해도, 가장 최근에 들어온 데이터가 나가는 후입선출 자료구조가 됩니다.

stack = []
# push O(1)
stack.append(1)
stack.append(2)
stack.append(3)
# pop O(1)
stack.pop()
stack.pop()
stack.pop()

4.  리트코드 Stack 문제(1)

https://leetcode.com/problems/valid-parentheses/

 

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 

풀이

class Solution:
    def isValid(self, s: str) -> bool:
        self.li = []
        for i in s:
            if i == '(' or i == '[' or i == '{':
                self.li.append(i)
            elif len(self.li):
                if i == ')' and self.li[-1] == '(':
                    self.li.pop()
                elif i == ')' and self.li[-1] != '(':
                    self.li.append(i)
                elif i == ']' and self.li[-1] == '[':
                    self.li.pop()
                elif i == ']' and self.li[-1] != '[':
                    self.li.append(i)
                elif i == '}' and self.li[-1] == '{':
                    self.li.pop()
                elif i == '}' and self.li[-1] != '{':
                    self.li.append(i)
            elif i == ')' or i == ']' or i == '}':
                self.li.append(i)
        return len(self.li) == 0

5.  리트코드 Stack 문제(2)

https://leetcode.com/problems/daily-temperatures/

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(temperatures)
        for i in range(len(temperatures)):
            while stack and stack[-1][1]< temperatures[i]:
                pre_day, _ = stack.pop()
                ans[pre_day] = i - pre_day
            stack.append((i,temperatures[i]))
        return ans