[자료구조] 스택(stack)

잔뜩 쌓아둔 접시를 떠올려 보자. 가장 마지막에 쌓은 접시부터 꺼내게 될 것이다

 

 

1. 정의 및 기능

• 정의
  • 후입선출(LIFO) 방식으로 데이터 삽입(push)과 삭제(pop)가 한쪽 끝에서만 이루어지는 추상 자료형이다. 파이썬에서는 리스트(list)가 스택의 모든 기능을 지원한다
• 기능 
  • push
    • 요소를 맨 끝에 추가한다
  • pop
    • 아직 제거되지 않은 가장 최근에 삽입된 요소 제거한다

 

2. 구현

• 연결 리스트를 이용해 스택을 구현해볼 수 있다

# 노드 정의
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

 

• 큐 2개로 스택을 구현해볼 수 있다

import queue

class Stack(object):
    def __init__(self):
        self.q1 = queue.Queue()
        self.q2 = queue.Queue()

    def push(self, element):
        self.q1.put(element)

    def pop(self):
        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())

        temp = self.q1
        self.q1 = self.q2
        self.q2 = temp

        return self.q2.get()

 

 

 

 

3. 예시 문제

• 괄호로 된 입력값이 올바른지 판별하기(Leetcode 20. Valid Parentheses)
  https://leetcode.com/problems/valid-parentheses/

def isValid(self, s:str) -> bool:
    stack = []
    table = {
        ')' : '(',
        '}' : '{',
        ']' : '[',
    }
    
    for char in s:
        if char not in table:
            stack.append(char)
        elif not stack or table[char] != stack.pop():
            return False
        
    return len(stack) == 0

 

• 중복 문자를 제외하고 사전식 순서로 나열하기(Leetcode 316. Remove Duplicate Letters)
  https://leetcode.com/problems/remove-duplicate-letters/

# 방법 1. 재귀를 이용한 분리
def removeDuplicateLetters(self, s:str) -> str:
    # 집합으로 정렬
    for char in sorted(set(s)):
        suffix = s[s.index(char):]
        if set(s) == set(suffix):
        	return char + self.removeDuplicateLetters(suffix.replace(char,''))
        return ''

# 방법 2. 스택을 이용한 문자 제거
def removeDuplicateLetters(self, s:str) -> str:
    counter, seen, stack = collections.Counter(s), set(), []
    
    for char in s:
        counter[char] -= 1
        if char in seen:
            continue
            
        # 뒤에 붙일 문자가 남아있는 경우, 스택에서 제거
        while stack and char < stack[-1] and counter[stack[-1]] > 0:
            seen.remove(stack.pop())
        stack.append(char)
        seen.add(char)
        
    return ''.join(stack)

 

• 일일 온도 리스트 T를 입력받아, 더 따뜻한 날씨를 위해 며칠을 더 기다려야 하는지(Leetcode 739. Daily Temparatures)
  https://leetcode.com/problems/daily-temperatures/

def dailyTemperatures(self, T: List[int]) -> List[int]:
    answer = [0] * len(T)
    stack = []
    for i, cur in enumerate(T):
        # 현재 온도가 스택 값보다 높으면 정답 처리
        while stack and cur > T[stack[-1]]:
            last = stack.pop()
            answer[last] = i - last
        stack.append(i)
    
    return answer

 

 

 

 

 

[출처] 파이썬 알고리즘 인터뷰