Tumpuk di C ++ STL dengan Contoh

Daftar Isi:

Anonim

Apa itu std :: stack?

Tumpukan adalah struktur data yang beroperasi berdasarkan teknik LIFO (Last In First Out). Std :: stack memungkinkan elemen ditambahkan dan dihapus dari satu ujung saja.

Kelas std :: stack adalah adaptor kontainer. Objek kontainer menyimpan data dari tipe data serupa. Anda dapat membuat tumpukan dari berbagai kontainer urutan. Jika tidak ada penampung yang disediakan, penampung deque akan digunakan secara default. Adaptor penampung tidak mendukung iterator, sehingga tidak dapat digunakan untuk memanipulasi data.

Dalam tutorial C ++ ini, Anda akan belajar

  • Apa itu std :: stack?
  • Stack Syntax
  • Jenis Anggota
  • Operasi di Stack
  • Implementasi Stack
  • push () dan pop ()
  • kosong (), ukuran (), atas ()
  • emplace () dan swap ()
  • Tumpuk di STL

Stack Syntax

Untuk membuat tumpukan, kita harus menyertakan file header dalam kode kita. Kami kemudian menggunakan sintaks ini untuk mendefinisikan std :: stack:

template  > class stack;
  • Type - adalah Jenis elemen yang ada di std :: stack. Ini bisa berupa tipe C ++ yang valid atau bahkan tipe yang ditentukan pengguna.
  • Penampung - adalah Jenis objek penampung yang mendasari.

Jenis Anggota

Berikut adalah tipe anggota tumpukan:

  • value_type- Parameter template pertama, T. Ini menunjukkan jenis elemen.
  • container_type- Parameter template kedua, Container. Ini menunjukkan jenis wadah yang mendasari.
  • size_type- Tipe integral tak bertanda tangan.

Operasi di Stack

Tumpukan C ++ mendukung operasi dasar berikut:

  • push - Menambahkan / mendorong item ke dalam tumpukan.
  • pop - Ini menghapus / memunculkan item dari tumpukan.
  • peek - Mengembalikan item teratas dari tumpukan tanpa mengeluarkannya.
  • isFull - Memeriksa apakah tumpukan sudah penuh.
  • isEmpty - Memeriksa apakah tumpukan kosong.

Implementasi Stack

Langkah 1) Awalnya kami memiliki tumpukan kosong. Bagian atas tumpukan kosong disetel ke -1.

Langkah 2) Selanjutnya, kami telah mendorong elemen 5 ke dalam tumpukan. Bagian atas tumpukan akan menunjuk ke elemen 5.

Langkah 3) Selanjutnya, kami telah mendorong elemen 50 ke dalam tumpukan. Bagian atas tumpukan bergeser dan menunjuk ke elemen 50.

Langkah 4) Kami kemudian melakukan operasi pop, menghapus elemen teratas dari tumpukan. Elemen 50 muncul dari tumpukan. Bagian atas tumpukan sekarang menunjuk ke elemen 5.

push () dan pop ()

Fungsi stack :: push () menambahkan item baru ke bagian atas stack. Ukuran tumpukan bertambah 1 setelah penyisipan. Fungsi tersebut mengambil sintaks ini:

stack.push(value)

Nilainya adalah item yang akan dimasukkan ke dalam tumpukan.

Fungsi stack :: pop () menghapus elemen teratas dari stack. Ini adalah item tumpukan terbaru. Ukuran tumpukan dikurangi 1 setelah penghapusan. Berikut adalah sintaks fungsinya:

stack.pop()

Fungsi ini tidak membutuhkan 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();}}

Keluaran:

Berikut tangkapan layar kodenya:

Penjelasan Kode:

  1. Sertakan file header iostream dalam kode kami untuk menggunakan fungsinya.
  2. Sertakan file stack header dalam kode kami untuk menggunakan fungsinya.
  3. Sertakan namespace std dalam kode kita untuk menggunakan kelasnya tanpa memanggilnya.
  4. Panggil fungsi main (). Logika program harus ditambahkan dalam fungsi ini.
  5. Buat tumpukan st untuk menyimpan nilai integer.
  6. Gunakan fungsi push () untuk memasukkan nilai 10 ke dalam tumpukan.
  7. Gunakan fungsi push () untuk memasukkan nilai 20 ke dalam tumpukan.
  8. Gunakan fungsi push () untuk memasukkan nilai 30 ke dalam tumpukan.
  9. Gunakan fungsi push () untuk memasukkan nilai 40 ke dalam tumpukan.
  10. Gunakan fungsi pop () untuk menghapus elemen teratas dari tumpukan, yaitu 40. Elemen teratas sekarang menjadi 30.
  11. Gunakan fungsi pop () untuk menghapus elemen teratas dari tumpukan, yaitu 30. Elemen teratas sekarang menjadi 20.
  12. Gunakan fungsi while loop dan empty () untuk memeriksa apakah stack TIDAK kosong. The! adalah operator NOT.
  13. Mencetak konten tumpukan saat ini di konsol.
  14. Panggil fungsi pop () di stack.
  15. Akhir badan loop sementara.
  16. Akhir badan fungsi main ().

kosong (), ukuran (), atas ()

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

  • kosong () - memeriksa apakah tumpukan kosong atau tidak.
  • size () - mengembalikan ukuran tumpukan, yaitu jumlah elemen dalam tumpukan.
  • top () - mengakses elemen tumpukan di bagian 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;}

Keluaran:

Berikut tangkapan layar kodenya:

Penjelasan Kode:

  1. Sertakan file header iostream dalam kode kami untuk menggunakan fungsinya.
  2. Sertakan file stack header dalam kode kami untuk menggunakan fungsinya.
  3. Sertakan namespace std dalam program kita untuk menggunakan kelasnya tanpa memanggilnya.
  4. Buat fungsi createStack yang bisa kita gunakan untuk membuat tumpukan mystack. Tumpukan akan menampung satu set bilangan bulat.
  5. Awal badan fungsi createStack.
  6. Buat instance dari tipe data mystack dan beri nama ms.
  7. Gunakan while loop dan fungsi empty () untuk memeriksa apakah stack kosong.
  8. Awal badan loop sementara.
  9. Gunakan fungsi top () yang disimpan di bagian atas tumpukan. Karakter \ t akan membuat tab baru.
  10. Gunakan fungsi pop () untuk menghapus elemen di bagian atas tumpukan.
  11. Akhir badan loop sementara.
  12. Cetak baris kosong di konsol.
  13. Akhir badan fungsi createStack.
  14. Panggil fungsi main (). Logika program harus ditambahkan di dalam tubuh fungsi main ().
  15. Awal dari isi fungsi main ().
  16. Buat objek tumpukan st.
  17. Gunakan fungsi push () untuk memasukkan elemen 32 ke dalam tumpukan.
  18. Gunakan fungsi push () untuk memasukkan elemen 21 ke dalam tumpukan.
  19. Gunakan fungsi push () untuk memasukkan elemen 39 ke dalam tumpukan.
  20. Gunakan fungsi push () untuk memasukkan elemen 89 ke dalam tumpukan.
  21. Gunakan fungsi push () untuk memasukkan elemen 25 ke dalam tumpukan.
  22. Cetak beberapa teks di konsol.
  23. Panggil fungsi createStack untuk menjalankan operasi penyisipan di atas ke dalam tumpukan.
  24. Cetak ukuran tumpukan di konsol bersama teks lainnya.
  25. Cetak elemen di bagian atas tumpukan di konsol.
  26. Cetak beberapa teks di konsol.
  27. Hapus elemen di bagian atas tumpukan. Ini kemudian akan mengembalikan elemen yang tersisa di tumpukan.
  28. Panggil fungsi createStack untuk menjalankan operasi di atas.
  29. Program harus mengembalikan nilai setelah berhasil diselesaikan.
  30. Akhir badan fungsi main ().

emplace () dan swap ()

Ini adalah fungsi tumpukan bawaan lainnya:

  • emplace () - konstruksi kemudian memasukkan elemen baru ke atas tumpukan.
  • swap () - menukar konten tumpukan dengan konten tumpukan 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();}}

Keluaran:

Berikut tangkapan layar kodenya:

Penjelasan Kode:

  1. Sertakan file header iostream dalam kode kami untuk menggunakan fungsinya.
  2. Sertakan file stack header dalam kode kami untuk menggunakan fungsinya.
  3. Sertakan file header cstdlib dalam kode kami untuk menggunakan fungsinya.
  4. Sertakan namespace std dalam kode kita untuk menggunakan kelasnya tanpa memanggilnya.
  5. Panggil fungsi main (). Logika program akan ditambahkan di dalam tubuh fungsi ini.
  6. Deklarasikan tumpukan bernama st1 untuk menyimpan nilai integer.
  7. Deklarasikan tumpukan bernama st2 untuk menyimpan nilai integer.
  8. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 12 ke dalam tumpukan bernama st1.
  9. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 19 ke dalam tumpukan bernama st1.
  10. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 20 ke dalam tumpukan bernama st2.
  11. Gunakan fungsi emplace () untuk memasukkan bilangan bulat 23 ke dalam tumpukan bernama st2.
  12. Gunakan fungsi swap () untuk menukar konten dari dua tumpukan, st1 dan st2. Isi tumpukan st1 harus dipindahkan ke tumpukan st2. Isi tumpukan st2 harus dipindahkan ke tumpukan st1.
  13. Cetak beberapa teks di konsol.
  14. Gunakan pernyataan while dan fungsi empty () untuk memeriksa apakah tumpukan st1 tidak kosong.
  15. Cetak konten tumpukan st1 di konsol. "" Menambahkan spasi di antara elemen tumpukan saat mencetaknya di konsol.
  16. Jalankan fungsi pop () pada stack st1 untuk menghapus elemen teratas.
  17. Akhir badan pernyataan while.
  18. Cetak beberapa teks di konsol. Endl adalah kata kunci C ++ untuk baris akhir. Ini menggerakkan kursor mouse ke baris berikutnya untuk mulai mencetak dari sana.
  19. Gunakan pernyataan while dan fungsi empty () untuk memeriksa apakah tumpukan st2 tidak kosong.
  20. Cetak isi tumpukan st2 di konsol. "" Menambahkan spasi di antara elemen tumpukan saat mencetaknya di konsol.
  21. Jalankan fungsi pop () pada stack st2 untuk menghapus elemen teratas.
  22. Akhir badan pernyataan while.
  23. Akhir badan fungsi main ().

Tumpuk di STL

STL (Standard Template Library) dilengkapi dengan kelas template yang menyediakan struktur data C ++ umum. Oleh karena itu, tumpukan juga dapat diterapkan di STL. Kami hanya menyertakan pustaka ini dalam kode kami dan menggunakannya untuk menentukan tumpukan.

stack st;

Sintaks di atas mendeklarasikan tumpukan st ke elemen tipe 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();}

Keluaran:

Berikut tangkapan layar kodenya:

Penjelasan Kode:

  1. Sertakan file header iostream dalam kode kami untuk menggunakan fungsinya.
  2. Sertakan file stack header dalam kode kami untuk menggunakan fungsinya.
  3. Sertakan file header cstdlib dalam kode kami untuk menggunakan fungsinya.
  4. Sertakan namespace std dalam kode kita untuk menggunakan kelasnya tanpa memanggilnya.
  5. Panggil fungsi main (). Logika program harus ditambahkan di dalam tubuh fungsi ini.
  6. Deklarasikan tumpukan st untuk menyimpan data integer.
  7. Tambahkan elemen 12 ke tumpukan.
  8. Tambahkan elemen 19 ke tumpukan.
  9. Tambahkan elemen 20 ke tumpukan.
  10. Cetak elemen di bagian atas tumpukan di konsol.
  11. Cetak ukuran tumpukan di konsol.
  12. Akhir badan fungsi main ().

Ringkasan:

  • Tumpukan adalah struktur data yang beroperasi berdasarkan teknik LIFO (Last In first Out).
  • Std :: stack hanya mengizinkan item ditambahkan dan dihapus dari satu ujung.
  • Kelas std :: stack adalah adaptor kontainer, yang menampung item dari tipe data serupa.
  • Tumpukan dapat dibuat dari berbagai wadah urutan.
  • Jika Anda tidak menyediakan container, container deque akan digunakan secara default.
  • Fungsi push () adalah untuk memasukkan item ke dalam tumpukan.
  • Fungsi pop () adalah untuk menghapus item teratas dari langkah.
  • Fungsi empty () untuk memeriksa apakah tumpukan kosong atau tidak.