Selalunya, prinsip operasi timbunan dibandingkan dengan timbunan plat: untuk mengambil yang kedua dari atas, anda perlu mengeluarkan yang atas.
Dalam sesetengah bahasa (contohnya, Lisp, Python), sebarang senarai boleh dipanggil tindanan, kerana operasi pop dan tolak tersedia untuk mereka. Dalam C++, perpustakaan standard mempunyai kelas dengan struktur dan kaedah yang dilaksanakan. Dan lain-lain.
YouTube ensiklopedia
1 / 3
Sains Komputer. Struktur data: Timbunan. Pusat Pembelajaran Dalam Talian Foxford
#9. Stack / 1. Asembler dan prosedur / Pengaturcaraan dari awal
Asas rangkaian data. model OSI dan timbunan protokol TCP IP. Asas Ethernet.
Sari kata
Timbunan perisian
Organisasi dalam ingatan
Selalunya, tindanan dilaksanakan sebagai senarai sehala (setiap elemen dalam senarai mengandungi, sebagai tambahan kepada maklumat yang disimpan dalam tindanan, penunjuk kepada elemen tindanan seterusnya).
Tetapi timbunan juga selalunya terletak dalam tatasusunan satu dimensi dengan alamat tersusun. Organisasi tindanan ini mudah jika elemen maklumat menduduki memori kuantiti tetap perkataan, contohnya, 1 perkataan. Ini menghapuskan keperluan untuk menyimpan penunjuk eksplisit ke elemen tindanan seterusnya dalam elemen tindanan, yang menjimatkan memori. Dalam kes ini, penuding tindanan ( Penunjuk Tindanan, - SP) biasanya merupakan daftar pemproses dan menunjuk ke alamat kepala timbunan.
Sebagai contoh, katakan bahawa kepala timbunan terletak di alamat yang lebih rendah, elemen berikut terletak pada alamat yang semakin meningkat. Setiap kali perkataan ditolak ke tindanan, SP mula-mula dikurangkan sebanyak 1 dan kemudian alamat dari SP ditulis ke ingatan. Setiap kali perkataan muncul daripada timbunan, ia mula-mula membaca alamat semasa daripada SP dan kemudian menambah kandungan SP sebanyak 1.
Apabila menyusun tindanan sebagai senarai satu arah, nilai pembolehubah tindanan ialah penunjuk ke bahagian atasnya - alamat bahagian atas. Jika timbunan kosong, maka nilai penunjuk ialah NULL.
Contoh pelaksanaan tindanan dalam C:
struct stack (char * data; struct stack * next; );
Operasi Timbunan
Terdapat tiga kemungkinan operasi pada tindanan: menambah elemen (aka menolak), mengeluarkan elemen (pop) dan membaca elemen kepala (mengintip).
Apabila menolak (tolak) elemen baru ditambah, menunjuk ke elemen yang sebelum ini menjadi kepala. Elemen baharu kini menjadi ketua.
Apabila memadamkan elemen (pop), yang pertama dialih keluar, dan bahagian kepala menjadi elemen yang mempunyai penuding objek ini (elemen seterusnya). Dalam kes ini, nilai elemen yang dialih keluar dikembalikan.
tolak batal (STACK * ps, int x) // Menambah elemen baharu pada timbunan( jika ( ps -> saiz == STACKSIZE ) // Adakah timbunan melimpah?( fputs ( "Ralat: limpahan tindanan \n " , stderr ); batalkan (); ) else ( ps -> item [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Alih keluar daripada timbunan( jika ( ps -> saiz == 0 ) // Adakah timbunan kosong?( fputs ( "Ralat: timbunan underflow \n " , stderr ); batalkan (); ) else ( return ps -> item [ -- ps -> size ]; ) )
Kawasan permohonan
Pandangan pengaturcaraan timbunan digunakan untuk melintasi struktur data, seperti pokok atau graf. menggunakan fungsi rekursif Tindanan juga akan digunakan, tetapi jenis perkakasannya. Sebagai tambahan kepada tujuan ini, timbunan digunakan untuk mengatur
Proses serupa berlaku semasa gangguan perkakasan (pemproses X86 dengan gangguan perkakasan secara automatik menyimpan daftar bendera pada timbunan). Di samping itu, penyusun meletakkan pembolehubah tempatan prosedur pada tindanan (jika pemproses mempunyai akses kepada lokasi tindanan rawak).
Sebelum tindanan boleh digunakan, ia mesti dimulakan supaya daftar SS:ESP menghala ke alamat kepala tindanan di kawasan fizikal. memori capaian rawak, dan untuk menyimpan data dalam tindanan adalah perlu untuk menyimpan bilangan sel memori yang diperlukan (jelas, tindanan dalam ROM, secara semula jadi, tidak boleh diatur). Program aplikasi, sebagai peraturan, daripada sistem operasi menerima timbunan sedia untuk dimakan. Dalam mod pemproses yang dilindungi, segmen keadaan tugas mengandungi empat pemilih segmen tindanan (untuk tahap yang berbeza keistimewaan), tetapi hanya satu timbunan digunakan pada satu masa.
Tindanan ialah fenomena pengaturcaraan dan penyelesaian semula jadi. Stack serta-merta masuk ke dalam perniagaan komputer dan menjadi begitu "asli", seolah-olah di situlah semuanya bermula.
Tanpa timbunan, pemproses tidak berfungsi, tidak ada rekursi, dan mustahil untuk mengatur panggilan fungsi yang cekap. Sebarang algoritma boleh dilakukan tanpa baris gilir, senarai, koleksi, tatasusunan atau sistem objek tersusun, tetapi tiada apa yang berfungsi tanpa memori dan timbunan, termasuk semua perkara di atas.
Pada awal permulaan: pemproses, memori dan timbunan
Memori ideal menyediakan pengalamatan terus kepada nilai - ini ialah tahap mesin dan bahasa darjat tinggi. Dalam kes pertama, pemproses secara berurutan melelaran melalui alamat memori dan melaksanakan arahan. Dalam kes kedua, pengaturcara memanipulasi tatasusunan. Kedua-dua episod mengandungi:
- alamat = nilai;
- indeks = nilai.
Alamat boleh menjadi mutlak dan relatif, indeks boleh menjadi digital dan bersekutu. Alamat dan indeks mungkin mengandungi alamat lain daripada nilai, tetapi ini adalah butiran pengalamatan tidak langsung. Tanpa ingatan, pemproses tidak boleh berfungsi, dan tanpa timbunan arahan dan data, ia seperti bot tanpa dayung.
Timbunan pinggan ialah cerita tradisional tentang intipati timbunan: konsep timbunan dan terjemahan dalam kesedaran bersama. Anda tidak boleh mengambil pinggan dari bawah, anda hanya boleh mengambilnya dari atas, dan kemudian semua pinggan akan menjadi utuh.
Apa sahaja yang datang terakhir pada timbunan pergi dahulu. Penyelesaian yang sempurna. Pada dasarnya, timbunan, sebagai terjemahan satu tindakan ke yang lain, mengubah idea algoritma sebagai urutan operasi.
Intipati dan konsep timbunan
Pemproses dan memori adalah blok binaan utama komputer. Pemproses melaksanakan arahan, memanipulasi alamat memori, dan mengambil dan mengubah suai nilai pada alamat ini. Dalam bahasa pengaturcaraan, semua ini diubah menjadi pembolehubah dan nilainya. Intipati timbunan dan konsep keluar dahulu lepas (LIFO) kekal tidak berubah.
Akronim LIFO tidak lagi digunakan sekerap dahulu. Mungkin kerana senarai telah diubah menjadi objek, dan baris gilir first in first out (FIFO) digunakan mengikut keperluan. Dinamik jenis data telah kehilangan kaitannya dalam konteks menerangkan pembolehubah, tetapi telah memperoleh kepentingannya pada masa pelaksanaan ungkapan: jenis data ditentukan pada saat penggunaannya, dan sehingga saat itu anda boleh menerangkan apa-apa dan apa-apa cara yang anda mahu.
Jadi, timbunan - apakah itu? Sekarang anda tahu bahawa ini adalah soalan yang tidak sesuai. Lagipun, tanpa timbunan tidak ada pengaturcaraan moden. Sebarang panggilan fungsi bermakna lulus parameter dan alamat pemulangan. Fungsi boleh memanggil fungsi lain - ini sekali lagi menghantar parameter dan alamat pemulangan. Menyediakan mekanisme untuk memanggil nilai tanpa timbunan adalah kerja tambahan, walaupun penyelesaian yang boleh dicapai pastinya mungkin.
Ramai orang bertanya: "Timbunan - apakah itu?" Dalam konteks panggilan fungsi, ia terdiri daripada tiga tindakan:
- menyimpan alamat pemulangan;
- menyimpan semua pembolehubah atau alamat yang dipindahkan kepada mereka;
- panggilan fungsi.
Setelah fungsi yang dipanggil telah menyelesaikan misinya, ia hanya akan mengembalikan kawalan ke alamat pemulangan. Fungsi boleh memanggil sebarang bilangan fungsi lain, kerana hadnya hanyalah saiz timbunan.
Sifat tindanan
Tindanan bukanlah jenis data abstrak, tetapi mekanisme sebenar. Di peringkat pemproses, ia adalah "enjin" yang memperhalusi dan melengkapkan kerja kitaran pemproses utama. Seperti bit aritmetik, timbunan menangkap peraturan operasi yang mudah dan jelas. Ia boleh dipercayai dan selamat.
Ciri ciri tindanan ialah saiz dan panjang unsurnya. Di peringkat pemproses, semuanya ditentukan oleh kapasiti bit, pengalamatan memori dan fizik akses kepadanya. Ciri yang menarik dan tradisi: timbunan berkembang ke bawah, iaitu, ke arah mengurangkan alamat memori, dan program dan memori data - ke atas. Ini adalah perkara biasa, tetapi tidak diperlukan. Maksud di sini adalah penting - dia datang terakhir dan pergi dahulu. Peraturan yang sangat mudah ini membolehkan anda membina algoritma menarik yang berfungsi terutamanya dalam bahasa tahap tinggi. Sekarang anda tidak akan bertanya, apakah timbunan?
Kerja yang sempurna perkakasan telah menjadi norma untuk masa yang sangat lama, tetapi di barisan hadapan teknologi maklumat Idea timbunan mendapat aplikasi baharu dan menjanjikan.
Pada asasnya, tidak kira apa timbunan di peringkat pemproses. Ia adalah bahagian semula jadi dalam seni bina komputer. Tetapi dalam pengaturcaraan, timbunan bergantung pada aplikasi tertentu dan keupayaan pengaturcara.
Tatasusunan, koleksi, senarai, baris gilir... Tindanan!
Orang sering bertanya soalan: "Timbunan - apakah itu?" "Pengaturcaraan" dan "sistematisasi" adalah konsep yang menarik: mereka bukan sinonim, tetapi ia sangat berkait rapat. Pengaturcaraan telah pergi begitu jauh dengan sangat cepat sehingga puncak yang dicapai kelihatan ideal. Kemungkinan besar ini tidak berlaku. Tetapi jelas sesuatu yang lain.
Idea timbunan telah menjadi biasa bukan sahaja pada tahap pelbagai bahasa pengaturcaraan, tetapi juga pada tahap reka bentuk dan keupayaan mereka untuk mencipta jenis data. Mana-mana tatasusunan mempunyai tolak dan pop, dan konsep "elemen pertama dan terakhir tatasusunan" telah menjadi tradisional. Sebelum ini terdapat hanya elemen tatasusunan, tetapi hari ini terdapat:
- elemen tatasusunan;
- elemen pertama tatasusunan;
- elemen terakhir tatasusunan.
Operasi meletakkan elemen dalam tatasusunan menggerakkan penuding, dan mendapatkan semula elemen dari permulaan tatasusunan atau dari hujungnya membuat perbezaan. Pada asasnya ini adalah timbunan yang sama, tetapi digunakan pada jenis data lain.
Ia amat perlu diberi perhatian bahawa bahasa popular pengaturcaraan tidak mempunyai binaan tindanan. Tetapi mereka memberikan ideanya kepada pemaju sepenuhnya.
Tindanan ialah koleksi yang unsur-unsurnya diperoleh atas dasar masuk terakhir, keluar dahulu. (Masuk Pertama-Keluar Terakhir atau LIFO). Ini bermakna kami hanya akan mempunyai akses kepada elemen tambahan yang terakhir.
Tidak seperti senarai, kami tidak boleh mengakses elemen timbunan sewenang-wenangnya. Kami hanya boleh menambah atau mengalih keluar elemen menggunakan kaedah khas. Tindanan juga tidak mempunyai kaedah Mengandungi seperti senarai. Juga, timbunan tidak mempunyai iterator. Untuk memahami sebab sekatan sedemikian diletakkan pada timbunan, mari lihat cara ia berfungsi dan cara ia digunakan.
Analogi yang paling biasa untuk menerangkan timbunan ialah timbunan plat. Tidak kira berapa banyak pinggan dalam tindanan, kami sentiasa boleh mengeluarkan yang teratas. Pinggan bersih diletakkan di atas timbunan dengan cara yang sama, dan kami akan sentiasa mengambil pinggan yang diletakkan terakhir dahulu.
Jika kita meletakkan, sebagai contoh, plat merah, kemudian yang biru, dan kemudian yang hijau, maka pertama kita perlu mengeluarkan yang hijau, kemudian yang biru, dan akhirnya yang merah. Perkara utama yang perlu diingat ialah pinggan sentiasa diletakkan di atas timbunan. Apabila seseorang mengambil pinggan, mereka juga mengeluarkannya dari atas. Ternyata plat dibongkar dalam susunan yang bertentangan dengan yang diletakkan.
Sekarang setelah kita memahami cara tindanan berfungsi, mari kita perkenalkan beberapa istilah. Operasi menambah elemen pada timbunan dipanggil "tolak", dan mengeluarkannya dipanggil "pop". Elemen terakhir yang ditambah dipanggil bahagian atas timbunan, atau "atas", dan boleh dilihat menggunakan operasi "mengintip". Sekarang mari kita lihat templat kelas yang melaksanakan tindanan.
Kelas tindanan
Kelas Stack mentakrifkan kaedah Push, Pop, Peek untuk mengakses elemen dan medan Count. Dalam pelaksanaan kami akan menggunakan LinkedList
Timbunan kelas awam ( LinkedList _items = New LinkedList(); public void Push(nilai T) ( throw new NotImplementedException(); ) public T Pop() ( throw new NotImplementedException(); ) public T Peek() ( throw new NotImplementedException( ); ) public int Count ( get; ) )
Kaedah tolak
- Kelakuan: Menambah elemen pada bahagian atas timbunan.
- Kerumitan: O(1).
Memandangkan kami menggunakan senarai terpaut untuk menyimpan elemen, kami hanya boleh menambahkan senarai baharu pada penghujung senarai.
Public void Push(nilai T) ( _items.AddLast(value); )
Kaedah pop
- Kelakuan: Mengeluarkan elemen dari bahagian atas tindanan dan mengembalikannya. Jika timbunan kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Tekan menambah elemen ke penghujung senarai, jadi ia juga akan membawanya dari penghujung. Jika senarai kosong, pengecualian akan dilemparkan.
Public T Pop() ( jika (_items.Count == 0) ( throw new InvalidOperationException("Timbunan kosong"); ) T hasil = _items.Tail.Value; _items.RemoveLast(); return result; )
Kaedah mengintip
- Kelakuan: Pulangan elemen atas timbunan, tetapi tidak memadamkannya. Jika timbunan kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah mengira
- Kelakuan: Mengembalikan bilangan elemen dalam timbunan.
- Kerumitan: O(1).
Mengapakah kita perlu tahu berapa banyak elemen yang ada pada timbunan jika kita tidak mempunyai akses kepada mereka? Dengan medan ini kita boleh menyemak sama ada terdapat elemen pada timbunan atau jika ia kosong. Ini sangat berguna memandangkan itu Kaedah pop melemparkan pengecualian.
Contoh: kalkulator dalam notasi Poland terbalik.
Contoh klasik menggunakan tindanan ialah kalkulator dalam notasi Poland terbalik, atau postfix. Di dalamnya pengendali ditulis selepas operan mereka. Iaitu, kami menulis:
<операнд> <операнд> <оператор>
bukannya yang tradisional:
<операнд> <оператор> <операнд>
Dengan kata lain, bukannya "4 + 2" kita akan menulis "4 2 +". Jika anda berminat dengan asal notasi Poland terbalik dan namanya, anda boleh mengetahui tentangnya di Wikipedia atau dalam enjin carian.
Cara notasi Poland terbalik dikira dan mengapa tindanan itu sangat berguna apabila menggunakannya boleh dilihat dengan jelas daripada algoritma berikut:
Untuk setiap nilai input jika nilai adalah integer, tolak nilai pada tindanan operan lain jika nilai itu adalah operator pop nilai kiri dan kanan daripada tindanan menilai operator menolak hasilnya ke jawapan pop tindanan daripada tindanan .
Iaitu, untuk ungkapan "4 2 +" tindakannya adalah seperti berikut:
Tolak(4) tolak(2) tolak(pop() + pop())
Pada akhirnya akan ada satu nilai pada timbunan - 6.
Yang berikut ialah kod penuh kalkulator mudah, yang membaca ungkapan (contohnya, 4 2 +) daripada konsol, membahagikan input mengikut ruang (["4", "2", "+"]) dan melaksanakan algoritma pengiraan. Penilaian diteruskan sehingga perkataan berhenti ditemui.
Void RpnLoop() ( while (true) ( Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") ( break; ) // Timbunan nilai yang belum diproses Nilai timbunan = new Stack(); foreach (token rentetan dalam input. Split(char baru ( " " ))) ( // Jika nilai ialah integer... int value; if (int. TryParse(token, out value)) ( // ... letakkan pada timbunan. values.Push(value); ) else ( // jika tidak lakukan operasi... int rhs = nilai .Pop(); int lhs = values.Pop(); // ... dan letakkan semula hasilnya. suis (token) ( case "+": values.Push(lhs + rhs); break; case "-" : nilai .Push(lhs % rhs); break; lalai: // Jika operasi bukan +, -, * atau / buang ArgumentException(string.Format("Token tidak dikenali: (0)", token)); ) ) ) // Elemen terakhir pada timbunan ialah hasilnya. Console.WriteLine(values.Pop()); ) )
Beratur
Baris gilir sangat mirip dengan tindanan. Mereka juga tidak memberikan akses kepada elemen sewenang-wenangnya, tetapi, tidak seperti timbunan, elemen disusun (enqueue) dan mendaki (dequeue) dari hujung yang berbeza. Kaedah ini dipanggil "masuk dahulu, keluar dahulu" (Dulu-Masuk-Dulu-Keluar atau FIFO). Iaitu, kami akan mengambil elemen dari baris gilir dalam susunan yang sama seperti yang kami masukkan. Seperti barisan atau penghantar sebenar.
Baris gilir sering digunakan dalam program untuk menyediakan penimbal di mana item boleh diletakkan untuk diproses kemudian sambil mengekalkan susunan kedatangannya. Sebagai contoh, jika pangkalan data hanya menyokong satu sambungan, anda boleh menggunakan baris gilir benang yang, anehnya, akan menunggu giliran untuk mengakses pangkalan data.
Kelas beratur
Kelas Queue, seperti tindanan, akan dilaksanakan menggunakan senarai terpaut. Ia akan menyediakan Enqueue untuk menambah elemen, Dequeue untuk mengalih keluar, kaedah Peek dan Count. Seperti kelas Stack, ia tidak akan melaksanakan antara muka ICollection
Baris gilir kelas awam ( LinkedList _items = New LinkedList(); public void Enqueue(nilai T) ( throw new NotImplementedException(); ) public T Dequeue() ( throw new NotImplementedException(); ) public T Peek() ( throw new NotImplementedException( ); ) public int Count ( get; ) )
Kaedah enqueue
- Kelakuan: Menambah elemen pada baris gilir.
- Kerumitan: O(1).
Elemen baris gilir baharu boleh ditambah sama ada pada permulaan senarai atau pada penghujung. Ia hanya penting bahawa unsur-unsur dicapai dari tepi bertentangan. Dalam pelaksanaan ini, kami akan menambah elemen baharu pada permulaan senarai dalaman.
Public void Enqueue(nilai T) ( _items.AddFirst(value); )
Kaedah dequeue
- Kelakuan: Mengalih keluar elemen yang diletakkan pertama daripada baris gilir dan mengembalikannya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Oleh kerana kami memasukkan elemen pada permulaan senarai, kami akan mengalih keluarnya dari penghujung. Jika senarai kosong, pengecualian akan dilemparkan.
Public T Dequeue() ( if (_items.Count == 0) ( throw new InvalidOperationException("Baris gilir kosong"); ) T last = _items.Tail.Value; _items.RemoveLast(); return last; )
Kaedah mengintip
- Kelakuan: Mengembalikan elemen yang akan dikembalikan oleh panggilan seterusnya kepada kaedah Dequeue. Barisan gilir kekal tidak berubah. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah mengira
- Kelakuan:
- Kerumitan: O(1).
Beratur dua hala
Beratur dua hala (Baris beratur dua hujung), atau Dis (Deque), memanjangkan gelagat baris gilir. Dalam deque, anda boleh menambah atau mengalih keluar elemen dari kedua-dua permulaan dan penghujung baris gilir. Tingkah laku ini berguna dalam banyak tugas, seperti menjadualkan urutan atau melaksanakan struktur data lain. Kemudian kita akan melihat pelaksanaan timbunan menggunakan deque.
Kelas Deque
Kelas Deque paling mudah untuk dilaksanakan menggunakan senarai berganda. Ia membolehkan anda melihat, memadam dan menambah elemen pada permulaan dan penghujung senarai. Perbezaan utama antara deque dan baris gilir biasa ialah kaedah Enqueue, Dequeue dan Peek dibahagikan kepada pasangan untuk berfungsi dengan kedua-dua hujung senarai.
Deque kelas awam ( LinkedList _items = new LinkedList(); public void EnqueueFirst(T value) ( throw new NotImplementedException(); ) public void EnqueueLast(T value) ( Throw new NotImplementedException(); ) public T DequeueFirst( ) ( buang NotImplementedException(); ) public T DequeueLast() ( throw new NotImplementedException(); ) public T PeekFirst() ( throw new NotImplementedException(); ) public T PeekLast() ( throw new NotImplementedException(); ) public int Kira (dapat; ) )
Kaedah EnqueueFirst
- Kelakuan:
- Kerumitan: O(1).
Kaedah EnqueueLast
- Kelakuan:
- Kerumitan: O(1).
Kaedah DequeueFirst
- Kelakuan: Mengalih keluar elemen dari hadapan baris gilir dan mengembalikannya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah DequeueLast
- Kelakuan:
- Kerumitan: O(1).
Kaedah PeekFirst
- Kelakuan: Mengembalikan elemen dari permulaan baris gilir tanpa mengubah suainya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah PeekLast
- Kelakuan:
- Kerumitan: O(1).
Kaedah mengira
- Kelakuan: Mengembalikan bilangan elemen dalam baris gilir, atau 0 jika baris gilir kosong.
- Kerumitan: O(1).
Contoh: Pelaksanaan Tindanan
Deque sering digunakan untuk melaksanakan struktur data lain. Mari lihat contoh pelaksanaan timbunan menggunakannya.
Anda mungkin tertanya-tanya mengapa melaksanakan tindanan berdasarkan baris gilir dan bukannya senarai terpaut. Terdapat dua sebab: prestasi dan guna semula kod. Senarai terpaut mempunyai overhed untuk mencipta nod dan tiada jaminan lokaliti data: elemen boleh terletak di mana-mana dalam memori, yang menyebabkan sejumlah besar ketinggalan dan kemerosotan prestasi di peringkat pemproses. Pelaksanaan deque yang lebih berprestasi memerlukan tatasusunan untuk menyimpan elemen.
Walau bagaimanapun, melaksanakan tindanan atau baris gilir menggunakan tatasusunan adalah bukan satu tugas yang mudah, tetapi melaksanakan deque dengan cara ini dan menggunakannya sebagai asas untuk struktur data lain akan memberi kami manfaat prestasi yang serius dan membolehkan kami menggunakan semula kod. Ini mengurangkan kos sokongan.
Kita akan melihat varian baris gilir menggunakan tatasusunan kemudian, tetapi mula-mula mari kita lihat kelas tindanan menggunakan dequeue:
Timbunan kelas awam ( Deque _items = new Deque(); public void Push(T value) ( _items.EnqueueFirst(value); ) public T Pop() ( return _items.DequeueFirst(); ) public T Peek() ( return _items .PeekFirst(); ) public int Count ( dapatkan ( return _items.Count; ) ) )
Ambil perhatian bahawa semua pengendalian ralat kini dikendalikan oleh kelas Deque, dan sebagai tambahan, sebarang pengoptimuman baris gilir juga akan ditunjukkan pada tindanan. Melaksanakan baris gilir pergi balik biasa adalah sangat mudah sehingga kami akan membiarkannya sebagai latihan untuk pembaca.
Menyimpan elemen dalam tatasusunan
Seperti yang telah disebutkan, melaksanakan baris gilir menggunakan tatasusunan mempunyai kelebihannya. Ia kelihatan mudah, tetapi sebenarnya terdapat beberapa nuansa yang perlu diambil kira.
Mari kita lihat masalah yang mungkin timbul dan cara menyelesaikannya. Di samping itu, kami memerlukan maklumat tentang meningkatkan tatasusunan dalaman daripada artikel sebelumnya tentang tatasusunan dinamik.
Apabila baris gilir dibuat, tatasusunan sifar panjang dibuat di dalamnya. Huruf merah "h" dan "t" bermaksud _kepala dan _penunjuk ekor, masing-masing.
Deque deq = new Deque(); deq.EnqueueFirst(1);
Deq.EnqueueLast(2);
Deq.EnqueueFirst(0);
Sila ambil perhatian: indeks "kepala" baris gilir telah melonjak ke permulaan senarai. Kini elemen pertama yang akan dikembalikan apabila memanggil kaedah DequeueFirst ialah 0 (indeks 3).
Deq.EnqueueLast(3);
Tatasusunan penuh, jadi apabila menambah elemen perkara berikut akan berlaku:
- Algoritma pertumbuhan akan menentukan saiz tatasusunan baharu.
- Elemen akan disalin ke tatasusunan baharu dari kepala ke ekor.
- Elemen baharu akan ditambah.
Sekarang mari kita lihat apa yang berlaku apabila elemen dialih keluar:
Deq.DequeueFirst();
Deq.DequeueLast();
Detik penting: tanpa mengira kapasiti atau kepenuhan tatasusunan dalaman, secara logiknya, kandungan baris gilir adalah elemen dari "kepala" hingga "ekor", dengan mengambil kira "pekeliling". Tingkah laku ini juga dipanggil "penampan cincin".
Sekarang mari kita lihat pelaksanaannya.
Kelas Deque (menggunakan tatasusunan)
Antara muka baris gilir berasaskan tatasusunan adalah sama seperti dalam kes pelaksanaan senarai terpaut. Kami tidak akan mengulanginya. Walau bagaimanapun, memandangkan senarai itu digantikan dengan tatasusunan, kami menambah medan baharu - tatasusunan itu sendiri, saiz dan penunjuknya kepada "ekor" dan "kepala" baris gilir.
Deque kelas awam ( T _item = T baharu; // Bilangan elemen dalam baris gilir. int _size = 0; // Indeks elemen pertama (tertua). int _head = 0; // Indeks elemen terakhir (terbaru) int _tail = -1; ... )
Algoritma pertumbuhan
Bila tempat percuma dalam tatasusunan dalaman berakhir, ia perlu ditingkatkan, elemen disalin dan penunjuk kepada "ekor" dan "kepala" dikemas kini. Operasi ini dilakukan jika perlu sambil menambah elemen. Parameter StartIndex digunakan untuk menunjukkan bilangan medan yang harus dibiarkan kosong pada permulaan (sekiranya menambah pada permulaan).
Perhatikan bagaimana data diambil apabila anda perlu melompat ke permulaan tatasusunan apabila pergi dari kepala ke ekor.
Private void allocateNewArray(int startingIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) ( int targetIndex = startingIndex; // Salin kandungan... // Jika tatasusunan tidak digelung, hanya salin elemen. // Jika tidak, salin dari kepala ke penghujung, dan kemudian dari permulaan tatasusunan ke ekor. // Jika ekor kurang daripada kepala, pergi ke permulaan. jika (_tail< _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }
Kaedah EnqueueFirst
- Kelakuan: Menambah elemen pada permulaan baris gilir. Elemen ini akan diambil dari baris gilir seterusnya apabila kaedah DequeueFirst dipanggil.
- Kerumitan:
Kaedah EnqueueLast
- Kelakuan: Menambah elemen pada penghujung baris gilir. Elemen ini akan diambil dari baris gilir seterusnya apabila kaedah DequeueLast dipanggil.
- Kerumitan: O(1) dalam kebanyakan kes; O(n) apabila pengembangan tatasusunan diperlukan.
Kaedah DequeueFirst
- Kelakuan: Mengalih keluar elemen dari permulaan baris gilir dan mengembalikannya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah DequeueLast
- Kelakuan: Mengalih keluar elemen dari penghujung baris gilir dan mengembalikannya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah PeekFirst
- Kelakuan: Mengembalikan elemen dari permulaan baris gilir tanpa mengubahnya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah PeekLast
- Kelakuan: Mengembalikan elemen dari penghujung baris gilir tanpa mengubahnya. Jika baris gilir kosong, buang InvalidOperationException.
- Kerumitan: O(1).
Kaedah mengira
- Kelakuan: Mengembalikan bilangan elemen dalam baris gilir, atau 0 jika baris gilir kosong.
- Kerumitan: O(1).
Akan bersambung
Kami kini telah menyelesaikan bahagian keempat siri artikel kami. Di dalamnya kami melihat susunan dan barisan. Lain kali kita akan beralih kepada pepohon carian binari.
Kami menggunakan bahasa pengaturcaraan yang semakin maju yang membolehkan kami menulis lebih sedikit kod dan mendapatkan hasil yang hebat. Anda perlu membayar untuk ini. Apabila kita berurusan dengan perkara peringkat rendah semakin kurang, adalah perkara biasa bahawa ramai di antara kita tidak begitu memahami apa itu tindanan dan timbunan, cara kompilasi sebenarnya berfungsi, apakah perbezaan antara penaipan statik dan dinamik, dsb. Saya tidak mengatakan bahawa semua pengaturcara tidak tahu tentang konsep ini - saya hanya fikir kadang-kadang ia berbaloi untuk kembali kepada perkara-perkara lama seperti itu.
Hari ini kita akan bercakap tentang hanya satu topik: tindanan dan timbunan. Kedua-dua tindanan dan timbunan merujuk kepada lokasi yang berbeza di mana pengurusan memori berlaku, tetapi strategi untuk pengurusan ini berbeza secara radikal.
Timbunan
Tindanan ialah kawasan RAM yang dibuat untuk setiap utas. Ia berfungsi dalam susunan LIFO (Masuk Terakhir, Keluar Dahulu), bermakna sekeping ingatan terakhir yang ditolak ke tindanan akan menjadi barisan pertama yang akan dikeluarkan dari timbunan. Setiap kali fungsi mengisytiharkan pembolehubah baharu, ia ditambahkan pada timbunan dan apabila pembolehubah itu keluar dari skop (contohnya, apabila fungsi tamat), ia dikeluarkan secara automatik daripada timbunan. Apabila pembolehubah tindanan dibebaskan, kawasan memori itu tersedia untuk pembolehubah tindanan lain.
Oleh kerana sifat timbunan ini, pengurusan memori adalah sangat logik dan mudah dilakukan pada CPU; ini menghasilkan kelajuan tinggi, terutamanya kerana masa kitaran kemas kini bait tindanan adalah sangat singkat, i.e. bait ini berkemungkinan besar terikat pada cache pemproses. Walau bagaimanapun, terdapat juga kelemahan kepada bentuk pengurusan yang ketat ini. Saiz tindanan ialah nilai tetap, dan melebihi had memori yang diperuntukkan pada tindanan akan mengakibatkan limpahan tindanan. Saiz ditetapkan apabila strim dibuat, dan setiap pembolehubah mempunyai saiz maksimum bergantung pada jenis data. Ini membolehkan anda mengehadkan saiz beberapa pembolehubah (seperti integer), dan memaksa anda untuk mengisytiharkan saiz jenis data yang lebih kompleks (seperti tatasusunan) terlebih dahulu, kerana timbunan tidak akan membenarkan mereka mengubahnya. Di samping itu, pembolehubah yang terletak pada timbunan sentiasa setempat.
Akhirnya, timbunan membolehkan anda mengurus memori dengan cara yang paling cekap - tetapi jika anda perlu menggunakan struktur data dinamik atau pembolehubah global, maka anda harus melihat timbunan.
Timbunan
Heap ialah stor memori, juga terletak dalam RAM, yang membenarkan peruntukan memori dinamik dan tidak berfungsi seperti timbunan: ia hanya gudang untuk pembolehubah anda. Apabila anda memperuntukkan sekeping memori pada timbunan untuk menyimpan pembolehubah, ia boleh diakses bukan sahaja dalam benang, tetapi sepanjang aplikasi. Inilah cara pembolehubah global ditakrifkan. Apabila aplikasi ditamatkan, semua memori yang diperuntukkan dikeluarkan. Saiz timbunan ditetapkan apabila aplikasi bermula, tetapi, tidak seperti timbunan, ia hanya terhad secara fizikal, dan ini membolehkan anda mencipta pembolehubah dinamik.
Anda berinteraksi dengan timbunan melalui rujukan, yang biasa dipanggil penunjuk - ini adalah pembolehubah yang nilainya adalah alamat pembolehubah lain. Apabila anda mencipta penunjuk, anda menunjuk ke lokasi memori pada timbunan, yang menetapkan nilai awal pembolehubah dan memberitahu program tempat untuk mengakses nilai tersebut. Oleh kerana sifat dinamik timbunan, CPU tidak mengambil bahagian dalam kawalannya; Dalam bahasa tanpa pengumpul sampah (C, C++), pembangun perlu mengosongkan kawasan memori secara manual yang tidak diperlukan lagi. Jika ini tidak dilakukan, kebocoran memori dan pemecahan mungkin berlaku, yang akan memperlahankan timbunan dengan ketara.
Berbanding dengan timbunan, timbunan adalah lebih perlahan kerana pembolehubah tersebar di seluruh memori dan bukannya duduk di atas timbunan. Pengurusan memori yang salah dalam timbunan membawa kepada kelembapan operasinya; bagaimanapun, ini tidak mengurangkan kepentingannya - jika anda perlu menggunakan pembolehubah dinamik atau global, gunakan timbunan.
Timbunan
Tindanan adalah struktur data yang paling popular dan mungkin paling penting dalam pengaturcaraan. Tindanan ialah peranti storan yang daripadanya unsur dialih keluar dalam susunan terbalik penambahannya. Ia seperti barisan yang tidak teratur, di mana yang pertama dilayan adalah yang terakhir masuk. Dalam literatur pengaturcaraan, singkatan diterima secara umum untuk menunjukkan disiplin baris gilir dan timbunan. Disiplin barisan ditetapkan FIFO, yang bermaksud Pertama Masuk Dahulu. Disiplin timbunan ditetapkan LIFO, terakhir masuk dahulu keluar (Terakhir Masuk Dahulu Keluar).
Timbunan boleh dianggap sebagai tiub dengan bahagian bawah pegas, terletak secara menegak. Hujung atas tiub terbuka, elemen boleh ditambah, atau, seperti yang mereka katakan, ditolak ke dalamnya. Istilah Inggeris biasa dalam hal ini sangat berwarna-warni; operasi menambah elemen pada tindanan ditandakan tolak, diterjemahkan sebagai "tolak, tolak." Elemen baharu yang ditambah menolak elemen yang sebelum ini diletakkan pada tindanan ke bawah satu kedudukan. Apabila elemen muncul dari timbunan, ia ditolak ke atas, dalam pop Inggeris (“menembak”).
Contoh timbunan ialah timbunan jerami, timbunan kertas di atas meja, timbunan pinggan, dsb. Di sinilah nama timbunan berasal, yang bermaksud timbunan dalam bahasa Inggeris. Plat dikeluarkan dari timbunan dalam susunan terbalik penambahannya. Hanya plat atas boleh diakses, i.e. pinggan di atas timbunan. Contoh yang baik juga ialah jalan buntu kereta api di mana kereta boleh disusun.
Tindanan digunakan agak kerap, dan dalam pelbagai situasi. Mereka bersatu dengan matlamat berikut: anda perlu menyimpan beberapa kerja yang belum selesai, jika anda perlu beralih kepada tugas lain. Tindanan digunakan untuk menyimpan sementara keadaan tugasan yang belum selesai. Selepas menyimpan keadaan, komputer beralih ke tugas lain. Setelah selesai pelaksanaannya, keadaan tugas tertunda dipulihkan daripada timbunan, dan komputer meneruskan operasi yang terganggu.
Mengapa timbunan digunakan untuk menyimpan keadaan kerja yang terganggu? Mari kita anggap bahawa komputer sedang melaksanakan tugas A. Semasa pelaksanaannya, keperluan timbul untuk melaksanakan tugas B. Keadaan tugas A diingati, dan komputer meneruskan untuk melaksanakan tugas B. Tetapi walaupun semasa melaksanakan tugasan B, komputer boleh bertukar ke tugasan C yang lain, dan ia perlu disimpan keadaan tugas B sebelum beralih ke C. Kemudian, setelah selesai C, keadaan tugas B akan dipulihkan dahulu, kemudian, setelah selesai B, keadaan tugas A. Oleh itu, pemulihan berlaku dalam urutan terbalik penjimatan, yang sepadan dengan disiplin tindanan.
Timbunan membolehkan anda mengatur rekursi, i.e. subrutin memanggil dirinya sendiri, sama ada secara langsung atau melalui rangkaian panggilan lain. Sebagai contoh, biarkan rutin A melaksanakan algoritma yang bergantung pada parameter input X dan mungkin pada keadaan data global. Untuk nilai X yang paling mudah, algoritma dilaksanakan secara langsung. Dalam kes nilai X yang lebih kompleks, algoritma dilaksanakan sebagai pengurangan kepada penggunaan algoritma yang sama untuk nilai X yang lebih mudah. Dalam kes ini, subrutin A mengakses dirinya sendiri, melepasi nilai X yang lebih mudah sebagai parameter. Dengan akses ini, nilai sebelumnya bagi parameter X, serta semua pembolehubah tempatan rutin A disimpan pada tindanan. Seterusnya, set baharu pembolehubah tempatan dan pembolehubah yang mengandungi nilai baharu (lebih ringkas) bagi parameter X dicipta. Subrutin A yang dipanggil beroperasi pada set pembolehubah baharu tanpa memusnahkan set sebelumnya. Pada penghujung panggilan, set lama pembolehubah tempatan dan keadaan lama parameter input X dipulihkan daripada timbunan, dan rutin diteruskan dari tempat ia berhenti.
Malah, anda tidak perlu menyimpan nilai pembolehubah tempatan subrutin pada timbunan dengan cara yang istimewa. Hakikatnya ialah pembolehubah tempatan subrutin (iaitu, pembolehubah dalamannya, berfungsi, yang dicipta pada permulaan pelaksanaannya dan dimusnahkan pada penghujungnya) diletakkan pada timbunan yang dilaksanakan dalam perkakasan berdasarkan RAM biasa. Pada permulaan kerjanya, subrutin mengambil ruang pada timbunan untuk pembolehubah setempatnya; kawasan ingatan dalam timbunan perkakasan ini biasanya dipanggil blok pembolehubah tempatan atau dalam bahasa Inggeris bingkai("bingkai"). Pada saat selesai kerja, subrutin membebaskan memori dengan mengalih keluar blok pembolehubah setempatnya daripada timbunan.
Selain pembolehubah tempatan, alamat pemulangan untuk panggilan subrutin disimpan pada tindanan perkakasan. Biarkan subrutin dipanggil pada satu ketika dalam program A B. Sebelum subrutin B dipanggil, alamat arahan berikutan arahan memanggil B disimpan pada tindanan. Inilah yang dipanggil alamat pemulangan ke atur cara A. Apabila ia selesai, subrutin B memaparkan alamat pemulangan program A daripada timbunan dan mengembalikan kawalan ke alamat tersebut. Oleh itu, komputer terus melaksanakan program A, bermula dengan arahan mengikuti arahan panggilan. Kebanyakan pemproses mempunyai arahan khas yang menyokong panggilan subrutin dengan terlebih dahulu menolak alamat pemulangan ke dalam tindanan dan kembali daripada subrutin pada alamat yang muncul dari tindanan. Biasanya arahan panggilan dipanggil panggilan, arahan kembali dipanggil pulangan.
Parameter subrutin atau fungsi juga ditolak ke tindanan sebelum ia dipanggil. Susunan ia diletakkan pada timbunan bergantung pada konvensyen bahasa peringkat tinggi. Jadi, dalam bahasa C atau C++, hujah fungsi pertama berada di bahagian atas timbunan, yang kedua di bawahnya, dan seterusnya. Dalam Pascal, ia adalah sebaliknya: hujah terakhir fungsi berada di bahagian atas timbunan. (Inilah sebabnya, dengan cara ini, fungsi dengan bilangan argumen yang berubah-ubah, seperti printf, adalah mungkin dalam C, tetapi tidak dalam Pascal.)
Dalam Fortran-4, salah satu bahasa pengaturcaraan tertua dan paling berjaya, hujah dihantar melalui kawasan memori khas, yang mungkin tidak terletak pada timbunan, kerana sehingga akhir 70-an abad ke-20 masih terdapat komputer seperti Komputer IBM 360 atau ES tanpa tindanan pelaksanaan perkakasan. Alamat pemulangan juga tidak disimpan pada timbunan, tetapi dalam sel memori yang ditetapkan untuk setiap subrutin. Pengaturcara memanggil memori sedemikian statik dalam erti kata bahawa pembolehubah statik sentiasa menduduki tempat yang sama dalam ingatan pada bila-bila masa semasa pelaksanaan program. Apabila hanya menggunakan memori statik, rekursi tidak boleh dilakukan kerana nilai sebelumnya pembolehubah tempatan dimusnahkan apabila panggilan baharu dibuat. Rujukan Fortran 4 hanya menggunakan pembolehubah statik, dan pengulangan adalah dilarang. Sehingga kini, bahasa Fortran digunakan secara meluas dalam pengiraan saintifik dan kejuruteraan, bagaimanapun, piawaian Fortran-90 moden telah memperkenalkan memori tindanan, menghapuskan kekurangan versi bahasa terdahulu.
