Several ways to implement stacks in Python and their advantages and disadvantages

​​To learn more about open source, please visit:​​

​​51CTO Open Source Basic Software Community ​​

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

1. The concept of stack

The stack consists of one A collection of series objects organized by objects. The addition and deletion operations of these objects follow a "Last In First Out" (LIFO) principle.

Only one object can be inserted into the stack at any time, but it can only be obtained or deleted at the top of the stack. For example, in a stack of books, the only book with its cover exposed is the one at the top. In order to get the other books, you can only remove the book on top, as shown in the picture:

Practical application of stack

In fact, many applications use stacks, such as:

1. The web browser stores the recently visited URLs in a stack. Whenever a user visitor visits a new website, the URL of the new website is pushed to the top of the stack. In this way, whenever we click the "Back" button in the browser (or press the keyboard shortcut CTRL Z, most undo shortcuts), we can pop up the most recently visited URL to return to the browsing state of its previous visit. .
2. Text editors usually provide an "undo" mechanism to cancel the most recent editing operation and return to the previous state. This undo operation is also achieved by saving the changed state of the text in a stack.
3. Memory management of some high-level languages, JVM stack, Python stack are also used for memory management, runtime environment of nested language features, etc.
4. Backtracking (playing games, finding paths, exhaustive Search)
5. Used in algorithms, such as Tower of Hanoi, tree traversal, histogram problems, and also used in graph algorithms, such as topological sorting
6. Syntax processing:

• The space for parameters and local variables is created internally using the stack.
• Compiler syntax checking for brace matching
• Support for recursion
• Expressions like suffixes or prefixes in the compiler

2. Abstract data type of stack

Any data structure is inseparable from the way of saving and obtaining data. As mentioned above, a stack is an ordered collection of elements, and additions, operations, and removals all occur. At the top of it (the top of the stack), its abstract data types include:

• Stack(): Creates an empty stack, it does not require parameters, and will return an empty stack.
• push(e): Adds an element e to the top of stack S. It requires a parameter e and has no return value.
• pop(): Removes the element at the top of the stack. It requires no parameters, but will return the top element and modify the contents of the stack.
• top(): Returns the element at the top of the stack, but does not remove the element at the top of the stack; if the stack is empty, this operation will operate.
• is_empty(): If the stack does not contain any elements, returns a Boolean value True.
• size(): Returns the data of the elements in the stack. It requires no parameters and returns an integer. In Python, this can be achieved using the special method __len__.

The size of the Python stack may be fixed, or there may be a dynamic implementation that allows the size to change. In the case of a fixed-size stack, attempting to add an element to an already full stack will result in a stack overflow exception. Likewise, attempting to remove an element from an already empty stack using a ​pop()​​ operation is called an underflow.

3. Use Python lists to implement stacks

When learning Python, you must have learned Python lists ​​list​​, which can be used through some built-in methods Implement the function of the stack:

• The append method is used to add an element to the end of the list. This method can simulate the push() operation.
• The pop() method is used to simulate pop operations.
• Simulate the top() operation through L[-1].
• Simulate the isEmpty() operation by judging len(L)==0.
• Implement the size() function through the len() function.

code show as below:

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()

Run this program, the result is:

Stack top element:Hello
Stack length:3
Stack popped item: Hello
Stack is empty? False
Stack is empty? True

In addition to using the end of the list as the top of the stack, you can also use the head of the list as the top of the stack. However, in this case, you cannot use the pop() and append() methods directly, but you can explicitly access the element with index 0, which is the first element of the list, through the pop() and insert() methods. , the code is as follows:

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

Although we have changed the implementation of the abstract data type, we have retained its logical characteristics. This ability embodies abstract thinking. No matter, although both methods implement stacks, their performance methods are different: the time complexity of

• append()​ and pop() methods are both *O(1), *Constant level operation
• The performance of the second implementation is limited by the number of elements in the stack. This is because the time complexity of insert(0)​ and pop(0) is O(n). The more elements, the slower it becomes. ​

4. Use collections.deque to implement the stack

In Python, the collections module has a double-ended queue data structure deque, which also implements append() and pop () Method:

>>> from collections import deque
>>> myStack = deque()
>>> myStack.append('Apple')
>>> myStack.append('Banana')
>>> myStack.append('Orange')
>>> 
>>> myStack
deque(['Apple', 'Banana', 'Orange'])
>>> myStack.pop()
'Orange'
>>> myStack.pop()
'Banana'
>>>
>>> len(myStack)
1
>>> myStack[0]
'Apple'
>>> myStack.pop()
'Apple'

>>>
>>> myStack.pop()
Traceback (most recent call last):
File "<pyshell#13>", line 1, in <module>
myStack.pop()
IndexError: pop from an empty deque
>>>

Why do we need deque when we have a list?

Maybe you can see that deque and list have similar operations on elements, so why does Python add a deque data structure to lists?

That's because lists in Python are built in contiguous blocks of memory, which means that the elements of the list are stored close to each other.

This is very effective for some operations, such as indexing a list. Getting myList[3] is fast because Python knows exactly where to look for it in memory. This memory layout also allows slicing to work well on lists.

The memory layout of contiguous lists is that it may take more time to .append() some objects. If the continuous memory block is full, then it will need to obtain another memory block and copy the entire memory block first. This action may take more time than the normal .append() operation.

The double-ended queue deque is based on a double-linked list. In a linked list structure, each entry is stored in its own block of memory and has a reference to the next entry in the list.

The same is true for a doubly linked list, except that each entry has a reference to the previous and following entries in the list. This makes it easy to add nodes to both ends of the list.

To add a new entry to a linked list structure, just set the reference of the new entry to point to the top of the current stack, and then point the top of the stack to the new entry.

However, this time of constantly adding and removing entries from the stack comes at a cost. Getting myDeque[3] is slower than a list because Python needs to walk through each node of the list to get the third element.

Fortunately, you rarely want to randomly index elements on the stack or perform list slicing operations. Most operations on the stack are push or pop.

If your code does not use threads, the constant-time .append() and .pop() operations make deque a better choice for implementing the Python stack.

5. Use queue.LifoQueue to implement the stack

The Python stack is also very useful in multi-threaded programs. We have already learned the two methods of list and deque. For any data structure that can be accessed by multiple threads, we should not use list in multi-threaded programming because lists are not thread-safe. deque's .append() and .pop() methods are atomic, meaning they will not be interfered by different threads.

So, while it is possible to build a thread-safe Python stack using deque, doing so opens yourself up to future misuse and creates race conditions.

Okay, if you are multi-threaded programming, you can't use list as a stack, and you probably don't want to use deque as a stack, so how do you build a Python stack for a threaded program?

The answer lies in the queue module: queue.LifoQueue. Remember how you learned that the stack operates on a last-in-first-out (LIFO) basis? Well, that's what the "Lifo" part of LifoQueue represents.

Although the interfaces of list and deque are similar, LifoQueue uses .put() and .get() to add and remove data from the stack.

>>> 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​​。

The above is the detailed content of Several ways to implement stacks in Python and their advantages and disadvantages. For more information, please follow other related articles on the PHP Chinese website!