Queue / Stack(큐/스택)

Queue(큐)

• 먼저 저장된 데이터가 먼저 출력되는 선입선출의 자료구조 (FIFO)
• python의 경우 colletions 모듈의 deque를 사용해서 구현
• enqueue는 data를 rear쪽에 추가하는 것
• dequeue는 data를 front쪽에서 꺼내는 것

Stack(스택)

• 가장 최근에 추가한 데이터가 먼저 출력되는 후입선출의 자료구조(LIFO)
• List를 활용하여 구현
• push는 top에 데이터를 추가하는 것
• pop은 top에서 데이터를 추출하는 것
• LIFO 특성을 활용한 문제 / DFS(깊이우선탐색)에 주로 사용 됨

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack<String> stack = new Stack<>();
        boolean answer = true;

        String[] sArr = s.split("");

        for(String i : sArr){
            if(stack.empty() && (i.equals(")") || i.equals("}") || i.equals("]"))){
                answer = false;
                return answer;
            } else if(!stack.empty() && stack.peek().equals("(") && i.equals(")")){
                stack.pop();
            } else if(!stack.empty() && stack.peek().equals("{") && i.equals("}")){
                stack.pop();
            } else if(!stack.empty() && stack.peek().equals("[") && i.equals("]")){
                stack.pop();
            } else {
                stack.push(i);
            }
        }

        if(stack.empty()){
            answer = true;
        } else {
            answer = false;
        }

        return answer;
    }
}

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

Valid Parentheses - LeetCode

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)

        stack = []

        for i in range(len(temperatures)):
            if not stack:
                stack.append([temperatures[i],i])
            else:
                if temperatures[i] > stack[-1][0]:
                    while stack and temperatures[i] > stack[-1][0]:
                        tmp = stack.pop()

                        answer[tmp[1]] = i - tmp[1]
                    stack.append([temperatures[i], i])
                else:
                    stack.append([temperatures[i], i])

        return answer

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

Daily Temperatures - LeetCode

 

 

 

출처 : https://www.inflearn.com/course/코딩테스트-입문-파이썬/