Stack dalam Python: definisi, pelaksanaan dan contoh

Utama » Python » Stack dalam Python: definisi, pelaksanaan dan contoh

Susunan dalam Python adalah salah satu konsep teras yang terus muncul di mana-mana sebaik sahaja anda mula mencari di sebalik program sebenar – daripada panggilan fungsi, untuk membatalkan ciri dalam editor, kepada cara pelayar mengendalikan sejarah navigasi anda. Walaupun anda kebanyakannya menulis kod aplikasi peringkat tinggi, memahami cara tindanan berfungsi (dan cara melaksanakannya dengan betul dalam Python) memberi anda kelebihan yang serius apabila anda perlu menyahpepijat isu rumit atau mereka bentuk algoritma yang cekap.

Dalam panduan ini, kita akan menghuraikan apa itu tindanan, apa sebenarnya maksud "Masuk Terakhir, Keluar Pertama" dalam praktiknya, operasi yang harus disokong oleh setiap tindanan, dan cara melaksanakan tindanan dalam Python menggunakan alat yang berbeza seperti senarai, koleksi.deque, queue.LifoQueue dan senarai berpaut tunggal.Kita juga akan membincangkan tentang prestasi, tingkah laku memori, keselamatan thread dan senario dunia sebenar di mana tindanan merupakan struktur data yang tepat untuk dicapai.

Apakah itu timbunan dalam Python?

Tindanan ialah struktur data linear yang mengikuti peraturan Masuk Terakhir, Keluar Dahulu (LIFO): elemen terakhir yang anda tekan ke atas tindanan ialah elemen pertama yang keluar semula.Secara konseptual, anda boleh membayangkan timbunan pinggan, timbunan buku atau timbunan pakaian: anda hanya boleh menambah atau mengalih keluar barang dari atas, bukan dari tengah atau bawah.

Tingkah laku LIFO ini bermaksud apabila anda memasukkan (tolak) elemen, setiap elemen baharu berada di atas elemen sebelumnya, dan apabila anda mengalih keluar (tembak), anda sentiasa mengambil elemen yang paling baru ditambah.Anda tidak akan pernah "melangkau ke hadapan" untuk mencapai elemen ketiga atau keempat tanpa membuang elemen yang berada di atasnya.

Dalam Python, tindanan bukanlah jenis bernama terbina dalam dengan sendirinya; sebaliknya, kami melaksanakan tindanan di atas struktur data sedia ada seperti senarai, dekues, barisan LIFO atau senarai terpaut tersuai.Setiap pilihan mempunyai keseimbangannya sendiri dari segi prestasi, penggunaan memori dan keselamatan thread.

Dua operasi asas pada mana-mana tindanan ialah push dan pop, tetapi pelaksanaan praktikal sering mendedahkan beberapa lagi pembantu seperti peek (atau top), size dan empty checksOperasi tambahan ini menjadikan penggunaan tindanan dalam aplikasi sebenar lebih mudah.

Sebelum mendalami kod, ingat satu sifat utama: tindanan yang dilaksanakan dengan baik akan melaksanakan operasi push dan pop dalam masa yang tetap, dicatatkan sebagai O(1), tanpa mengira berapa banyak elemen yang disimpan.Prestasi yang boleh diramalkan merupakan salah satu sebab utama tindanan digunakan secara meluas dalam algoritma dan sistem peringkat rendah.

Operasi dan tingkah laku tindanan teras

Setiap susunan yang boleh digunakan dalam Python, tanpa mengira pelaksanaan yang mendasarinya, berkisar pada segelintir operasi biasa yang menentukan kelakuannyaMemahami perkara ini adalah jauh lebih penting daripada menghafal nama kaedah tertentu dalam setiap pustaka.

Operasi klasik untuk memasukkan elemen dipanggil push: anda mengambil nilai dan meletakkannya di atas tindanan sedia adaSelepas satu push, elemen baharu menjadi elemen yang akan dikembalikan dahulu oleh operasi pop seterusnya.

Untuk mengalih keluar elemen, kita menggunakan pop, yang akan mengambil item paling atas daripada tindanan dan mengembalikannya.Jika tindanan kosong, pelaksanaan yang mantap harus sama ada menimbulkan ralat atau mengembalikan nilai tertentu yang menandakan ketiadaan elemen dengan jelas.

Kebanyakan pelaksanaan tindanan juga mendedahkan operasi peek atau top, yang membolehkan anda melihat elemen yang sedang berada di atas tanpa mengeluarkannya daripada tindanan.Ini amat berguna dalam algoritma yang perlu memeriksa nilai seterusnya tetapi masih mahu menyimpannya di sana untuk kemudian.

Dua operasi pembantu tambahan yang anda akan kerap temui ialah isempty (atau isEmpty) dan size, yang menyemak sama ada tindanan mempunyai sebarang elemen dan berapa banyak elemen yang terkandung di dalamnya.Dalam Python, kedua-dua semakan terbina dalam len() dan boolean boleh digunakan semula secara dalaman untuk melaksanakan pembantu ini dengan kod yang minimum.

Dari segi kerumitan masa, susunan yang direka bentuk dengan betul menjamin bahawa push, pop, peek dan isEmpty semuanya berjalan dalam masa yang tetap O(1), dan saiz boleh sama ada O(1) atau O(n) bergantung pada sama ada pelaksanaan menyimpan panjang sebagai medan yang berasinganYang penting, tindanan tidak menyokong akses rawak yang cekap ke kedudukan sewenang-wenangnya seperti tatasusunan.

Bila dan mengapa perlu menggunakan timbunan

Susunan akan bersinar apabila anda berurusan dengan proses yang kemudiannya perlu anda "undurkan" atau lalui dalam susunan terbalik yang tepat di mana langkah-langkah telah diambilSebarang situasi di mana anda secara semula jadi berfikir "Saya perlu membuat asal ini dari terakhir hingga pertama" adalah calon yang kuat untuk tindanan.

Satu analogi klasik dunia sebenar ialah membongkar mesin: anda menanggalkan skru dan bahagian dalam susunan tertentu, dan jika anda ingin memasangnya semula dengan betul, anda mesti meletakkannya semula dalam susunan yang bertentangan.Menyimpan bahagian-bahagian ini pada tindanan sangat sepadan dengan aliran kerja tersebut.

Dalam perisian, salah satu kegunaan paling asas bagi tindanan ialah tindanan panggilan fungsi: setiap kali fungsi memanggil fungsi lain, parameter, pembolehubah setempat dan alamat pemulangan ditolak ke tindanan dalam ingatan.Apabila fungsi kembali, bingkainya akan dipaparkan, memulihkan keadaan pemanggil.

Mekanisme buat asal dan buat semula dalam editor teks, alat lukisan, IDE dan banyak aplikasi lain biasanya bergantung pada susunan tindakan atau keadaanSetiap tindakan pengguna ditolak ke tindanan buat asal; apabila anda menekan Ctrl+Z, aplikasi akan memaparkan tindakan terkini dan membalikkannya.

Tindanan juga banyak digunakan dalam algoritma seperti carian kedalaman dahulu (DFS) dalam graf, penilaian ekspresi (menghuraikan kurungan, operator dan operan), penjejakan balik dan untuk melaksanakan sejarah pelayar di mana setiap halaman yang dilawati ditolak dan "Kembali" memaparkan yang terakhir.Senario-senario ini mendapat manfaat daripada susunan disiplin LIFO semula jadi yang dikuatkuasakan dan berkaitan dengan teras logik pengaturcaraan.

Melaksanakan susunan dengan senarai Python

Cara paling mudah untuk membina tindanan dalam Python adalah dengan menggunakan jenis senarai terbina dalam, memanfaatkan kaedah append() untuk push dan pop() bagi mengalih keluar elemen terakhir.Senarai ialah tatasusunan dinamik di bawah hud dan menyediakan semua fungsi asas yang diperlukan oleh tindanan.

Susunan minimum berdasarkan senarai mungkin menyediakan fungsi pembantu seperti create_stack, push, pop, isempty dan show (atau top, size, dll.), yang semuanya memanipulasi secara dalaman contoh senarai Python biasa.Contohnya, create_stack hanya boleh mengembalikan senarai kosong, dan isempty boleh ditakrifkan sebagai len(stack) == 0.

Satu corak biasa adalah untuk menganggap hujung senarai sebagai bahagian atas tindanan, jadi stack.append(item) melakukan push dan stack.pop() melakukan popIni memastikan kedua-dua operasi berada dalam purata masa yang malar, dan kod tersebut kekal sangat mudah dibaca dan pendek.

Jika anda lebih suka kod yang lebih berstruktur, anda boleh membungkus tingkah laku ini dalam kelas Stack tersuai yang merangkumi senarai dan mendedahkan kaedah yang jelas seperti push(), pop(), peek(), is_empty() dan size(). Enkapsulasi memudahkan untuk melanjutkan tindanan dengan pemeriksaan tambahan atau pengelogan kemudian.

Senarai agak cekap memori kerana setiap elemen menyimpan nilainya secara langsung tanpa overhead penunjuk ke nod seterusnya, seperti yang anda akan lihat dalam senarai terpautTambahan pula, ramai pembangun Python sudah sangat selesa dengan semantik senarai, menjadikan pendekatan ini mudah untuk diajar dan diselenggara.

Walau bagaimanapun, terdapat satu peringatan penting: senarai disokong oleh memori bersebelahan, jadi apabila ia berkembang melebihi ruang yang dikhaskan, Python perlu memperuntukkan blok baharu yang lebih besar dan menyalin elemen tersebutKebanyakan masa peruntukan semula ini dilunaskan dan tidak kelihatan, tetapi kadangkala satu append() mungkin ketara lebih perlahan daripada yang lain.

Satu lagi kelemahan ialah senarai Python tidak selamat untuk thread untuk pengubahsuaian serentak daripada berbilang thread, yang boleh menjadi isu jika anda ingin menggunakan tindanan dalam program berbilang thread.Bagi situasi tersebut, anda harus mempertimbangkan alternatif seperti queue.LifoQueue dan bukannya senarai biasa.

Menggunakan collections.deque sebagai tindanan

Modul koleksi Python menyediakan deque (baris gilir berganda), yang selalunya lebih sesuai daripada senarai apabila anda memerlukan operasi push dan pop yang kerap.Deque dioptimumkan untuk penambahan pantas dan pop dari kedua-dua hujungnya.

Apabila menggunakan deque sebagai tindanan, anda biasanya menolak item menggunakan kaedah append() dan mengalih keluarnya dengan pop(), melayan hujung kanan sebagai bahagian atas tindanan.Secara dalaman, deque dilaksanakan sebagai senarai blok yang dipautkan dua kali, mengelakkan pengagihan semula besar yang kadangkala diperlukan oleh senarai.

Mencipta tindanan menggunakan deque adalah mudah: panggil deque() untuk mendapatkan bekas kosong, kemudian takrifkan operasi seperti push(stack, item) yang memanggil stack.append(item) dan pop(stack) yang menyemak sama ada tindanan tidak kosong dan kemudian memanggil stack.pop()Pembantu tambahan seperti show(stack) boleh mencetak kandungan semasa dengan mudah.

Oleh kerana deque ditala khusus untuk penyisipan dan pemadaman yang cekap di kedua-dua hujung, operasi push dan pop mengekalkan prestasi O(1) yang konsisten walaupun strukturnya berkembang.Ini boleh menjadikan deque lebih baik daripada senarai untuk tindanan yang besar atau banyak digunakan.

Dalam kod single-threaded, deque biasanya merupakan salah satu pilihan lalai terbaik untuk melaksanakan tindanan dalam Python, kerana ia menggabungkan prestasi yang baik, API yang bersih dan tiada kejutan mengenai had kapasiti.Ia juga bertindak lebih mudah diramal dari segi masa apabila tindanan menjadi sangat besar.

Melaksanakan tindanan dengan queue.LifoQueue

Apabila keselamatan thread menjadi penting, kelas LifoQueue modul giliran adalah pilihan utama untuk melaksanakan tindanan dalam PythonLifoQueue pada asasnya ialah tindanan selamat thread dengan mekanisme penguncian terbina dalam.

Untuk mencipta tindanan berasaskan LifoQueue baharu, anda membuat instansiasi LifoQueue dengan parameter maxsize pilihan, yang mewakili bilangan maksimum elemen yang boleh dipegang oleh tindananSecara dalaman, giliran akan mengendalikan menunggu, menyekat dan memberi isyarat merentasi thread jika tindanan penuh atau kosong.

Menolak elemen ke atas timbunan LifoQueue dilakukan dengan put(item), yang mungkin menyekat jika timbunan sudah mencapai kapasiti maksimumnya. Memunculkan elemen menggunakan get(), yang juga boleh menyekat jika tindanan kosong sehingga item baharu tersedia.

Kaedah pembantu tambahan seperti qsize(), full() dan empty() membolehkan anda memeriksa keadaan semasa tindanan dengan cara yang selamat untuk thread.Contohnya, full() memberitahu anda jika tiada lagi elemen yang boleh ditambah, manakala empty() menunjukkan sama ada terdapat apa-apa untuk dipaparkan.

Pertukaran utama apabila menggunakan LifoQueue adalah prestasi: semua penyegerakan yang diperlukan untuk menjadikannya selamat untuk thread memperkenalkan overhead, menjadikan operasi lebih perlahan daripada yang terdapat dalam senarai atau dequesDalam senario berprestasi tinggi yang terikat dengan CPU, overhed tersebut mungkin penting, tetapi bagi banyak aplikasi berbilang thread, keselamatan dan ketepatan adalah jauh lebih penting.

Perlu diingatkan bahawa threading Python tidak bermakna thread akan berjalan secara automatik pada teras CPU yang berbeza disebabkan oleh Global Interpreter Lock (GIL), tetapi LifoQueue masih melindungi tindanan kongsi anda daripada keadaan perlumbaan dan keadaan yang tidak konsisten.Untuk keselarian sebenar merentasi teras, anda memerlukan berbilang pemprosesan atau pendekatan lain, namun konsep tindanan selamat thread kekal relevan untuk beban kerja terikat I/O atau koperasi.

Pelaksanaan tindanan menggunakan senarai berpaut tunggal

Cara sains komputer yang lebih "klasik" untuk membina tindanan dalam Python adalah dengan menggunakan senarai berpaut tunggal, di mana setiap nod menyimpan nilai dan penunjuk (rujukan) ke nod seterusnya.Pendekatan ini memberi anda tindanan bersaiz dinamik yang tidak bergantung pada memori bersebelahan.

Anda biasanya mentakrifkan kelas Nod dengan atribut untuk nilai dan rujukan seterusnya, dan kemudian melaksanakan kelas Stack yang menjejaki nod kepala dan kaunter saizSelalunya, nod kepala tiruan digunakan untuk memudahkan kes tepi apabila tindanan kosong.

Dalam reka bentuk ini, bahagian atas timbunan diwakili oleh nod sejurus selepas kepalaUntuk menolak nilai, anda mencipta nod baharu, menetapkan rujukan seterusnya kepada head.next semasa dan kemudian kemas kini head.next untuk menunjuk ke nod baharu, sambil menambah saiznya semasa anda meneruskan.

Memasang elemen melibatkan pemeriksaan sama ada tindanan kosong, kemudian mengambil nod yang dihalakan oleh head.next, menggerakkan head.next ke nod berikut, mengurangkan saiz dan mengembalikan nilai yang dialih keluarOperasi ini mempunyai kerumitan masa yang malar kerana hanya beberapa kemas kini penunjuk diperlukan.

Kaedah tambahan seperti getSize(), isEmpty() dan peek() mudah dilaksanakan dengan struktur ini: size dijejaki sebagai integer, isEmpty boleh menyemak sama ada size adalah sifar dan peek mengembalikan head.next.value jika tindanan tidak kosong.Anda juga boleh mentakrifkan kaedah __str__ untuk menjana rentetan yang boleh dibaca dengan semua elemen tindanan.

Kelebihan tindanan berasaskan senarai terpaut termasuk pertumbuhan dinamik tanpa pengagihan semula dan prestasi O(1) yang boleh diramal untuk push and pop walaupun struktur menjadi besar.Memori diperuntukkan nod demi nod, yang boleh memberi manfaat dalam sistem dengan memori yang terfragmentasi.

Kelemahannya ialah overhed memori tambahan untuk penunjuk (setiap nod menyimpan sekurang-kurangnya satu rujukan) dan kod yang lebih berjela dan kompleks berbanding senarai atau dequesBagi kebanyakan program Python harian, kos tersebut tidak berbaloi dengan manfaatnya, tetapi teknik ini tetap berharga untuk difahami dan mungkin sesuai untuk senario peringkat rendah atau pendidikan tertentu.

Sifat, kecekapan dan batasan susunan

Secara konseptual, tindanan bertindak seperti timbunan objek di mana hanya bahagian atas sahaja yang boleh diakses: anda sentiasa berinteraksi dengan elemen yang paling baru ditambah dahulu.Sekatan ini memberikan susunan kuasa dan batasannya.

Apabila dilaksanakan dengan betul, membaca elemen atas, memasukkan yang baharu, dan membuang bahagian atas adalah semua operasi O(1) masa malarPrestasi yang konsisten itu amat berguna apabila anda mereka bentuk algoritma yang mungkin perlu ditekan dan diletupkan beribu-ribu atau berjuta-juta kali.

Satu batasan penting ialah anda tidak boleh mencapai elemen sewenang-wenangnya di tengah-tengah tindanan dengan cekap tanpa meletakkan semua yang di atasnya.Jika anda sentiasa mendapati diri anda memerlukan akses rawak, struktur data yang berbeza (seperti senarai yang digunakan dalam fesyen seperti tatasusunan) mungkin lebih sesuai.

Penggunaan memori dan corak peruntukan sangat bergantung pada pelaksanaan yang dipilih: tatasusunan (senarai) menggunakan memori bersebelahan dan kadangkala perlu diagihkan semula, deques mengurus blok memori untuk mengelakkan salinan besar, dan senarai terpaut menyebarkan nod merentasi lokasi memori yang tersediaSetiap pendekatan mengimbangi overhed, lokaliti dan tingkah laku kapasiti secara berbeza.

Dari perspektif reka bentuk, susunan sengaja dibuat ringkas: hanya bahagian atas yang kelihatan, dan tiada konsep pengindeksan atau penyisipan di tengah.Kesederhanaan ini mengurangkan kemungkinan penyalahgunaan secara tidak sengaja dan menggalakkan kod yang secara eksplisit memodelkan aliran kerja LIFO.

Pertimbangan susunan dan penguliran Python

Apabila program Python anda berbenang tunggal, anda boleh memilih antara senarai dan deques dengan selamat untuk melaksanakan tindanan berdasarkan prestasi dan kemudahanKedua-duanya menyediakan keupayaan push dan pop dan mudah diintegrasikan ke dalam kod biasa.

Sebaik sahaja anda memperkenalkan berbilang thread yang berkongsi tindanan, keadaan menjadi lebih rumit: operasi yang kelihatan atomik pada tahap Python mungkin bersambung dengan cara yang tidak dijangka, merosakkan keadaan dalamanSenarai dan dek biasa tidak direka bentuk untuk selamat sepenuhnya untuk thread apabila digunakan sebagai tindanan boleh ubah kongsi.

Deques agak selamat jika anda sangat berdisiplin dan mengehadkan diri anda untuk hanya menggunakan append() dan pop() dari satu hujung dengan cara yang dikawal dengan telitiWalau bagaimanapun, walaupun begitu, isu-isu halus dan keadaan perlumbaan boleh muncul jika berbilang thread membaca dan menulis pada masa yang sama tanpa penyegerakan luaran.

Untuk senario berbilang thread yang mantap di mana beberapa thread mungkin tekan dan muncul serentak, queue.LifoQueue ialah pelaksanaan tindanan yang disyorkanKunci terbina dalam dan semantik penyekatan memastikan akses serentak tidak merosakkan tindanan.

Pertukarannya, sudah tentu, ialah operasi LifoQueue (put dan get) adalah lebih perlahan daripada kaedah senarai mentah atau deque kerana koordinasi tambahan antara threadSama ada overhed itu penting bergantung pada keperluan prestasi aplikasi anda dan kekerapan tindanan diakses.

Perlu juga diingat bahawa model threading Python masih berjalan di bawah Global Interpreter Lock, jadi walaupun dengan tindanan selamat thread, anda tidak akan mendapat paralelisme CPU yang sempurna secara automatik untuk tugasan terikat CPU.Namun begitu, untuk program atau reka bentuk terikat I/O yang bergantung pada keserentakan dan bukannya paralelisme mentah, tindanan selamat thread ialah blok binaan penting.

Memilih pelaksanaan susunan Python yang betul

Memandangkan semua pilihan ini, pelaksanaan tindanan "terbaik" dalam Python sangat bergantung pada konteks anda: single-threaded vs multi-threaded, kepekaan prestasi, tingkah laku memori dan kejelasan kod semuanya memainkan peranan.Tiada pilihan tunggal yang sempurna untuk setiap situasi.

Dalam skrip atau persekitaran pembelajaran yang mudah dan tidak berulir, menggunakan senarai sebagai tindanan selalunya lebih daripada cukup: append() dan pop() adalah intuitif, pantas untuk kebanyakan beban kerja dan hampir tidak memerlukan kod boilerplateUntuk tujuan pendidikan, senarai juga memudahkan untuk mencetak dan memeriksa kandungan.

Apabila tindanan anda akan banyak digunakan, berpotensi menyimpan banyak elemen, dan anda mahukan push/pop yang pantas secara konsisten dengan lebih sedikit kejutan yang berkaitan dengan pengagihan semula memori, collections.deque cenderung menjadi pilihan yang paling praktikal.. Cermin APInya disenaraikan dengan teliti, jadi penghijrahan biasanya tidak menyakitkan.

Jika anda tahu dari awal bahawa tindanan akan diakses daripada berbilang thread, terutamanya dengan kedua-dua push dan pop berlaku serentak, queue.LifoQueue ialah pilihan paling selamatIa mungkin lebih perlahan, tetapi ia menjimatkan anda daripada melaksanakan protokol penguncian anda sendiri dan membantu mengelakkan keadaan perlumbaan yang rumit.

Pendekatan senarai berpaut tunggal adalah ideal apabila anda ingin meneroka atau mengajar struktur data dalaman, atau apabila kekangan tertentu menjadikan tatasusunan atau dekues bersebelahan kurang menarik.Ia juga memberi anda kawalan penuh ke atas susun atur dan tingkah laku nod, dengan mengorbankan lebih banyak kod dan sedikit lebih banyak overhed mental.

Walau apa pun pelaksanaan yang anda pilih, idea asasnya tetap sama: anda memodelkan struktur Masuk Terakhir, Keluar Dahulu yang menyimpan elemen di atas satu sama lain dan memberi anda akses pantas dan boleh diramal kepada item yang paling baru ditambah.Sebaik sahaja anda selesa dengan model ini, ia menjadi lebih mudah untuk memikirkan algoritma dan tingkah laku sistem yang mana susunan adalah padanan semula jadi.

Dengan memahami cara tindanan beroperasi, operasi yang disokongnya, pelaksanaan Python biasa dan prestasi serta pertukaran threadingnya, anda boleh memilih dan melaksanakan versi yang paling sesuai dengan keperluan projek anda dengan yakin sambil menulis kod yang kekal cekap dan mudah dipertimbangkan dari semasa ke semasa..