Tumpukan hanyalah struktur data linier di mana penyisipan dan penghapusan berlaku hanya pada satu hujung. Operasi penyisipan mempunyai nama khas yang dikenali sebagai PUSH dan operasi penghapusan juga mempunyai nama khas yang dikenali sebagai POP. PUSH dan POP adalah dua operasi asas yang dapat dilakukan hanya dalam timbunan tertentu. Ini adalah sekumpulan lokasi memori dan lokasi memori berkaitan dengan memori baca atau memori tulis. Ini digunakan untuk menyimpan maklumat binari semasa pelaksanaan program, ketika kita menjalankan program apa pun maka kandungan program tersebut akan disimpan dalam timbunan. Ia mengikuti Terakhir Dalam Keluar Pertama (LIFO) dan digunakan hanya untuk menyimpan dan mengambil data tetapi tidak digunakan untuk menyimpan data. Penjelasan ringkas mengenai stack / stack pointer dibincangkan di bawah.
Apa itu Stack / Stack Pointer?
Definisi: Tumpukan adalah alat penyimpanan, digunakan untuk menyimpan maklumat 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 penyisip terakhir, jadi elemen yang dimasukkan terakhir dikeluarkan terlebih dahulu. Ini adalah unit memori dalam daftar alamat yang disebut stack pointer (SP). Penunjuk tumpukan selalu menunjukkan elemen teratas dalam timbunan yang bermaksud lokasi mana data harus dimasukkan.
Jenis Tumpukan
Terdapat dua jenis tumpukan iaitu tumpukan daftar dan timbunan memori.
Daftar Tumpukan
Tumpukan daftar juga merupakan perangkat memori yang terdapat di unit memori, tetapi hanya menangani sebilangan kecil data. Kedalaman timbunan selalu terhad dalam timbunan daftar kerana ukuran timbunan daftar sangat kecil jika dibandingkan dengan memori.
Operasi Tolak dalam Daftar Tumpukan
Langkah 1: Penunjuk timbunan meningkat sebanyak 1.
SP ← SP + 1
Langkah 2: Masukkan data ke dalam timbunan.
1000 [SP] ← CT
Di mana DR adalah Daftar Data
Langkah 3: Periksa sama ada timbunan penuh atau tidak
jika (sp = 0) maka (penuh ← 1)
Langkah 4: Tandakan tidak kosong
kosong ← 0
Operasi Pop dalam Daftar Tumpukan
Langkah 1: Baca data dari timbunan.
DR ← M [SP]
Langkah 2: Titik timbunan penurunan.
SP ← SP-1
Langkah 3: Periksa sama ada timbunan itu kosong atau tidak
jika sp = 0 maka kosongkan ← 1
Susunan susunan timbunan daftar 64-bit ditunjukkan dalam gambar di bawah.
Daftar Pertubuhan Tumpukan
Tumpukan Memori
Dalam timbunan memori, kedalaman timbunan adalah fleksibel. Ini menempati sejumlah besar data memori, sedangkan di tumpukan daftar hanya sejumlah kata memori yang akan disimpan.
Operasi Tolak di Storan Memori
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 daftar, unit memori menyimpan sejumlah besar data. Angka timbunan memori ditunjukkan dalam gambar di bawah.
Tumpukan Memori
Jumlah unit memori terbahagi kepada tiga bahagian, unit memori pertama mempunyai program (tidak lain kecuali arahan), bahagian kedua adalah data (operan) dan bahagian ketiga adalah timbunan. Arahan program selalu disimpan di kaunter program (PC), daftar data dikenal pasti oleh daftar alamat (AR). Alamat 3000 hingga 4001 yang digunakan untuk timbunan dan item atau elemen pertama disimpan pada 4001.
Stack / Stack Pointer pada 8085 Mikropemproses
Paparan pengaturcara 8085 mikropemproses mengandungi daftar tujuan am dan daftar tujuan khas . Daftar tujuan umum adalah A, B, C, D, E, H, L, dan daftar tujuan khas adalah SP (Stack Pointer) dan PC (Program Counter). Paparan pengaturcara 8085 mikropemproses ditunjukkan dalam gambar di bawah.
Paparan Pengaturcara 8085
Penunjuk tumpukan adalah daftar 16-bit yang mengandungi alamat memori, misalkan kandungan penumpuk tumpukan (SP) adalah FC78H, maka mikropemproses 8085 menafsirkannya. Lokasi memori mempunyai maklumat berguna dari FC78H hingga FFFH dan dari FC77H hingga 0000H lokasi memori tidak mempunyai maklumat berguna. Tafsiran penunjuk timbunan ditunjukkan dalam rajah di bawah.
Tafsiran Stack Pointer
Operasi Asas Stack Pointer
Terdapat dua operasi timbunan iaitu operasi PUSH dan operasi POP.
Operasi PUSH
PUSH bermaksud menolak atau memasukkan elemen ke dalam timbunan. Operasi PUSH selalu menambah penunjuk timbunan dan operasi POP selalu menurunkan penunjuk timbunan. Sekiranya berlaku operasi tolak, kita harus memeriksa apakah ada ruang kosong yang ada atau tidak. Sekiranya ruang kosong tersedia, kita dapat pergi ke operasi tekan, jika ruang kosong tidak tersedia maka pesan ralat terjadi yang melimpah. Limpahan harus diperiksa sekiranya berlaku operasi tolak. Operasi asas push dan pop ditunjukkan pada gambar di bawah.
Operasi Asas PUSH dan POP
Rajah (a) ialah timbunan. Sekiranya anda ingin mendorong elemen yang memasukkan elemen ke dalam timbunan, anda harus menekan (s, a), di mana 's' tidak lain hanyalah timbunan. Di timbunan, kita meletakkan elemen ‘a’ dan operasi ini ditunjukkan pada gambar (b). Lihat gambar (3), anggap tumpukan mengandungi tiga elemen a, b, c, dan timbunan diisi dengan elemen.
Sekiranya anda ingin memasukkan elemen keempat-‘d’ menggunakan tekan (s, d), tetapi tidak ada ruang yang tersedia untuk memasukkan elemen tersebut maka ini menunjukkan bahawa timbunan itu meluap. Terminologi limpahan digunakan apabila timbunan penuh dan algoritma operasi tolak ditunjukkan di bawah.
tolak (tumpukan [], atas, tumpukan maksimum, item)
jika (atas == maxstack-1)
{
cetak 'limpahan'
}
yang lain
{
atas = atas + 1
susun [atas] = item
}
akhir
Operasi POP
POP bermaksud menghapus elemen di bahagian atas timbunan. Dalam kes operasi pop, kita harus memeriksa sama ada timbunan pada mulanya kosong atau tidak. Sekiranya timbunan pada awalnya kosong maka berlaku keadaan aliran masuk. Katakan timbunan kosong masih anda mahu memasukkan elemen dalam timbunan tetapi tidak ada unsur dalam timbunan maka ia mengarah ke timbunan aliran masuk.
Aliran bawah harus diperiksa sekiranya terdapat operasi pop. Dalam operasi pop apa pun elemen teratas yang ada dalam tumpukan yang seharusnya muncul atau dihapus, jadi tidak perlu disebutkan elemen mana yang akan muncul, secara lalai elemen paling atas akan muncul. Algoritma operasi pop ditunjukkan di bawah.
pop (tumpukan [], bahagian atas, item)
jika (atas == - 1)
{
cetak 'underflow'
}
yang lain
{
item = timbunan [atas]
atas = teratas-1
}
Contohnya
Unsur-unsur dimasukkan dalam urutan sebagai A, B, C, D, E, ia mewakili timbunan lima elemen. Pada rajah (a), kita ingin menolak elemen 'A' pada timbunan maka bahagian atas menjadi sifar (atas = 0), sama dengan bahagian atas = 1 ketika elemen 'B' didorong, atas = 2 ketika elemen 'C' didorong, atas = 3 ketika elemen 'D' didorong, dan atas = 4 apabila elemen 'E' didorong.
Oleh itu, apa sahaja elemen yang telah saya ambil diletakkan di dalam timbunan, kini timbunannya sudah penuh. Sekiranya anda ingin mendorong elemen lain tidak ada tempat di timbunan, jadi ini menunjukkan limpahan. Sekarang timbunan sudah penuh jika anda mahu memasukkan elemen ‘E’ harus dipadamkan terlebih dahulu. Operasi tolak ditunjukkan dalam gambar di bawah.
Operasi Tolak
Kita harus menggunakan operasi pop untuk menghapus elemen dalam timbunan. Oleh itu, sebutkan pop () jangan menulis argumen dalam pop kerana secara lalai ia menghapus elemen teratas. Elemen ‘E’ pertama dihapuskan elemen ‘D’ seterusnya… .. ’A’. Apabila elemen teratas dihapus maka nilai teratas akan berkurang. Apabila teratas = -1 timbunan menunjukkan aliran masuk. Operasi pop ditunjukkan dalam gambar di bawah.
Operasi POP
Jadi ini adalah penjelasan bagaimana elemen dimasukkan dan dihapus dalam timbunan dengan menggunakan operasi tekan dan pop.
Permohonan
Aplikasi penunjuk timbunan / timbunan adalah
- Pembalikan tali
- Kurungan seimbang
- UNDO / FINGER
- Tumpukan sistem untuk rekod pengaktifan
- Infix, awalan, postfix, ekspresi
Soalan Lazim
1). Apakah penunjuk timbunan di lengan?
Daftar penunjuk tumpukan (R13) digunakan sebagai penunjuk kepada timbunan aktif di ARM.
2). Mengapa penunjuk tumpukan adalah 16 bit?
Penunjuk tumpukan (SP) dan penghitung program (PC) yang digunakan untuk menyimpan lokasi sebelumnya dan alamat lokasi memori adalah 16 bit, jadi penunjuk tumpukan (SP) juga sebesar 16 bit.
3). Apakah peranan penunjuk timbunan?
Peranan penunjuk tumpukan (SP) adalah untuk menunjukkan bahagian atas elemen dalam timbunan.
4). Tumpukan mana yang digunakan pada tahun 8085?
Tumpukan yang digunakan pada tahun 8085 adalah Last In First Out (LIFO).
5). Adakah penunjuk tumpukan adalah daftar?
Ya, penunjuk tumpukan (SP) adalah daftar alamat yang selalu menunjukkan bahagian atas elemen dalam timbunan.
