수색…


소개

스택은 LIFO (last-in-first-out) 원리에 따라 삽입 및 제거되는 객체의 컨테이너입니다. 푸시 다운 스택에서는 두 가지 작업 만 허용됩니다. 항목을 스택으로 밀어 넣고 항목을 스택 밖으로 팝합니다 . 스택은 제한된 액세스 데이터 구조입니다. 요소는 맨 위에서 스택에 추가 및 제거 할 수 있습니다 . 스택의 구조적 정의는 다음과 같습니다. 스택은 비어 있거나 스택과 상단으로 구성됩니다.

통사론

  • stack = [] # 스택을 만듭니다.
  • stack.append (object) # 스택 맨 위에 객체를 추가합니다.
  • stack.pop () -> object # 스택에서 최상위 객체를 반환하고 제거합니다.
  • list [-1] -> object # 맨 위의 객체를 지우지 않고 엿보기

비고

위키 백과에서 :

컴퓨터 과학에서 스택 은 요소를 컬렉션에 추가하는 push 와 아직 제거되지 않은 가장 최근에 추가 된 요소를 제거하는 pop의 두 가지 기본 연산으로 요소 컬렉션으로 사용되는 추상 데이터 유형입니다.

요소가 액세스되는 방식으로 인해 스택은 LIFO ( Last-In, First-Out ) 스택 이라고도합니다.

파이썬에서는 pop() 과 push append() 를 스택으로 사용하여 append() pop() 를 pop 연산으로 사용할 수 있습니다. 두 연산은 일정 시간 O (1)에서 실행됩니다.

파이썬의 deque 데이터 구조는 스택으로도 사용될 수 있습니다. deque 는 목록과 비교하여 양쪽 끝에서 일정한 시간 복잡성으로 푸시 및 팝 작업을 허용합니다.

List 객체를 사용하여 Stack 클래스 만들기

list 개체를 사용하면 스택을 비우고 확인하는 등의 도우미 메서드를 사용하여 완전하게 기능하는 제네릭 스택을 만들 수 있습니다. listStack 사용하려면 공식 파이썬 문서를 확인 하십시오 .

#define a stack class
class Stack:
    def __init__(self):
        self.items = []
    
    #method to check the stack is empty or not
    def isEmpty(self):
        return self.items == []
    
    #method for pushing an item 
    def push(self, item):
        self.items.append(item)

    #method for popping an item 
    def pop(self):
        return self.items.pop()
    
    #check what item is on top of the stack without removing it
    def peek(self):
        return self.items[-1]

    #method to get the size
    def size(self):
        return len(self.items)

    #to view the entire stack
    def fullStack(self):
        return self.items

예제 실행 :

stack = Stack()
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())
print('Pushing integer 1')
stack.push(1)
print('Pushing string "Told you, I am generic stack!"')
stack.push('Told you, I am generic stack!')
print('Pushing integer 3')
stack.push(3)
print('Current stack:', stack.fullStack())
print('Popped item:', stack.pop())
print('Current stack:', stack.fullStack())
print('Stack empty?:', stack.isEmpty())

산출:

Current stack: []
Stack empty?: True
Pushing integer 1
Pushing string "Told you, I am generic stack!"
Pushing integer 3
Current stack: [1, 'Told you, I am generic stack!', 3]
Popped item: 3
Current stack: [1, 'Told you, I am generic stack!']
Stack empty?: False

괄호 파싱

스택은 종종 구문 분석에 사용됩니다. 간단한 구문 분석 작업은 괄호 문자열이 일치하는지 확인하는 것입니다.

예를 들어, 외부 및 내부 대괄호가 쌍을 이루기 때문에 문자열 ([]) 이 일치합니다. ()<>) 과 일치하지 않고, 마지막으로 인해 ) 더 파트너가 없다. ([)] 도 일치하지 않습니다. 왜냐하면 쌍은 완전히 다른 쌍 내부 또는 외부에 있어야하기 때문입니다.

def checkParenth(str):
    stack = Stack()
    pushChars, popChars = "<({[", ">)}]"
    for c in str:
        if c in pushChars:
            stack.push(c)
        elif c in popChars:
            if stack.isEmpty():
                return False
            else:
                stackTop = stack.pop()
                # Checks to see whether the opening bracket matches the closing one
                balancingBracket = pushChars[popChars.index(c)]
                if stackTop != balancingBracket:
                    return False
        else:
            return False

    return not stack.isEmpty()


Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow