Beberapa cara untuk melaksanakan timbunan dalam Python dan kelebihan dan kekurangannya

​​Untuk mengetahui lebih lanjut tentang sumber terbuka, sila lawati: ​​

​​Komuniti Perisian Asas Sumber Terbuka 51CTO​ ​

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

1. Konsep tindanan

Timbunan terdiri daripada satu Koleksi objek bersiri yang disusun mengikut objek Operasi penambahan dan pemadaman objek ini mengikut prinsip "Masuk Dahulu Terakhir" (LIFO).

Hanya satu objek boleh dimasukkan ke dalam tindanan pada bila-bila masa, tetapi pemerolehan atau pemadaman hanya boleh dilakukan di bahagian atas tindanan. Sebagai contoh, dalam timbunan buku, satu-satunya buku dengan kulitnya terdedah ialah buku yang berada di bahagian atas Untuk pergi ke buku lain, anda hanya boleh mengalih keluar buku di atas, seperti yang ditunjukkan dalam gambar:

Pelayar web menyimpan URL yang dilawati baru-baru ini dalam timbunan . Setiap kali pelawat pengguna melawat tapak web baharu, URL tapak web baharu itu ditolak ke bahagian atas timbunan. Dengan cara ini, apabila kita mengklik butang "Kembali" dalam penyemak imbas (atau tekan pintasan papan kekunci CTRL+Z, kebanyakan pintasan buat asal), URL yang paling baru dilawati boleh muncul untuk kembali ke keadaan penyemak imbas yang dilawati sebelum ini .
1. Editor teks sering menyediakan mekanisme "buat asal" untuk membatalkan operasi pengeditan terbaharu dan kembali ke keadaan sebelumnya. Operasi buat asal ini juga dicapai dengan menyimpan keadaan teks yang diubah dalam tindanan.
2. Pengurusan memori beberapa bahasa peringkat tinggi, tindanan JVM, tindanan Python juga digunakan untuk pengurusan memori, persekitaran masa jalan bagi ciri bahasa bersarang, dsb.
3. Menjejak ke belakang (bermain permainan, mencari laluan, senarai lengkap Carian)
4. digunakan dalam algoritma, seperti Menara Hanoi, traversal pokok, masalah histogram, dan juga digunakan dalam algoritma graf, seperti pengisihan topologi
5. Pemprosesan sintaks:

Ruang untuk parameter dan pembolehubah setempat dicipta secara dalaman menggunakan tindanan.
• Menyemak sintaks pengkompil untuk pemadanan pendakap
• Sokongan untuk rekursi
• Ungkapan seperti akhiran atau awalan dalam pengkompil

Timbunan(): Mencipta tindanan kosong, ia tidak memerlukan parameter dan akan mengembalikan tindanan kosong.
• tekan(e): Menambah elemen e ke bahagian atas tindanan S. Ia memerlukan parameter e dan tidak mempunyai nilai pulangan.
• pop(): Mengalih keluar elemen di bahagian atas tindanan. Ia tidak memerlukan parameter, tetapi akan mengembalikan elemen teratas dan mengubah suai kandungan tindanan.
• top(): Mengembalikan elemen atas tindanan, tetapi tidak mengalih keluar elemen atas tindanan; jika tindanan kosong, operasi ini akan beroperasi.
• is_empty(): Jika tindanan tidak mengandungi sebarang elemen, mengembalikan nilai Boolean True.
• size(): Mengembalikan data elemen dalam tindanan. Ia tidak memerlukan parameter dan mengembalikan integer. Dalam Python, ini boleh dicapai menggunakan kaedah khas __len__.

​ dipanggil aliran bawah. ​pop()​

​, yang boleh melaksanakan fungsi tindanan melalui beberapa kaedah terbina dalam: ​list​

Kaedah tambah digunakan untuk menambah elemen pada penghujung senarai Kaedah ini boleh mensimulasikan operasi push().
• Kaedah pop() digunakan untuk mensimulasikan operasi pop.
• Simulasikan operasi top() melalui L[-1].
• Simulasikan operasi isEmpty() dengan menilai len(L)==0.
• Laksanakan fungsi size() melalui fungsi len().

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

Jalankan program ini, hasilnya ialah:

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

Selain menggunakan hujung senarai sebagai bahagian atas tindanan, anda juga boleh menggunakan kepala senarai sebagai bahagian atas tindanan . Walau bagaimanapun, dalam kes ini, anda tidak boleh menggunakan kaedah pop() dan append() secara langsung, tetapi anda boleh mengakses elemen secara eksplisit dengan indeks 0, iaitu elemen pertama senarai, melalui kaedah pop() dan insert() . , kodnya adalah seperti berikut:

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

Walaupun kami telah mengubah pelaksanaan jenis data abstrak, kami telah mengekalkan ciri logiknya. Walau apa pun, walaupun kedua-dua kaedah melaksanakan tindanan, kaedah prestasinya adalah berbeza: kerumitan masa kaedah

• append()​ dan pop() adalah kedua-duanya *O(1), *operasi tahap malar
• Prestasi pelaksanaan kedua dihadkan oleh bilangan elemen dalam tindanan Ini kerana kerumitan masa sisipan(0)​ dan pop(0) ialah O(n). semakin perlahan ia menjadi. ​

4. Gunakan collections.deque untuk melaksanakan tindanan

Dalam Python, modul koleksi mempunyai struktur data baris gilir dua hujung, yang turut melaksanakan append() dan pop () Kaedah:

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

Mengapa anda memerlukan deque apabila anda mempunyai senarai?

Mungkin anda boleh melihat deque dan list itu beroperasi pada elemen dengan cara yang sama, jadi mengapa Python menambah struktur data deque pada senarai?

Itu kerana senarai dalam Python dibina dalam blok memori bersebelahan, bermakna unsur-unsur senarai disimpan betul-betul bersebelahan antara satu sama lain.

Ini sangat berguna untuk sesetengah operasi, seperti mengindeks senarai. Mendapatkan myList[3] adalah pantas kerana Python mengetahui dengan tepat di mana hendak mencarinya dalam ingatan. Susun atur memori ini juga membolehkan penghirisan berfungsi dengan baik pada senarai.

Susun atur memori senarai bersebelahan mungkin mengambil lebih banyak masa untuk .tambah() beberapa objek. Jika blok memori berterusan penuh, maka ia perlu mendapatkan blok memori lain dan menyalin keseluruhan blok memori terlebih dahulu Tindakan ini mungkin mengambil lebih masa daripada operasi .append() biasa.

Deque baris gilir dua hujung adalah berdasarkan senarai pautan dua kali. Dalam struktur senarai terpaut, setiap entri disimpan dalam blok memorinya sendiri dan mempunyai rujukan kepada entri seterusnya dalam senarai.

Begitu juga dengan senarai pautan berganda, kecuali setiap entri mempunyai rujukan kepada entri sebelumnya dan seterusnya dalam senarai. Ini memudahkan untuk menambah nod pada kedua-dua hujung senarai.

Untuk menambah entri baharu dalam struktur senarai terpaut, cuma tetapkan rujukan entri baharu untuk menghala ke bahagian atas timbunan semasa, kemudian arahkan bahagian atas timbunan ke entri baharu.

Walau bagaimanapun, masa menambah dan mengalih keluar masukan daripada timbunan ini memerlukan kos. Mendapatkan myDeque[3] adalah lebih perlahan daripada senarai kerana Python perlu melalui setiap nod senarai untuk mendapatkan elemen ketiga.

Nasib baik, anda jarang mahu mengindeks elemen secara rawak pada tindanan atau melakukan operasi penghirisan senarai. Kebanyakan operasi pada tindanan adalah tolak atau pop.

Jika kod anda tidak menggunakan benang, operasi constant-time .append() dan .pop() menjadikan deque pilihan yang lebih baik untuk melaksanakan tindanan Python.

5. Gunakan baris gilir.LifoQueue untuk melaksanakan tindanan

Timbunan Python juga sangat berguna dalam program berbilang benang Kami telah mempelajari kaedah senarai dan deque. Untuk sebarang struktur data yang boleh diakses oleh berbilang benang, kita tidak seharusnya menggunakan senarai dalam pengaturcaraan berbilang benang kerana senarai tidak selamat untuk benang. kaedah .append() dan .pop() deque adalah atom, bermakna ia tidak akan diganggu oleh benang yang berbeza.

Jadi semasa menggunakan deque boleh membina tindanan Python yang selamat untuk benang, berbuat demikian membuka diri anda kepada penyalahgunaan masa hadapan dan mewujudkan keadaan perlumbaan.

Baiklah, jika anda pengaturcaraan berbilang benang, anda tidak boleh menggunakan senarai sebagai timbunan, dan anda mungkin tidak mahu menggunakan deque sebagai timbunan, jadi bagaimana anda membina timbunan Python untuk program berulir?

Jawapannya terletak pada modul baris gilir: giliran.LifoQueue. Ingat bagaimana anda mengetahui bahawa timbunan beroperasi pada asas keluar masuk terakhir (LIFO)? Nah, itulah yang diwakili oleh bahagian "Lifo" LifoQueue.

Walaupun antara muka senarai dan deque adalah serupa, LifoQueue menggunakan .put() dan .get() untuk menambah dan mengalih keluar data daripada tindanan.

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

Atas ialah kandungan terperinci Beberapa cara untuk melaksanakan timbunan dalam Python dan kelebihan dan kekurangannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!