Python Language
스택
수색…
소개
스택은 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 개체를 사용하면 스택을 비우고 확인하는 등의 도우미 메서드를 사용하여 완전하게 기능하는 제네릭 스택을 만들 수 있습니다. list 을 Stack 사용하려면 공식 파이썬 문서를 확인 하십시오 .
#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()