(Python) 스택

스택 : 후입선출 ex)팬케이크 먹는거/ 박스 쌓기     O(1)

 

python 에서 큐 구현은 deque 라이브러리 사용  데이터 삭제시 queue.popleft 사용

 

 

Stacks

자료 를 보관할 수 있는 (선형(일렬로 늘어선)) 구조  후입(push)선출(pop) 구조

비어 있는 스택에서 pop > stack underflow

꽉 찬 스택에 push > stack overflow

 

구현 방법

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

1. Array

>Python 리스트와 메서드들을 이용

# 괄호 문제

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():
                return False
            else:
                t = S.pop()
                if t!= match[c]:
                    return False
    return S.isEmpty()

print(solution("[(A + B) * C]"))

2. L inked List

> 양방향 링크드리스트 이용

 

class LinkedListStack:

    def __init__(self):
        self.data = DoublyLinkedList()

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

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

    def push(self, item):
        node = Node(item)
        self.data.insertAt(self.size() + 1, node)

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

    def peek(self):
        return self.data.getAt(self.size()).data

 

스택 응용

중위 표기법: 연산자가(+,-,*,//) 피연산자(숫자)들 사이에 위치

(A+B) *(C+D)

 

후위 표기법: 연산자가 피 연산자들 뒤에 위치

AB + CD+ *

 

관련문제 : https://windy7271.tistory.com/manage/newpost/345?type=post&returnURL=https%3A%2F%2Fwindy7271.tistory.com%2Fmanage%2Fposts%3Fcategory%3D1042709 

https://windy7271.tistory.com/manage/newpost/345?returnURL=https%3A%2F%2Fwindy7271.tistory.com%2Fmanage%2Fposts%3Fcategory%3D1042709&type=post