리트코드

• 괄호로 된 입력값이 올바른지 판별하라.

1. 스택 일치 여부 판별

class Solution:
    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
        

• ' ( , { , [ ' 를 만나면 스택에 푸시(Push)하고, ' ) , } , ] ' 를 만날 때 스택에서 팝(Pop) 한 결과가 매핑 테이블 결과와 매칭되는지 확인하면 된다.

• 먼저 매핑 테이블을 만들어 놓고, 테이블에 존재하지 않으면 무조건 푸시하고, 팝했을 때 결과가 일치하지 않으면 False를 리턴하도록 한다.

  • 여기서 stack은 파이썬의 동적 배열 구현인 리스트를 사용했다.

  • 파이썬 리스트는 스택 연산인 푸시와 팝이 O(1)에 동작하기 때문에 성능에도 큰 문제가 없다.

• 실제로 실행시키기 위해서는 예외처리가 필요하다.

  이 문제의 경우에도 리트코드에는 비정상적인 테스트 케이스가 다수 포함되어있기 때문에 제대로 실행되기 위해서는 다음과 같이 예외 처리를 해야한다.

  • 여기서는 팝 결과가 일치하지 않는지 확인하는 것 외에도 스택이 비어 있는지 여부를 함께 확인하여 True, False를 결정하게 한다.

  • 이처럼 예외처리가 반드시 포함되어 있어야 한다

✔ 스택, 큐

• 스택: LIFO ( Last-In-First-Out, 후입선출 )

  • 마지막에 쌓은 접시가 맨 위에 놓일 것이라, 가장 마지막에 쌓은 접시를 제일 먼저 꺼내게 된다.

• 큐: FIFO (First-In-First-Out, 선입선출)

  • 가장 먼저 줄을 선 사람이 가장 먼저 입장한다.

• 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트 가 사실상 스택의 모든 연산을 지원한다.

  리스트는 큐의 모든 연산을 지원한다. 하지만, 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크(Deque) 라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다.

스택 (Stack)

• 스택은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다.

  • push( ): 요소를 컬렉션에 추가한다.

  • pop( ): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.

• 스택은 콜 스택(Call Stack) 이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다.

  컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다.

• 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다.

• 스택 버퍼 오버플로우(Stack Buffer Overflow)

  : 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것

<스택 추상 자료형과 메모리 구현>

• ADT는 스택의 연산을 지원하기 위해 1부터 5까지 각 요소가 접시 쌓든 차곡차곡 놓이겠지만, 실제로 연결 리스트로 구현하게 된다면 물리 메모리 상에는 순서와 관계 없이 무작위로 배치되고 포인터로 가리키게 될 것이다.

<연결 리스트를 이용한 스택 ADT 구현>

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

class Stack:
    def __init__(self, item):
        self.last = Node(item, self.last)
        
     
    def push(self, item):
        item = self.last.item
        self.last = self.last.next
        return item
        

• 먼저 연결 리스트를 담을 Node 클래스부터 정의한다.

• 다음으로 초기화 하뭇 init()에서 노드의 값은 item, 다음 노드를 가리키는 포인터는 next로 정의한다.

• 그리고 스택의 연산인 push( )와 pop( )을 담은 stack 클래스를 다음과 같이 정의한다.

  • push( ): 연결 리스트에 요소를 추가하면서 가장 마지막 값을 next로 지정하고, 포인터인 last는 가장 마지막으로 이동시킨다.

  • pop( ): 가장 마지막 아이템을 끄집어내고 last 포인터를 한 칸 앞으로 전진시킨다. 즉, 이전에 추가된 값을 가리키게 한다.

 stack = Stack()
 stack.push(1)
 stack.push(2)
 stack.push(3)
 stack.push(4)
 stack.push(5)
 

>>> for _ in range(5):
...     print(stack.pop())
...
5
4
3
2
1

```'