스택

플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤

---

1. 스택이란

데이터를 보관할 수 있는 선형 구조로써,
데이터의 입출력 방향이 일치하는 특징이 있다.(push, pop)

---

2. push 동작

---

3. pop 동작

---

4. 스택 언더플로우

---

5. 스택 오버플로우

---

6. 스택 ADT

연산 정의

• size()
• is_emtpy()
• push()
• pop()
• peek()

1) 배열 기반

class ArrayStack:
    def __init__(self) -> None:
        self.data = []

    def size(self) -> int:
        return len(self.data)

    def is_empty(self) -> bool:
        return self.size() == 0

    def push(self, item) -> None:
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

2) 연결 리스트 기반

class LinkedListStack:
    def __init__(self) -> None:
        self.stack = DoublyLinkedList()

    def size(self) -> int:
        return self.stack.node_cnt

    def is_empty(self) -> bool:
        return self.size() == 0

    def push(self, item):
        new_node = Node(item)
        last_idx = self.size()
        next_idx = last_idx + 1
        self.stack.insert_at(next_idx, new_node)

    def peek(self) -> int:
        last_idx = self.size()
        return self.stack.get_at(last_idx).data

---

7. collections 활용하기

collections 모듈의 deque를 통해 스택을 구현할 수도 있다.

from collections import deque


stack = deque()

# push()
stack.append('a')
stack.append('b')
stack.append('c')
print(stack)

print('Initial stack:')
print(stack)

# pop()
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('\nStack after elements are popped:')
print(stack)

---

8. 괄호 유효성 검사

1) 리팩터링 이전 코드

문제 설명
소괄호: ( )
중괄호: { }
대괄호: [ ]
를 포함할 수 있는 수식을 표현한 문자열 expr 이 인자로 주어질 때, 이 수식의 괄호가 올바르게 여닫혀 있는지를 판단하는 함수 solution() 을 완성하세요. 이 함수는 수식의 괄호가 유효하면 True 를, 그렇지 않으면 False 를 리턴합니다.

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]


def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':       
			S.push(c)
        elif c in match:
            if S.isEmpty() or S.size() > len(expr[expr.index(c):]):
            	return False
            else: 
				t=S.pop()
				if t != match[c]:
                    return False
	return True

2) 개선 😄

def solution(expr):
    match = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    S = ArrayStack()
    for c in expr:
        if c in '({[':       
			S.push(c)
        elif c in match:
            if S.isEmpty() or S.size():
            	return False
            else: 
				t=S.pop()
				if t != match[c]:
                    return False
	return S.isEmpty()