[자료구조] Queue & Stack

<개념복습>

1. Queue
- 큐 메모리구조? 선입선출을 따르는 자료구조
- 가장 먼저 저장된 데이터(push)가 가장 먼저 인출(pop)되는 구조


2. Stack
- 먼저 들어온 데이터가 나중에 나가고, 나중에 들어온 데이터는 먼저 나가는 구조의 컬렉션- Push()와 Pop()을 이용 
- 후입선출(LIFO) 시멘틱을 따르는 자료 구조 

 

3. Deque

- Double-Ended Queue의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는 

- 파이썬에서는 데크자료형을 collections모듈에서 deque라는  이름으로 지원 

 

20. Valid Parentheses

class Solution:
    def isValid(self, string: str) -> bool:
        
        dic = {"}" : "{", 
               ")" : "(", 
               "]" : "["}
            
        stack = [];
        
        for s in string:            
            if s not in dic:
                stack.append(s);
            elif not stack or dic[s] != stack.pop():
                return False;
            
        
        return len(stack) == 0

 

 

 

23. Merge k Sorted Lists

- Hint? 

 

 

 

 

225. Implement Stack using Queues

class MyStack:

    def __init__(self):
        self.q = collections.deque();
        

    def push(self, x: int) -> None:
        self.q.append(x);
        for _ in range(len(self.q)-1):
            self.q.append(self.q.popleft())
        
    def pop(self) -> int:
        return self.q.popleft();

    def top(self) -> int:
        return self.q[0];
    
    def empty(self) -> bool:
        return len(self.q) == 0

self.q.append(self.q.popleft()) -> queue니깐 재 정렬을 해줌 

 

 

232. Implement Queue using Stacks

class MyQueue:

    def __init__(self):
        self.q = collections.deque();        

    def push(self, x: int) -> None:
        self.q.append(x)     

    def pop(self) -> int:
        return self.q.popleft();
        
    def peek(self) -> int:
        return self.q[0];

    def empty(self) -> bool:
        return len(self.q) ==0

 

 

 

 

316. Remove Duplicate Letters

 

 

 

 

 

622. Design Circular Queue

 

 

 

 

 

 

 

739. Daily Temperatures

 

 

 

 

 

 

 

 

 

 

 

 

<출처>

1. 

2. freestrokes.tistory.com/84

3. 인프런 java 알고리즘 강의