Apa itu Stack Pointer: Jenis & Aplikasinya
Stack 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, konten program itu akan disimpan di stack.
Ini mengikuti Last In First Out (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 atau Stack Pointer 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 stack (tumpukan) yaitu stack register dan stack memori.
Register Stack
Register stack 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 Push di Register Stack
Step1: Stack Pointer bertambah 1.
SP←SP+1
step2: Masukkan data ke dalam stack (tumpukan).
M [SP] ← DR
Dimana DR adalah Data Register
Step3: Periksa apakah tumpukan sudah penuh atau tidak
jika (sp = 0) maka (full← 1)
Step4: Tandai tidak kosong
empty ← 0
Operasi Pop di Register Stack
Step1: Baca data dari stack (tumpukan).
DR ← M [SP]
Step2: Penurunan stack point.
SP ← SP-1
Step3: Periksa apakah tumpukan kosong atau tidak
jika sp = 0 maka empty ← 1
Kumpulan tumpukan dari tumpukan register 64-bit ditunjukkan pada gambar di bawah ini.
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 Push (dorong) di Memory Stack
Langkah 1: SP ← SP-1
Langkah2: M [SP] ← DR
Operasi Pop di Memory Stack
Langkah 1: DR ← M [SP]
Langkah2: SP ← SP-1
Bandingkan dengan unit register, unit memori menyimpan data dalam jumlah besar. Gambar tumpukan memori ditunjukkan pada gambar di bawah ini.
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 (tumpukan). Instruksi program selalu disimpan di program counter (PC), register data diidentifikasi oleh address register (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.
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.
Operasi Dasar Stack / Stack Pointer
Ada dua operasi stack yaitu: operasi PUSH dan operasi POP.
Operasi PUSH
PUSH berarti mendorong atau memasukkan elemen ke dalam tumpukan (stack). Operasi PUSH selalu menambah penunjuk tumpukan dan operasi POP selalu mengurangi stack pointer. 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.
Gambar (a) adalah stack (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 atau tumpukan berisi tiga elemen a, b, c, dan stack diisi dengan satu elemen.
Jika Anda ingin memasukkan elemen keempat-'d 'menggunakan push (s, d), tetapi tidak ada ruang yang tersedia untuk memasukkan elemen tersebut, ini menunjukkan bahwa tumpukan melimpah. Terminologi overflow digunakan saat tumpukan penuh dan algoritme operasi dorong ditampilkan di bawah.
if(top==maxstack-1)
{
print “overflow”
}
else
{
top=top+1
stack[top]=item
}
end
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.
if(top==-1)
{
print “underflow”
}
else
{
item=stack[top]
top=top-1
}
Contoh
Elemen-elemen 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 meletuskan elemen 'E' elemen harus di hapus terlebih dahulu. Operasi dorong ditunjukkan pada gambar di bawah ini.
Kami harus menggunakan operasi pop untuk menghapus elemen dalam tumpukan. Jadi sebutkan saja pop () jangan menulis 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.
Jadi begini penjelasan bagaimana elemen disisipkan dan dihapus di stack dengan menggunakan operasi push and pop.
Aplikasi
Penggunaan stack / stack pointer adalah
- Pembalikan string
- Tanda kurung yang seimbang
- UNDO / DEDO
- Sistem stack untuk catatan aktivasi
- Infix, prefix, postfix, ekspresi
Pertanyaan
1). Apa stack pointer di ARM?
Stack register pointer (R13) digunakan sebagai penunjuk ke tumpukan aktif di ARM.
2). Mengapa stack pointer 16 bit?
Stack pointer (SP) dan program counter (PC) yang digunakan untuk menyimpan lokasi sebelumnya dan alamat lokasi memori adalah 16 bit, sehingga stack pointer (SP) juga 16 bit.
3). Apa peran penunjuk tumpukan?
Peran stack pointer (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.
Dalam artikel ini apa itu stack / stack pointer (SP), operasi push, dan operasi pop dengan sebuah contoh, register stack dan memory stack dengan diagram, stack, dan penunjuk stack di 8085 dan aplikasi dibahas.