오픈 소스에 대해 자세히 알아보려면 다음을 방문하세요.
스택은 일련의 객체로 구성된 모음입니다. 이러한 객체의 추가 및 삭제 작업은 "LIFO(Last In First Out)" 원칙을 따릅니다.
스택에는 언제든지 하나의 객체만 삽입할 수 있지만, 획득이나 삭제는 스택 상단에서만 수행할 수 있습니다. 예를 들어, 책으로 구성된 더미에서 표지가 노출된 유일한 책은 다른 책으로 이동하려면 그림과 같이 맨 위에 있는 책만 제거할 수 있습니다.
다음과 같은 인터넷의 많은 응용 프로그램이 스택을 사용합니다.
모든 데이터 구조는 분리 불가능합니다. 데이터를 저장하고 얻는 방법. 위에서 언급했듯이 스택은 추가, 작업 및 제거가 모두 스택 상단(스택 상단)에서 발생하는 순서가 지정된 요소 모음입니다. 그런 다음 추상 데이터 유형은 다음과 같습니다.
Python 스택의 크기는 고정되어 있을 수도 있고, 크기 변경을 허용하는 동적 구현이 있을 수도 있습니다. 고정 크기 스택의 경우 이미 가득 찬 스택에 요소를 추가하려고 하면 스택 오버플로 예외가 발생합니다. 마찬가지로, 이미 비어 있는 스택에서 요소를 제거하려고 하면 pop() 이러한 상황을 언더플로우라고 합니다. pop() 操作这种情况被称为下溢。
在学习 Python 的时候，一定学过 Python 列表 list
list, 내장된 메소드를 통해 스택 기능을 실현할 수 있습니다: len() 함수를 통해 size() 함수를 구현합니다. 
class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.append(e)
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop()
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[-1]# the last item in the list
arrayStack = ArrayStack()
arrayStack.push("Python")
arrayStack.push("Learning")
arrayStack.push("Hello")
print("Stack top element: ", arrayStack.top())
print("Stack length: ", arrayStack.size())
print("Stack popped item: %s" % arrayStack.pop())
print("Stack is empty?", arrayStack.is_empty())
arrayStack.pop()
arrayStack.pop()
print("Stack is empty?", arrayStack.is_empty())
# arrayStack.pop()이 프로그램을 실행하면 결과는 다음과 같습니다.
Stack top element:Hello Stack length:3 Stack popped item: Hello Stack is empty? False Stack is empty? True
목록의 끝을 스택의 맨 위로 사용하는 것 외에도 목록의 헤드를 스택의 맨 위로 사용할 수도 있습니다. 단, 이 경우 pop(), add() 메소드를 직접 사용할 수는 없으나, pop(), insert() 메소드를 통해 목록의 첫 번째 요소인 인덱스 0의 요소에 명시적으로 접근할 수 있다. . , 코드는 다음과 같습니다.
class ArrayStack:
""" 通过 Python 列表实现 LIFO 栈"""
def __init__(self):
self._data = []
def size(self):
""" return the number of elements in the stack"""
return len(self._data)
def is_empty(self):
""" return True if the stack is empty"""
return len(self._data) == 0
def push(self, e):
""" add element e to the top of the stack"""
self._data.insert(0, e)
def pop(self):
""" remove and return the element from the top of the stack
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data.pop(0)
def top(self):
"""return the top of the stack
Raise Empty exception if the stack is empty
"""
if self.is_empty():
raise Exception('Stack is empty')
return self._data[0]# the last item in the list추상적인 데이터 유형의 구현을 변경했지만 이 기능은 추상적인 사고를 구현합니다. 그럼에도 불구하고 두 메서드 모두 스택을 구현하지만 성능 방법은 다릅니다.
Python에서 collections 모듈에는 이중 끝형 큐 데이터 구조 deque가 있습니다. 이 데이터 구조는 또한append() 및 pop() 메서드를 구현합니다. 왜 목록에는 여전히 deque가 필요합니까?
Python의 목록은 연속적인 메모리 블록으로 구성되어 있기 때문입니다. 즉, 목록의 요소가 서로 바로 옆에 저장된다는 의미입니다.
이 기능은 목록 색인 생성과 같은 일부 작업에 적합합니다. myList[3]을 얻는 것은 Python이 메모리에서 찾을 위치를 정확히 알고 있기 때문에 빠릅니다. 이 메모리 레이아웃을 사용하면 슬라이싱이 목록에서 잘 작동할 수도 있습니다.
목록의 연속 메모리 레이아웃은 일부 객체를 .append()하는 데 더 많은 시간이 걸릴 수 있습니다. 연속 메모리 블록이 가득 차면 다른 메모리 블록을 확보하고 전체 메모리 블록을 먼저 복사해야 합니다. 이 작업은 일반적인 .append() 작업보다 시간이 더 걸릴 수 있습니다.
이중 끝 큐 데크는 이중 연결 목록을 기반으로 합니다. 연결된 목록 구조에서 각 항목은 자체 메모리 블록에 저장되며 목록의 다음 항목에 대한 참조를 갖습니다.
각 항목이 목록의 이전 항목과 다음 항목에 대한 참조를 갖는다는 점을 제외하면 이중 연결 목록에도 동일하게 적용됩니다. 이렇게 하면 목록의 양쪽 끝에 노드를 쉽게 추가할 수 있습니다.
연결된 목록 구조에 새 항목을 추가하려면 새 항목의 참조가 현재 스택의 상단을 가리키도록 설정한 다음 스택의 상단이 새 항목을 가리키도록 설정하세요.
그러나 스택에서 항목을 지속적으로 추가하고 제거하는 데는 비용이 듭니다. myDeque[3]을 얻는 것은 목록보다 느립니다. Python이 세 번째 요소를 얻기 위해 목록의 각 노드를 통과해야 하기 때문입니다.
다행히도 스택의 요소를 무작위로 인덱싱하거나 목록 분할 작업을 수행하고 싶은 경우는 거의 없습니다. 스택의 대부분의 작업은 푸시 또는 팝입니다.
코드에서 스레드를 사용하지 않는 경우 상수 시간 .append() 및 .pop() 작업을 사용하면 Deque가 Python 스택 구현에 더 나은 선택이 됩니다.
5. queue.LifoQueue를 사용하여 스택 구현
따라서 deque를 사용하면 스레드로부터 안전한 Python 스택을 구축할 수 있지만 그렇게 하면 향후 오용에 대한 위험이 생기고 경쟁 조건이 발생하게 됩니다.
좋아요, 멀티 스레드 프로그래밍을 한다면 list를 스택으로 사용할 수 없고 deque를 스택으로 사용하고 싶지 않을 것입니다. 그렇다면 스레드 프로그램용 Python 스택을 어떻게 구축합니까?
답은 대기열 모듈인 queue.LifoQueue에 있습니다. 스택이 LIFO(후입선출) 원칙에 따라 작동한다는 것을 어떻게 배웠는지 기억하시나요? 음, 이것이 바로 LifoQueue의 "Lifo" 부분이 나타내는 것입니다.
list와 deque의 인터페이스는 유사하지만 LifoQueue는 .put() 및 .get()을 사용하여 스택에서 데이터를 추가하고 제거합니다.
>>> from queue import LifoQueue
>>> stack = LifoQueue()
>>> stack.put('H')
>>> stack.put('E')
>>> stack.put('L')
>>> stack.put('L')
>>> stack.put('O')
>>> stack
<queue.LifoQueue object at 0x00000123159F7310>
>>>
>>> stack.get()
'O'
>>> stack.get()
'L'
>>> stack.empty()
False
>>> stack.qsize()
3
>>> stack.get()
'L'
>>> stack.get()
'E'
>>> stack.qsize()
1
>>> stack.get()
'H'
>>> stack.get_nowait()
Traceback (most recent call last):
File "<pyshell#31>", line 1, in <module>
stack.get_nowait()
_queue.Empty
>>>
>>> stack.put('Apple')
>>> stack.get_nowait()
'Apple'与 deque 不同，LifoQueue 被设计为完全线程安全的。它的所有方法都可以在线程环境中安全使用。它还为其操作添加了可选的超时功能，这在线程程序中经常是一个必须的功能。
然而，这种完全的线程安全是有代价的。为了实现这种线程安全，LifoQueue 必须在每个操作上做一些额外的工作，这意味着它将花费更长的时间。
通常情况下，这种轻微的减速对你的整体程序速度并不重要，但如果你已经测量了你的性能，并发现你的堆栈操作是瓶颈，那么小心地切换到 deque 可能是值得做的。
一般来说，如果你不使用多线程，你应该使用 deque。如果你使用多线程，那么你应该使用 LifoQueue，除非你已经测量了你的性能，发现 push 和 pop 的速度的小幅提升会带来足够的差异，以保证维护风险。
你可以对列表可能很熟悉，但需要谨慎使用它，因为它有可能存在内存重新分配的问题。deque 和 list 的接口是相同的，而且 deque 没有线程不安全问题。
本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中如何使用它的情况。在文章的中，介绍了 Python 中实现栈的三种不同方式，知道了 deque 对于非多线程程序是一个更好的选择，如果你要在多线程编程环境中使用栈的话，可以使用 LifoQueue。
위 내용은 Python에서 스택을 구현하는 여러 가지 방법과 그 장점과 단점의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
