스택과 큐

스택 : 후입선출

큐 : 선입선출

 

리스트는 동적할당으로 구현되어있어서 큐의 연산을 수행하기에는 효율적이지 않다.

데크를 사용하면 좋은 성능을 낼 수 있다.

 

스택 구현

class Node:
	def __init__(self, item, next):
		self.item = item
		self.next = next

class Stack:
	def __init__(self):
		self.last = None
	
    #맨 위에 집어넣음
	def push(self,item):
		self.last = Node(item, self.last)
	
	#맨 위값 꺼냄
	def pop(self):
		item = self.last.item
		self.last = self.last.next
		return item

 

20. 유효한 괄호

'''
https://leetcode.com/problems/valid-parentheses
괄호로 입력된 값이 올바른지 판별하라.

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

Input: s = "([)]"
Output: false

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

방법1)
last in fisrt out. 
열린 괄호를 만날때 스택에 push하고
닫힌 괄호를 만날때 pop
pop했을때 닫힌 괄호와 일치하는지 확인

'''



class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        table = { ')':'(', 
                 '}' : '{',
                ']' : '['
                }
        for char in s:
            #괄호에 해당되지 않을 경우 stack에 추가 X
            if char not in table:
                stack.append(char)
            #stack이 비어있지 않고, pop한 결과와 다르다면
            elif not stack or table[char] != stack.pop():
                return False
            
        #스택이 비어있지 않다면 쌓이기만 했으므로 false
        return len(stack) == 0