Tumpukan dalam C ++ STL dengan Contoh

Isi kandungan:

Anonim

Apakah std :: timbunan?

Stack adalah struktur data yang beroperasi berdasarkan teknik LIFO (Last In First Out). Std :: stack membolehkan elemen ditambahkan dan dikeluarkan dari satu hujung sahaja.

Kelas std :: stack adalah penyesuai bekas. Objek kontena menyimpan data dari jenis data yang serupa. Anda boleh membuat timbunan dari pelbagai bekas urutan. Sekiranya tidak ada bekas yang disediakan, deque container akan digunakan secara lalai. Penyesuai kontena tidak menyokong iterator, jadi tidak dapat digunakan untuk memanipulasi data.

Dalam tutorial C ++ ini, anda akan belajar

  • Apakah std :: timbunan?
  • Sintaksis Stack
  • Jenis Ahli
  • Operasi di Stack
  • Pelaksanaan Stack
  • tekan () dan pop ()
  • kosong (), saiz (), atas ()
  • letakkan () dan tukar ()
  • Tumpukan di STL

Sintaksis Stack

Untuk membuat timbunan, kita mesti memasukkan fail tajuk dalam kod kita. Kami kemudian menggunakan sintaks ini untuk menentukan std :: stack:

template  > class stack;
  • Type - adalah Jenis elemen yang terdapat dalam std :: stack. Ia boleh menjadi jenis C ++ yang sah atau bahkan jenis yang ditentukan pengguna.
  • Container - adalah Jenis objek kontena yang mendasari.

Jenis Ahli

Berikut adalah jenis ahli timbunan:

  • value_type- Parameter templat pertama, T. Ini menunjukkan jenis elemen.
  • container_type- Parameter templat kedua, Container. Ini menunjukkan jenis bekas yang mendasari.
  • size_type- Jenis kamiran yang tidak ditandatangani.

Operasi di Stack

Tumpukan C ++ menyokong operasi asas berikut:

  • tolak - Ia menambah / menolak item ke dalam timbunan.
  • pop - Ia mengeluarkan / mengeluarkan item dari timbunan.
  • mengintip - Mengembalikan item teratas timbunan tanpa mengeluarkannya.
  • isFull - Menyemak sama ada timbunan penuh.
  • isEmpty - Menyemak sama ada timbunan kosong.

Pelaksanaan Stack

Langkah 1) Pada mulanya kami mempunyai timbunan kosong. Bahagian atas timbunan kosong ditetapkan ke -1.

Langkah 2) Seterusnya, kami telah memasukkan elemen 5 ke dalam timbunan. Bahagian atas timbunan akan menunjukkan elemen 5.

Langkah 3) Seterusnya, kami telah memasukkan elemen 50 ke dalam timbunan. Bahagian atas timbunan beralih dan menunjuk ke elemen 50.

Langkah 4) Kami kemudian melakukan operasi pop, mengeluarkan elemen teratas dari timbunan. Elemen 50 muncul dari timbunan. Bahagian atas timbunan sekarang menunjukkan elemen 5.

tekan () dan pop ()

Fungsi stack :: push () menambah item baru ke bahagian atas timbunan. Ukuran timbunan dinaikkan sebanyak 1 selepas penyisipan. Fungsi menggunakan sintaks ini:

stack.push(value)

Nilai adalah item yang akan dimasukkan ke dalam timbunan.

Fungsi stack :: pop () membuang elemen atas timbunan. Ini adalah item timbunan terbaru. Ukuran timbunan dikurangkan sebanyak 1 selepas penyingkiran. Berikut adalah sintaks fungsi:

stack.pop()

Fungsi tidak memerlukan parameter.

Contoh 1:

#include #include using namespace std;int main() {stack st;st.push(10);st.push(20);st.push(30);st.push(40);st.pop();st.pop();while (!st.empty()) {cout << ' ' << st.top();st.pop();}}

Pengeluaran:

Berikut adalah tangkapan skrin kod:

Penjelasan Kod:

  1. Sertakan fail tajuk iostream dalam kod kami untuk menggunakan fungsinya.
  2. Sertakan fail header timbunan dalam kod kami untuk menggunakan fungsinya.
  3. Sertakan ruang nama std dalam kod kami untuk menggunakan kelasnya tanpa memanggilnya.
  4. Panggil fungsi utama (). Logik program harus ditambah dalam fungsi ini.
  5. Buat timbunan untuk menyimpan nilai integer.
  6. Gunakan fungsi tekan () untuk memasukkan nilai 10 ke dalam timbunan.
  7. Gunakan fungsi tekan () untuk memasukkan nilai 20 ke dalam timbunan.
  8. Gunakan fungsi tekan () untuk memasukkan nilai 30 ke dalam timbunan.
  9. Gunakan fungsi tekan () untuk memasukkan nilai 40 ke dalam timbunan.
  10. Gunakan fungsi pop () untuk mengeluarkan elemen atas dari timbunan, iaitu, 40. Elemen teratas kini menjadi 30.
  11. Gunakan fungsi pop () untuk mengeluarkan elemen teratas dari timbunan, iaitu 30. Elemen teratas kini menjadi 20.
  12. Gunakan fungsi loop sementara dan kosong () untuk memeriksa sama ada stack TIDAK kosong. The! adalah pengendali NOT.
  13. Mencetak kandungan timbunan semasa di konsol.
  14. Panggil fungsi pop () pada timbunan.
  15. Hujung badan gelung sementara.
  16. Akhir badan fungsi utama ().

kosong (), saiz (), atas ()

Tumpukan mempunyai fungsi bawaan yang dapat Anda gunakan untuk bermain-main dengan timbunan dan nilainya. Ini termasuk:

  • kosong () - memeriksa sama ada timbunan kosong atau tidak.
  • size () - mengembalikan ukuran timbunan, iaitu jumlah elemen dalam timbunan.
  • atas () - mengakses elemen timbunan di bahagian atas.

Contoh 2:

#include #include using namespace std;void createStack(stack  mystack){stack  ms = mystack;while (!ms.empty()){cout << '\t' << ms.top();ms.pop();}cout << '\n';}int main(){stack  st;st.push(32);st.push(21);st.push(39);st.push(89);st.push(25);cout << "The stack st is: ";createStack(st);cout << "\n st.size() : " << st.size();cout << "\n st.top() : " << st.top();cout << "\n st.pop() : ";st.pop();createStack(st);return 0;}

Pengeluaran:

Berikut adalah tangkapan skrin kod:

Penjelasan Kod:

  1. Sertakan fail header iostream dalam kod kami untuk menggunakan fungsinya.
  2. Sertakan fail header timbunan dalam kod kami untuk menggunakan fungsinya.
  3. Sertakan ruang nama std dalam program kami untuk menggunakan kelasnya tanpa memanggilnya.
  4. Buat fungsi createStack yang dapat kita gunakan untuk membuat stack mystack. Tumpukan akan menyimpan satu set bilangan bulat.
  5. Permulaan fungsi fungsi createStack.
  6. Buat contoh jenis data mystack dan beri nama ms.
  7. Gunakan loop sementara dan fungsi kosong () untuk memeriksa sama ada timbunan kosong.
  8. Permulaan gelung sementara.
  9. Gunakan fungsi atas () yang disimpan di bahagian atas timbunan. Watak \ t akan membuat tab baru.
  10. Gunakan fungsi pop () untuk menghapus elemen di bahagian atas timbunan.
  11. Hujung badan gelung sementara.
  12. Cetak garis kosong pada konsol.
  13. Bahagian akhir fungsi createStack.
  14. Panggil fungsi utama (). Logik program harus ditambah dalam badan fungsi utama ().
  15. Permulaan badan fungsi utama ().
  16. Buat stack objek st.
  17. Gunakan fungsi tekan () untuk memasukkan elemen 32 ke dalam timbunan.
  18. Gunakan fungsi tekan () untuk memasukkan elemen 21 ke dalam timbunan.
  19. Gunakan fungsi tekan () untuk memasukkan elemen 39 ke dalam timbunan.
  20. Gunakan fungsi tekan () untuk memasukkan elemen 89 ke dalam timbunan.
  21. Gunakan fungsi tekan () untuk memasukkan elemen 25 ke dalam timbunan.
  22. Cetak sebilangan teks pada konsol.
  23. Panggil fungsi createStack untuk menjalankan operasi memasukkan di atas ke dalam timbunan.
  24. Cetak ukuran timbunan pada konsol bersama teks lain.
  25. Cetak elemen di bahagian atas timbunan di konsol.
  26. Cetak sebilangan teks pada konsol.
  27. Padamkan elemen di bahagian atas timbunan. Ia kemudian akan mengembalikan unsur-unsur yang tinggal di timbunan.
  28. Panggil fungsi createStack untuk menjalankan operasi di atas.
  29. Program mesti mengembalikan nilai setelah berjaya diselesaikan.
  30. Hujung badan fungsi utama ().

letakkan () dan tukar ()

Ini adalah fungsi timbunan terbina dalam yang lain:

  • emplace () - konstruk kemudian memasukkan elemen baru ke bahagian atas timbunan.
  • swap () - menukar isi timbunan dengan isi timbunan yang lain.

Contoh 3:

#include #include #include using namespace std;int main() {stack st1;stack st2;st1.emplace(12);st1.emplace(19);st2.emplace(20);st2.emplace(23);st1.swap(st2);cout << "st1 = ";while (!st1.empty()) {cout << st1.top() << " ";st1.pop();}cout << endl << "st2 = ";while (!st2.empty()) {cout << st2.top() << " ";st2.pop();}}

Pengeluaran:

Berikut adalah tangkapan skrin kod:

Penjelasan Kod:

  1. Sertakan fail tajuk iostream dalam kod kami untuk menggunakan fungsinya.
  2. Sertakan fail header timbunan dalam kod kami untuk menggunakan fungsinya.
  3. Sertakan fail header cstdlib dalam kod kami untuk menggunakan fungsinya.
  4. Sertakan ruang nama std dalam kod kami untuk menggunakan kelasnya tanpa memanggilnya.
  5. Panggil fungsi utama (). Logik program akan ditambahkan dalam badan fungsi ini.
  6. Menyatakan timbunan bernama st1 untuk menyimpan nilai integer.
  7. Menyatakan timbunan bernama st2 untuk menyimpan nilai integer.
  8. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 12 ke dalam timbunan bernama st1.
  9. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 19 ke dalam timbunan bernama st1.
  10. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 20 ke dalam timbunan bernama st2.
  11. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 23 ke dalam timbunan bernama st2.
  12. Gunakan fungsi swap () untuk menukar isi dua timbunan, st1 dan st2. Kandungan stack st1 harus dipindahkan ke stack st2. Kandungan stack st2 harus dipindahkan ke stack st1.
  13. Cetak sebilangan teks pada konsol.
  14. Gunakan pernyataan sementara dan fungsi kosong () untuk memeriksa sama ada timbunan st1 tidak kosong.
  15. Cetak isi timbunan st1 pada konsol. The "" menambah ruang antara elemen timbunan semasa mencetaknya di konsol.
  16. Jalankan fungsi pop () pada stack st1 untuk membuang elemen atas.
  17. Bahagian akhir pernyataan sementara.
  18. Cetak sebilangan teks pada konsol. Endl adalah kata kunci C ++ untuk garis akhir. Ia menggerakkan kursor tetikus ke baris seterusnya untuk mula mencetak dari sana.
  19. Gunakan pernyataan sementara dan fungsi kosong () untuk memeriksa sama ada timbunan st2 tidak kosong.
  20. Cetak isi timbunan st2 pada konsol. The "" menambah ruang antara elemen timbunan semasa mencetaknya di konsol.
  21. Jalankan fungsi pop () pada stack st2 untuk membuang elemen atas.
  22. Bahagian akhir pernyataan sementara.
  23. Akhir badan utama () fungsi.

Tumpukan di STL

STL (Standard Template Library) dilengkapi dengan kelas templat yang menyediakan struktur data C ++ yang biasa. Oleh itu, timbunan juga dapat dilaksanakan dalam STL. Kami hanya memasukkan pustaka ini dalam kod kami dan menggunakannya untuk menentukan timbunan.

stack st;

Sintaks di atas mengisytiharkan timbunan kepada elemen jenis data T.

Contoh 3:

#include #include #include using namespace std;int main() {stack st;st.push(12);st.push(19);st.push(20);cout << st.top();cout << st.size();}

Pengeluaran:

Berikut adalah tangkapan skrin kod:

Penjelasan Kod:

  1. Sertakan fail tajuk iostream dalam kod kami untuk menggunakan fungsinya.
  2. Sertakan fail header timbunan dalam kod kami untuk menggunakan fungsinya.
  3. Sertakan fail header cstdlib dalam kod kami untuk menggunakan fungsinya.
  4. Sertakan ruang nama std dalam kod kami untuk menggunakan kelasnya tanpa memanggilnya.
  5. Panggil fungsi utama (). Logik program harus ditambahkan dalam badan fungsi ini.
  6. Menyatakan tumpukan untuk menyimpan data integer.
  7. Tambahkan elemen 12 ke timbunan.
  8. Tambahkan elemen 19 ke timbunan.
  9. Tambahkan elemen 20 ke timbunan.
  10. Cetak elemen di bahagian atas timbunan di konsol.
  11. Cetak ukuran timbunan pada konsol.
  12. Bahagian akhir fungsi utama ().

Ringkasan:

  • Stack adalah struktur data yang beroperasi berdasarkan teknik LIFO (Last In first Out).
  • Std :: stack hanya membenarkan item ditambahkan dan dikeluarkan dari satu hujung.
  • Kelas std :: stack adalah penyesuai kontena, memegang item dari jenis data yang serupa.
  • Tumpukan boleh dibuat dari pelbagai bekas turutan.
  • Sekiranya anda tidak menyediakan bekas, bekas deque akan digunakan secara lalai.
  • Fungsi push () adalah untuk memasukkan item ke dalam timbunan.
  • Fungsi pop () adalah untuk membuang item teratas dari langkah.
  • Fungsi kosong () adalah untuk memeriksa sama ada timbunan kosong atau tidak.