Tumpukan tidak lain adalah struktur data linier tempat penyisipan dan penghapusan hanya terjadi di satu ujung. Operasi penyisipan memiliki nama khusus yang dikenal sebagai PUSH dan operasi penghapusan juga memiliki nama khusus yang disebut POP. PUSH dan POP adalah dua operasi dasar yang hanya dapat dilakukan di tumpukan tertentu. Ini adalah sekelompok lokasi memori dan lokasi memori terkait dengan memori baca atau memori tulis. Ini digunakan untuk menyimpan informasi biner selama eksekusi program, ketika kita menjalankan program apa pun maka konten program itu akan disimpan di stack. Itu mengikuti Terakhir Masuk Pertama Keluar (LIFO) dan hanya digunakan untuk menyimpan dan mengambil data tetapi tidak digunakan untuk menyimpan data. Penjelasan singkat tentang stack / stack pointer dibahas di bawah ini.
Apa itu Stack / Stack Pointer?
Definisi: Tumpukan adalah perangkat penyimpanan, digunakan untuk menyimpan informasi atau data dengan cara LIFO (Last In First Out). Setiap kali kita memasukkan data dalam bentuk LIFO, elemen yang harus dihapus terlebih dahulu adalah elemen inserter terakhir, sehingga elemen yang disisipkan terakhir dikeluarkan terlebih dahulu. Ini adalah unit memori dalam register alamat yang disebut stack pointer (SP). Penunjuk tumpukan selalu menunjukkan elemen teratas dalam tumpukan yang berarti lokasi mana data harus dimasukkan.
Jenis Stack
Ada dua jenis tumpukan yaitu tumpukan register dan tumpukan memori.
Daftarkan Stack
Tumpukan register juga merupakan perangkat memori yang ada di unit memori, tetapi hanya menangani sejumlah kecil data. Kedalaman tumpukan selalu terbatas dalam tumpukan register karena ukuran tumpukan register sangat kecil dibandingkan dengan memori.
Operasi Dorong di Register Stack
Langkah 1: Penunjuk tumpukan bertambah 1.
SP ← SP + 1
Langkah 2: Masukkan data ke dalam tumpukan.
1000 [SP] ← CT
Dimana DR adalah Register Data
Step3: Periksa apakah tumpukan sudah penuh atau tidak
jika (sp = 0) maka (penuh ← 1)
Step4: Tandai tidak kosong
kosong ← 0
Operasi Pop di Register Stack
Langkah 1: Baca data dari tumpukan.
DR ← M [SP]
Langkah 2: Penurunan titik tumpukan.
SP ← SP-1
Step3: Periksa apakah tumpukan kosong atau tidak
jika sp = 0 maka kosongkan ← 1
Organisasi tumpukan dari tumpukan register 64-bit ditunjukkan pada gambar di bawah ini.
Daftarkan Organisasi Stack
Memory Stack
Dalam tumpukan memori, kedalaman tumpukan fleksibel. Ini menempati sejumlah besar data memori, sedangkan dalam tumpukan register hanya sejumlah kata memori yang akan disimpan.
Operasi Dorong di Memory Stack
Langkah 1: SP ← SP-1
Langkah 2: 1000 [SP] ← CT
Operasi pop di Memory Stack
Langkah 1: DR ← M [SP]
Langkah 2: SP ← SP-1
Bandingkan dengan unit register, unit memori menyimpan data dalam jumlah besar. Gambar tumpukan memori ditunjukkan pada gambar di bawah ini.
Memory Stack
Unit memori total dibagi menjadi tiga bagian, unit memori pertama memiliki program (tidak lain adalah instruksi), bagian kedua adalah data (operan) dan bagian ketiga adalah stack. Instruksi program selalu disimpan di penghitung program (PC), register data diidentifikasi oleh register alamat (AR). Alamat 3000 hingga 4001 digunakan untuk tumpukan dan item atau elemen pertama disimpan di 4001.
Stack / Stack Pointer di 8085 Mikroprosesor
Tampilan programmer dari 8085 mikroprosesor berisi register tujuan umum dan register tujuan khusus . Register tujuan umum adalah A, B, C, D, E, H, L, dan register tujuan khusus adalah SP (Stack Pointer) dan PC (Program Counter). Tampilan programmer dari 8.085 mikroprosesor ditunjukkan pada gambar di bawah ini.
Tampilan Programmer 8085
Stack pointer adalah register 16-bit yang berisi alamat memori, misalkan isi stack pointer (SP) adalah FC78H, maka mikroprosesor 8085 akan menafsirkannya. Lokasi memori memiliki informasi yang berguna dari FC78H hingga FFFH dan dari FC77H hingga 0000H lokasi memori tidak memiliki informasi yang berguna. Interpretasi dari stack pointer ditunjukkan pada gambar di bawah ini.
Interpretasi Stack Pointer
Operasi Dasar Stack / Stack Pointer
Ada dua operasi tumpukan yaitu: operasi PUSH dan operasi POP.
Operasi PUSH
PUSH berarti mendorong atau memasukkan elemen ke dalam tumpukan. Operasi PUSH selalu menambah penunjuk tumpukan dan operasi POP selalu mengurangi penunjuk tumpukan. Dalam kasus operasi push, kita harus memeriksa apakah ada ruang kosong yang tersedia atau tidak. Jika ruang kosong tersedia, kita dapat pergi ke operasi push, jika ruang kosong tidak tersedia maka terjadi pesan kesalahan yang melimpah. Overflow harus diperiksa dalam kasus operasi push masing-masing. Operasi dasar push dan pop ditunjukkan pada gambar di bawah ini.
Pengoperasian Dasar PUSH dan POP
Gambar (a) adalah tumpukan. Jika Anda ingin mendorong elemen yang merupakan penyisipan elemen ke dalam tumpukan, Anda harus mendorong (s, a), di mana 's' tidak lain adalah tumpukan. Dalam tumpukan, kami menempatkan elemen 'a' dan operasi ini ditunjukkan pada gambar (b). Lihat gambar (3), misalkan stack berisi tiga elemen a, b, c, dan stack diisi dengan satu elemen.
Jika Anda ingin menyisipkan elemen keempat-'d 'menggunakan push (s, d), tetapi tidak ada ruang yang tersedia untuk menyisipkan elemen tersebut, ini menunjukkan bahwa tumpukan meluap. Terminologi overflow digunakan saat tumpukan penuh dan algoritme operasi dorong ditampilkan di bawah.
dorong (tumpukan [], atas, tumpukan maks, item)
jika (top == maxstack-1)
{
cetak 'luapan'
}
lain
{
atas = atas + 1
tumpukan [atas] = item
}
akhir
Operasi POP
POP berarti menghapus elemen di bagian atas tumpukan. Dalam kasus operasi pop, kita harus memeriksa apakah tumpukan awalnya kosong atau tidak. Jika tumpukan awalnya kosong maka terjadi situasi aliran bawah. Misalkan tumpukan masih kosong Anda ingin memunculkan elemen di tumpukan tetapi tidak ada elemen di tumpukan maka itu mengarah ke tumpukan underflow.
Arus bawah harus diperiksa dalam kasus operasi pop masing-masing. Dalam operasi pop, elemen teratas apa pun yang ada di tumpukan yang harus dimunculkan atau dihapus, jadi tidak perlu menyebutkan elemen mana yang akan dimunculkan, secara default elemen paling atas akan dimunculkan. Algoritma operasi pop ditampilkan di bawah ini.
pop (tumpukan [], atas, item)
jika (atas == - 1)
{
cetak 'underflow'
}
lain
{
item = tumpukan [atas]
top = top-1
}
Contoh
Elemen-elemen tersebut disisipkan dalam urutan sebagai A, B, C, D, E, ini mewakili tumpukan dari lima elemen. Pada gambar (a), kita ingin menekan elemen 'A' pada stack kemudian top menjadi nol (top = 0), demikian pula top = 1 ketika elemen 'B' didorong, top = 2 ketika elemen 'C' didorong, top = 3 saat elemen 'D' didorong, dan top = 4 saat elemen 'E' didorong.
Jadi apapun elemen yang saya ambil ditempatkan di stack, sekarang stack sudah penuh. Jika Anda ingin mendorong elemen lain, tidak ada tempat di tumpukan, jadi ini menunjukkan luapan. Sekarang stack sudah penuh jika ingin memunculkan elemen 'E' elemen harus di hapus terlebih dahulu. Operasi dorong ditunjukkan pada gambar di bawah ini.
Operasi Dorong
Kami harus menggunakan operasi pop untuk menghapus elemen dalam tumpukan. Jadi sebutkan saja pop () jangan tulis argumen di pop karena secara default menghapus elemen teratas. Elemen 'E' pertama dihapus berikutnya elemen 'D'… .. 'A'. Ketika elemen teratas dihapus maka nilai teratas berkurang. Ketika top = -1 tumpukan menunjukkan aliran bawah. Operasi pop ditunjukkan pada gambar di bawah ini.
Operasi POP
Jadi begini penjelasan bagaimana elemen disisipkan dan dihapus di stack dengan menggunakan operasi push and pop.
Aplikasi
Aplikasi penunjuk stack / stack adalah
- Pembalikan string
- Tanda kurung yang seimbang
- UNDO / FINGER
- Tumpukan sistem untuk catatan aktivasi
- Infix, prefix, postfix, ekspresi
FAQ
1). Apa penunjuk tumpukan di lengan?
Register penunjuk tumpukan (R13) digunakan sebagai penunjuk ke tumpukan aktif di ARM.
2). Mengapa stack pointer 16 bit?
Stack pointer (SP) dan program counter (PC) digunakan untuk menyimpan lokasi sebelumnya dan alamat lokasi memori adalah 16 bit, jadi stack pointer (SP) juga 16 bit.
3). Apa peran penunjuk tumpukan?
Peran penunjuk tumpukan (SP) adalah untuk menunjukkan bagian atas elemen dalam tumpukan.
4). Tumpukan mana yang digunakan di 8085?
Tumpukan yang digunakan pada 8085 adalah Last In First Out (LIFO).
5). Apakah penunjuk tumpukan sebuah register?
Ya, stack pointer (SP) adalah register alamat yang selalu menunjukkan bagian atas elemen dalam tumpukan.
