Python에서 스택을 구현하는 여러 가지 방법과 그 장점과 단점

​​오픈 소스에 대해 자세히 알아보려면 다음을 방문하세요.​​

​​51CTO 오픈 소스 기본 소프트웨어 커뮤니티​​

​​https://ost.51cto.com​ ​

1. 스택의 개념

스택은 일련의 객체로 구성된 모음입니다. 이러한 객체의 추가 및 삭제 작업은 "LIFO(Last In First Out)" 원칙을 따릅니다.

스택에는 언제든지 하나의 객체만 삽입할 수 있지만, 획득이나 삭제는 스택 상단에서만 수행할 수 있습니다. 예를 들어, 책으로 구성된 더미에서 표지가 노출된 유일한 책은 다른 책으로 이동하려면 그림과 같이 맨 위에 있는 책만 제거할 수 있습니다.

스택의 실제 응용

다음과 같은 인터넷의 많은 응용 프로그램이 스택을 사용합니다.

1. 웹 브라우저는 최근 방문한 URL을 스택에 저장합니다. 사용자 방문자가 새 웹사이트를 방문할 때마다 새 웹사이트의 URL이 스택 맨 위로 푸시됩니다. 이러한 방식으로 브라우저에서 "뒤로" 버튼을 클릭할 때마다(또는 대부분의 실행 취소 단축키인 키보드 단축키 CTRL+Z를 누를 때마다) 가장 최근에 방문한 URL이 팝업되어 이전에 방문한 브라우저로 돌아갈 수 있습니다. 상태.
2. 텍스트 편집기는 가장 최근의 편집 작업을 취소하고 이전 상태로 돌아갈 수 있는 "실행 취소" 메커니즘을 제공하는 경우가 많습니다. 이 실행 취소 작업은 텍스트의 변경된 상태를 스택에 저장하여 수행됩니다.
3. 일부 고급 언어의 메모리 관리, JVM 스택, Python 스택은 메모리 관리, 중첩 언어 기능의 런타임 환경 등에 사용됩니다.
4. 역추적(게임 플레이, 경로 찾기, 철저한 검색)
5. 알고리즘에 사용됩니다. , 하노이 타워, 트리 순회, 히스토그램 문제와 같은 위상 정렬과 같은 그래프 알고리즘에도 사용됩니다.
6. 구문 처리:

• 매개변수 및 지역 변수를 위한 공간은 스택을 사용하여 내부적으로 생성됩니다.
• 중괄호 일치를 위한 컴파일러의 구문 검사
• 재귀 지원
• 컴파일러의 접미사 또는 접두사와 같은 표현

2. 스택의 추상 데이터 유형

모든 데이터 구조는 분리 불가능합니다. 데이터를 저장하고 얻는 방법. 위에서 언급했듯이 스택은 추가, 작업 및 제거가 모두 스택 상단(스택 상단)에서 발생하는 순서가 지정된 요소 모음입니다. 그런 다음 추상 데이터 유형은 다음과 같습니다.

• Stack(): 빈 스택의 경우 매개변수가 필요하지 않으며 빈 스택을 반환합니다.
• push(e): 스택 S의 맨 위에 요소 e를 추가합니다. 매개변수 e가 필요하며 반환 값이 없습니다.
• pop(): 스택 맨 위에 있는 요소를 제거합니다. 매개변수는 필요하지 않지만 맨 위 요소를 반환하고 스택의 내용을 수정합니다.
• top(): 스택 맨 위에 있는 요소를 반환하지만 스택이 비어 있으면 이 작업이 수행됩니다.
• is_empty(): 스택에 요소가 포함되어 있지 않으면 부울 값 True를 반환합니다.
• size(): 스택에 있는 요소의 데이터를 반환합니다. 매개변수가 필요하지 않으며 정수를 반환합니다. Python에서는 특수 메서드 __len__을 사용하여 이를 수행할 수 있습니다.

Python 스택의 크기는 고정되어 있을 수도 있고, 크기 변경을 허용하는 동적 구현이 있을 수도 있습니다. 고정 크기 스택의 경우 이미 가득 찬 스택에 요소를 추가하려고 하면 스택 오버플로 예외가 발생합니다. 마찬가지로, 이미 비어 있는 스택에서 요소를 제거하려고 하면 ​pop()​​ 이러한 상황을 언더플로우라고 합니다. ​pop()​​ 操作这种情况被称为下溢。

三、用 Python 的列表实现栈

在学习 Python 的时候，一定学过 Python 列表 ​​list​

3. Python 목록을 사용하여 스택 구현

• Python을 배울 때 Python 목록을 배웠어야 합니다. ​​list​​, 내장된 메소드를 통해 스택 기능을 실현할 수 있습니다:
• append 메소드를 사용하여 요소를 목록 끝에 추가하면 이 메서드는 push() 작업을 시뮬레이션할 수 있습니다.
• pop() 메서드는 팝 작업을 시뮬레이션하는 데 사용됩니다.
• L[-1]을 통해 top() 작업을 시뮬레이션합니다.
• len(L)==0으로 판단하여 isEmpty() 작업을 시뮬레이션합니다.

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

추상적인 데이터 유형의 구현을 변경했지만 이 기능은 추상적인 사고를 구현합니다. 그럼에도 불구하고 두 메서드 모두 스택을 구현하지만 성능 방법은 다릅니다.

• append()​ 및 pop() 메서드의 시간 복잡도는 모두 *O(1), *상수 수준 작업
• 두 번째의 성능 구현은 스택의 요소 수에 의해 제한됩니다. 이는 insert(0)​ 및 pop(0)의 시간 복잡도가 O(n)이고 요소가 많을수록 속도가 느려지기 때문입니다. ​

4. collections.deque를 사용하여 스택 구현

Python에서 collections 모듈에는 이중 끝형 큐 데이터 구조 deque가 있습니다. 이 데이터 구조는 또한append() 및 pop() 메서드를 구현합니다. 왜 목록에는 여전히 deque가 필요합니까?

deque와 list가 같은 방식으로 요소에 대해 작동하는 것을 볼 수 있는데 Python이 deque 데이터 구조를 목록에 추가하는 이유는 무엇입니까?

Python의 목록은 연속적인 메모리 블록으로 구성되어 있기 때문입니다. 즉, 목록의 요소가 서로 바로 옆에 저장된다는 의미입니다.

이 기능은 목록 색인 생성과 같은 일부 작업에 적합합니다. myList[3]을 얻는 것은 Python이 메모리에서 찾을 위치를 정확히 알고 있기 때문에 빠릅니다. 이 메모리 레이아웃을 사용하면 슬라이싱이 목록에서 잘 작동할 수도 있습니다.

목록의 연속 메모리 레이아웃은 일부 객체를 .append()하는 데 더 많은 시간이 걸릴 수 있습니다. 연속 메모리 블록이 가득 차면 다른 메모리 블록을 확보하고 전체 메모리 블록을 먼저 복사해야 합니다. 이 작업은 일반적인 .append() 작업보다 시간이 더 걸릴 수 있습니다.

이중 끝 큐 데크는 이중 연결 목록을 기반으로 합니다. 연결된 목록 구조에서 각 항목은 자체 메모리 블록에 저장되며 목록의 다음 항목에 대한 참조를 갖습니다.

각 항목이 목록의 이전 항목과 다음 항목에 대한 참조를 갖는다는 점을 제외하면 이중 연결 목록에도 동일하게 적용됩니다. 이렇게 하면 목록의 양쪽 끝에 노드를 쉽게 추가할 수 있습니다.

연결된 목록 구조에 새 항목을 추가하려면 새 항목의 참조가 현재 스택의 상단을 가리키도록 설정한 다음 스택의 상단이 새 항목을 가리키도록 설정하세요.

그러나 스택에서 항목을 지속적으로 추가하고 제거하는 데는 비용이 듭니다. myDeque[3]을 얻는 것은 목록보다 느립니다. Python이 세 번째 요소를 얻기 위해 목록의 각 노드를 통과해야 하기 때문입니다.

다행히도 스택의 요소를 무작위로 인덱싱하거나 목록 분할 작업을 수행하고 싶은 경우는 거의 없습니다. 스택의 대부분의 작업은 푸시 또는 팝입니다.

코드에서 스레드를 사용하지 않는 경우 상수 시간 .append() 및 .pop() 작업을 사용하면 Deque가 Python 스택 구현에 더 나은 선택이 됩니다.

5. queue.LifoQueue를 사용하여 스택 구현

Python 스택은 다중 스레드 프로그램에서도 매우 유용합니다. 우리는 이미 list와 deque의 두 가지 방법을 배웠습니다. 여러 스레드에서 액세스할 수 있는 모든 데이터 구조의 경우 목록은 스레드로부터 안전하지 않기 때문에 다중 스레드 프로그래밍에서 목록을 사용해서는 안 됩니다. deque의 .append() 및 .pop() 메서드는 원자적이므로 다른 스레드의 간섭을 받지 않습니다.

따라서 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。

​​想了解更多关于开源的内容，请访问：​​

​​51CTO 开源基础软件社区​​

​​https://ost.51cto.com​​。

위 내용은 Python에서 스택을 구현하는 여러 가지 방법과 그 장점과 단점의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!