logo

TechCodeview

Python의 스택

ㅏ 스택 항목을 저장하는 선형 데이터 구조입니다. 후입선출(LIFO) 또는 FILO(선입/후출) 방식. 스택에서는 한쪽 끝에 새 요소가 추가되고 해당 끝에서만 요소가 제거됩니다. 삽입 및 삭제 작업을 흔히 푸시(Push) 및 팝(Pop)이라고 합니다.

파이썬으로 스택



스택과 관련된 기능은 다음과 같습니다.

  • 비어 있는() – 스택이 비어 있는지 여부를 반환 – 시간 복잡도: O(1)
  • 크기() – 스택의 크기를 반환합니다. – 시간 복잡도: O(1)
  • 상단() / 엿보기() – 스택의 최상위 요소에 대한 참조를 반환합니다. – 시간 복잡도: O(1)
  • 푸시(a) – 스택 맨 위에 요소 'a'를 삽입합니다. – 시간 복잡도: O(1)
  • 팝() – 스택의 최상위 요소를 삭제합니다. – 시간 복잡도: O(1)

구현:

Python에서 스택을 구현하는 방법에는 여러 가지가 있습니다. 이 문서에서는 Python 라이브러리의 데이터 구조와 모듈을 사용하여 스택을 구현하는 방법을 다룹니다.
Python의 스택은 다음 방법을 사용하여 구현할 수 있습니다.

  • 목록
  • Collections.deque
  • 큐.Lifo큐

목록을 사용한 구현:

Python에 내장된 데이터 구조 목록을 스택으로 사용할 수 있습니다. push() 대신, add()를 사용하여 스택 상단에 요소를 추가하고, pop()은 LIFO 순서로 요소를 제거합니다.
불행하게도 이 목록에는 몇 가지 단점이 있습니다. 가장 큰 문제는 성장함에 따라 속도 문제가 발생할 수 있다는 것입니다. 목록의 항목은 메모리에서 서로 옆에 저장됩니다. 스택이 현재 보유하고 있는 메모리 블록보다 커지면 Python은 일부 메모리 할당을 수행해야 합니다. 이로 인해 일부 추가() 호출이 다른 호출보다 훨씬 오래 걸릴 수 있습니다.



파이썬 
# Python program to # demonstrate stack implementation # using list stack = [] # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>
산출 
Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: []>

collections.deque를 사용한 구현:

Python 스택은 컬렉션 모듈의 deque 클래스를 사용하여 구현할 수 있습니다. Deque는 O(n)을 제공하는 목록에 비해 추가 및 팝 작업에 O(1) 시간 복잡도를 제공하므로 컨테이너의 양쪽 끝에서 더 빠른 추가 및 팝 작업이 필요한 경우 목록보다 Deque가 선호됩니다. 시간 복잡도.

목록에 표시된 것과 동일한 deque 메소드(append() 및 pop())가 사용됩니다.

파이썬 
# Python program to # demonstrate stack implementation # using collections.deque from collections import deque stack = deque() # append() function to push # element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop # element from stack in # LIFO order print('
Elements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('
Stack after elements are popped:') print(stack) # uncommenting print(stack.pop()) # will cause an IndexError # as the stack is now empty>
산출 
Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([])>

큐 모듈을 이용한 구현

대기열 모듈에는 기본적으로 스택인 LIFO 대기열도 있습니다. put() 함수를 사용하여 데이터를 Queue에 삽입하고 get()을 사용하여 Queue에서 데이터를 가져옵니다.



이 모듈에서는 다양한 기능을 사용할 수 있습니다:

  • 최대 크기 – 대기열에 허용되는 항목 수.
  • 비어 있는() – 대기열이 비어 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
  • 가득한() – 있는 경우 True를 반환합니다. 최대 크기 대기열에 있는 항목입니다. 대기열이 maxsize=0(기본값)으로 초기화된 경우 full()은 결코 True를 반환하지 않습니다.
  • 얻다() – 대기열에서 항목을 제거하고 반환합니다. 대기열이 비어 있으면 항목을 사용할 수 있을 때까지 기다립니다.
  • get_nowait() – 즉시 사용 가능한 항목이 있으면 항목을 반환하고, 그렇지 않으면 QueueEmpty를 발생시킵니다.
  • 넣다(항목) – 항목을 대기열에 넣습니다. 대기열이 가득 찬 경우 항목을 추가하기 전에 여유 슬롯을 사용할 수 있을 때까지 기다리십시오.
  • put_nowait(항목) – 차단하지 않고 항목을 대기열에 넣습니다. 즉시 사용 가능한 여유 슬롯이 없으면 QueueFull을 발생시킵니다.
  • 큐사이즈() – 대기열에 있는 항목 수를 반환합니다.
파이썬 
# Python program to # demonstrate stack implementation # using queue module from queue import LifoQueue # Initializing a stack stack = LifoQueue(maxsize=3) # qsize() show the number of elements # in the stack print(stack.qsize()) # put() function to push # element in the stack stack.put('a') stack.put('b') stack.put('c') print('Full: ', stack.full()) print('Size: ', stack.qsize()) # get() function to pop # element from stack in # LIFO order print('
Elements popped from the stack') print(stack.get()) print(stack.get()) print(stack.get()) print('
Empty: ', stack.empty())>
산출 
0 Full: True Size: 3 Elements popped from the stack c b a Empty: True>

단일 연결 리스트를 사용한 구현:

연결된 목록에는 일정한 시간에 실행되는 addHead(item) 및 RemoveHead() 두 가지 메서드가 있습니다. 이 두 가지 방법은 스택을 구현하는 데 적합합니다.

  • getSize() – 스택에 있는 항목 수를 가져옵니다.
  • 비었다() – 스택이 비어 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
  • 몰래 엿보다() – 스택의 맨 위 항목을 반환합니다. 스택이 비어 있으면 예외를 발생시킵니다.
  • 푸시(값) – 스택의 헤드에 값을 넣습니다.
  • 팝() – 스택 헤드의 값을 제거하고 반환합니다. 스택이 비어 있으면 예외를 발생시킵니다.

다음은 위의 접근 방식을 구현한 것입니다.

파이썬 
# Python program to demonstrate # stack implementation using a linked list. # node class class Node: def __init__(self, value): self.value = value self.next = None class Stack: # Initializing a stack. # Use a dummy node, which is # easier for handling edge cases. def __init__(self): self.head = Node('head') self.size = 0 # String representation of the stack def __str__(self): cur = self.head.next out = '' while cur: out += str(cur.value) + '->' cur = cur.next return out[:-2] # 스택의 현재 크기를 가져옵니다 def getSize(self): return self.size # 스택이 비어 있는지 확인 def isEmpty(self): return self.size = = 0 # 스택의 맨 위 항목을 가져옵니다 def peek(self): # 빈 스택을 엿보고 있는지 # 위생 검사합니다. if self.isEmpty(): return None return self.head.next.value # 값을 스택에 푸시합니다. def push(self, value): node = Node(value) node.next = self.head.next # 새 노드가 현재 헤드를 가리키도록 만듭니다. self.head.next = node #!!! # 헤드를 새 노드로 업데이트합니다. self.size += 1 # 스택에서 값을 제거하고 반환합니다. def pop(self): if self.isEmpty(): raise Exception('빈 스택에서 팝핑') Remove = self.head.next self.head.next = Remove.next #!!! Change self.size -= 1 return Remove.value # 드라이버 코드 if __name__ == '__main__': stack = Stack() for i in range(1, 11): stack.push(i) print(f' 스택: {stack}') for _ in range(1, 6): top_value = stack.pop() print(f'Pop: {top_value}') # 변수 이름 변경됨 print(f'Stack: { 스택}')>

산출 

Stack: 10->9->8->7->6->5->4->3->2->1 팝: 10 팝: 9 팝: 8 팝: 7 팝: 6 스택: 5->4->3->2->1>

스택의 장점:

  • 스택은 잘 정의된 작업 세트가 포함된 간단한 데이터 구조이므로 이해하고 사용하기 쉽습니다.
  • 스택은 요소를 추가하고 제거하는 데 효율적입니다. 이러한 작업의 시간 복잡도는 O(1)입니다.
  • 요소의 순서를 바꾸기 위해 스택 데이터 구조를 사용합니다.
  • 스택은 애플리케이션에서 실행 취소/다시 실행 기능을 구현하는 데 사용될 수 있습니다.

스택의 단점:

  • 스택의 크기 제한은 단점이며 가득 차면 스택에 더 이상 요소를 추가할 수 없습니다.
  • 스택은 최상위 요소 이외의 요소에 대한 빠른 액세스를 제공하지 않습니다.
  • 스택은 원하는 요소를 찾을 때까지 요소를 하나씩 팝해야 하기 때문에 효율적인 검색을 지원하지 않습니다.