Sebuah stack adalah struktur data terbatas, karena hanya sejumlah kecil operasi dilakukan di atasnya. Sifat dari pop dan operasi mendorong juga berarti bahwa elemen stack memiliki tatanan alam. Unsur dikeluarkan dari stack dalam urutan terbalik dengan urutan penambahan mereka:. Oleh karena itu, unsur-unsur yang lebih rendah adalah mereka yang telah di stack terpanjang
Sejarah
Tumpukan pertama kali diusulkan pada tahun 1955, dan kemudian dipatenkan pada tahun 1957, oleh Friedrich L. Bauer Jerman [2] Konsep yang sama dikembangkan secara independen, pada sekitar waktu yang sama, oleh Leonard Charles Australia Hamblin..
Abstrak definisi
Sebuah stack adalah ilmu komputer dasar struktur data dan dapat didefinisikan dalam implementasi, abstrak gratis, cara.
Ini adalah VDM (Wina Pengembangan Metode) deskripsi suatu tumpukan
Fungsi tanda tangan:
init: -> Stack
push: N x Stack -> Stack
top: Stack -> (N U ERROR)
remove: Stack -> Stack
isempty: Stack -> Boolean
(dimana N menunjukkan unsur (bilangan asli dalam kasus ini), dan U menunjukkan mengatur serikat)
Semantik
top(init()) = ERROR
top(push(i,s)) = i
remove(init()) = init()
remove(push(i, s)) = s
isempty(init()) = true
isempty(push(i, s)) = false
Tdk penting operasi
Dalam bahasa komputer modern, stack biasanya diimplementasikan dengan operasi yang lebih dari sekedar "push" dan "pop". Beberapa implementasi memiliki fungsi yang mengembalikan saat ini jumlah item pada stack. Operasi lain pembantu khas atas [4] (juga dikenal sebagai mengintip) dapat mengembalikan elemen atas saat tumpukan tanpa menghapusnya.
[Sunting] Perangkat Lunak tumpukan
[Sunting] Implementasi
Dalam bahasa tingkat yang paling tinggi, setumpuk bisa diimplementasikan baik melalui array atau linked list. Apa mengidentifikasi struktur data sebagai stack dalam kasus baik bukan implementasi tetapi antarmuka: user hanya diperbolehkan untuk pop atau mendorong barang ke array atau linked list, dengan beberapa operasi penolong lainnya. Berikut ini akan menunjukkan kedua implementasi, menggunakan C.
[Sunting] Array
Pelaksanaan array bertujuan untuk menciptakan sebuah array di mana elemen pertama (biasanya di-offset nol) adalah bagian bawah. Artinya, array [0] adalah elemen pertama didorong ke stack dan elemen terakhir muncul off. Program harus melacak ukuran, atau panjang tumpukan. Tumpukan itu sendiri sehingga dapat secara efektif diimplementasikan sebagai struktur dua-elemen di C:
typedef struct {
int size;
int items[STACKSIZE];
} STACK;
Push () operasi digunakan baik untuk menginisialisasi stack, dan untuk menyimpan nilai-nilai untuk itu. Hal ini bertanggung jawab untuk memasukkan (menyalin) nilai ke dalam item ps-> [] array dan untuk incrementing elemen counter (ukuran ps->). Dalam implementasi C yang bertanggung jawab, juga perlu memeriksa apakah array sudah penuh untuk mencegah menyerbu....
Pop () operasi bertanggung jawab untuk menghilangkan nilai dari stack, dan decrementing nilai ukuran ps->. Implementasi C bertanggung jawab juga akan perlu memeriksa bahwa array tidak sudah kosong.
void push(STACK *ps, int x)
{
if (ps->size == STACKSIZE) {
fputs("Error: stack overflow\n", stderr);
abort();
} else
ps->items[ps->size++] = x;
}
int pop(STACK *ps)
{
if (ps->size == 0){
fputs("Error: stack underflow\n", stderr);
abort();
} else
return ps->items[--ps->size];
}
Jika kita menggunakan array dinamis, maka kita dapat mengimplementasikan stack yang dapat tumbuh atau menyusut sebanyak yang dibutuhkan. Ukuran stack hanyalah ukuran dari array dinamis. Sebuah array dinamis adalah implementasi yang sangat efisien tumpukan, karena menambahkan item ke atau menghapus item dari akhir array dinamis diamortisasi O (1) waktu.
[sunting] Linked list
Pelaksanaan linked-list sama sederhana dan mudah. Bahkan, daftar secara tunggal-linked sederhana adalah cukup untuk menerapkan stack - hanya mensyaratkan bahwa kepala node atau elemen dapat dihapus, atau muncul, dan node hanya dapat disisipkan dengan menjadi simpul kepala baru.
Berbeda dengan implementasi array, typedef struktur kita tidak sesuai dengan struktur seluruh tumpukan, tetapi untuk node tunggal:
typedef struct stack {
int data;
struct stack *next;
} STACK;
Seperti sebuah node identik dengan daftar node khas sendiri-sendiri-linked, setidaknya untuk mereka yang diimplementasikan dalam C.
Push () operasi baik menginisialisasi stack kosong, dan menambahkan node baru ke satu non-kosong. Ia bekerja dengan menerima nilai data untuk mendorong ke stack, bersama dengan target setumpuk, menciptakan sebuah node baru dengan mengalokasikan memori untuk itu, dan kemudian dimasukkan ke dalam linked list sebagai kepala baru:
void push(STACK **head, int value)
{
STACK *node = malloc(sizeof(STACK)); /* create a new node */
if (node == NULL){
fputs("Error: no space available for node\n", stderr);
abort();
} else { /* initialize node */
node->data = value;
node->next = empty(*head) ? NULL : *head; /* insert new head if any */
*head = node;
}
}
Sebuah operasi pop menghapus kepala dari linked list, dan memberikan pointer ke kepala ke node kedua sebelumnya. Ia memeriksa apakah daftar kosong sebelum bermunculan dari itu:...
int pop(STACK **head)
{
if (empty(*head)) { /* stack is empty */
fputs("Error: stack underflow\n", stderr);
abort();
} else { /* pop a node */
STACK *top = *head;
int value = top->data;
*head = top->next;
free(top);
return value;
}
}
Tumpukan dan bahasa pemrograman
Beberapa bahasa, seperti LISP dan Python, jangan panggil untuk implementasi stack, karena push dan pop fungsi yang tersedia untuk daftar apapun. Semua bahasa Forth seperti (seperti Adobe PostScript) juga dirancang di sekitar tumpukan bahasa jelas, yang secara langsung dapat dilihat dan dimanipulasi oleh programmer.
C + + 's Standard Template Library menyediakan "stack" kelas templated yang dibatasi hanya push / pop operasi. Jawa perpustakaan berisi kelas Stack yang merupakan spesialisasi dari Vector --- ini bisa dianggap sebagai cacat desain, karena mewarisi get () method dari Vector mengabaikan kendala LIFO dari Stack.
[sunting] struktur data Terkait
Fungsionalitas antrian dan setumpuk dapat dikombinasikan dalam struktur data deque. Secara singkat menaruh, antrian adalah sebuah First In First Out (FIFO) struktur data.
[sunting] tumpukan Hardware
arsitektur dasar dari stack
Sebuah khas stack, penyimpanan data lokal dan informasi panggilan untuk panggilan prosedur tersarang (nested prosedur belum tentu!). Stack ini tumbuh ke bawah dari asal-usulnya. Stack pointer menunjuk ke datum paling atas saat di stack. Sebuah decrements operasi push pointer dan salinan data ke stack, sebuah data operasi pop salinan dari kenaikan stack dan kemudian pointer. Setiap prosedur yang disebut dalam program menyimpan informasi prosedur kembali (dalam kuning) dan data lokal (dalam warna lain) dengan mendorong mereka ke dalam stack. Jenis implementasi stack sangat umum, tetapi rentan terhadap serangan buffer overflow (lihat teks).
Sebuah khas stack adalah daerah memori komputer dengan asal tetap dan ukuran variabel. Awalnya ukuran stack adalah nol. Sebuah stack pointer, biasanya dalam bentuk register perangkat keras, menunjuk ke lokasi yang terakhir dirujuk di stack, ketika tumpukan memiliki ukuran nol, tumpukan poin pointer ke asal dari stack.
Dua kegiatan yang berlaku untuk semua tumpukan adalah:
* Operasi push, di mana sebuah item data ditempatkan di lokasi yang ditunjuk oleh stack pointer, dan alamat dalam stack pointer disesuaikan dengan ukuran dari item data;
* Pop atau tarik operasi: item data di lokasi saat ditunjuk oleh stack pointer dihapus, dan stack pointer disesuaikan dengan ukuran dari item data.
Ada banyak variasi pada prinsip dasar operasi stack. Setiap tumpukan memiliki lokasi tetap dalam memori di mana ia dimulai. Seperti item data ditambahkan ke stack, stack pointer adalah pengungsi untuk menunjukkan sejauh mana saat ini dari stack, yang berkembang jauh dari asal.
Stack pointer dapat menunjukkan asal suatu tumpukan atau kisaran alamat terbatas baik di atas atau di bawah asal (tergantung pada arah di mana tumpukan tumbuh), namun, stack pointer tidak dapat menyeberang asal dari stack. Dengan kata lain, jika asal stack yang di alamat 1000 dan tumpukan tumbuh ke bawah (ke arah alamat 999, 998, dan sebagainya), stack pointer tidak boleh bertambah melampaui 1000 (untuk 1001,, 1002 dll). Jika operasi pop pada stack menyebabkan stack pointer untuk bergerak melewati asal dari stack, setumpuk underflow terjadi. Jika operasi push menyebabkan stack pointer untuk kenaikan atau penurunan melebihi batas maksimum stack sebuah stack overflow terjadi.
Beberapa lingkungan yang sangat bergantung pada tumpukan dapat menyediakan operasi tambahan, misalnya:
* GKG (licate): item teratas adalah muncul, dan kemudian mendorong lagi (dua kali), sehingga salinan tambahan dari item atas mantan sekarang di atas, dengan yang asli di bawahnya.
* Peek: item paling atas diperiksa (atau kembali), tetapi stack pointer tidak berubah, dan ukuran stack tidak berubah (berarti bahwa item tersebut tetap di stack). Ini juga disebut operasi teratas di banyak artikel.
* Swap atau tukar: dua item teratas di stack tempat pertukaran.
* Putar (atau Roll): item n paling atas adalah bergerak di tumpukan dalam mode berputar. Sebagai contoh, jika n = 3,, item 1, 2, dan 3 di stack dipindahkan ke posisi 2, 3, dan 1 di stack, masing-masing. Banyak varian operasi ini adalah mungkin, dengan yang paling umum adalah yang disebut memutar kiri dan kanan berputar.
Tumpukan baik divisualisasikan tumbuh dari bawah ke atas (seperti tumpukan dunia nyata), atau, dengan bagian atas dari stack dalam posisi tetap (lihat gambar catatan [di gambar, bagian atas (28) adalah 'bawah' stack, karena tumpukan 'top' adalah di mana item didorong atau muncul dari]), pemegang koin, Pez dispenser, atau tumbuh dari kiri ke kanan, sehingga "paling atas" menjadi "paling kanan". visualisasi ini mungkin tergantung pada struktur yang sebenarnya dari stack dalam memori. Ini berarti bahwa hak memutar akan memindahkan elemen pertama ke posisi ketiga, yang kedua untuk yang pertama dan yang ketiga untuk yang kedua. Berikut adalah dua visualisasi setara dari proses ini:
pisang
apel=== kanan akan memutar mentimun> ==mentimun apel
pisang
Sebuah stack biasanya diwakili dalam komputer oleh sebuah blok sel memori, dengan "bawah" di lokasi yang tetap, dan stack pointer memegang alamat dari sel saat ini "atas" di stack. Bagian atas dan bawah terminologi digunakan terlepas dari apakah benar-benar tumbuh ke arah tumpukan alamat memori yang lebih rendah atau ke alamat memori yang lebih tinggi.
Mendorong item ke stack stack pointer menyesuaikan dengan ukuran item (baik decrementing atau incrementing, tergantung pada arah di mana tumpukan tumbuh di memori), menunjuk ke sel berikutnya, dan salinan item atas baru untuk tumpukan daerah. Tergantung lagi pada penerapan yang tepat, pada akhir operasi push, stack pointer dapat menunjuk ke lokasi yang tidak terpakai berikutnya dalam stack, atau mungkin menunjuk ke item teratas dalam tumpukan. Jika tumpukan menunjuk ke item paling atas saat ini, stack pointer akan diperbarui sebelum item baru didorong ke dalam stack, jika itu menunjuk ke lokasi yang tersedia berikutnya dalam tumpukan, akan diperbarui setelah item baru didorong ke stack.
Popping tumpukan hanyalah kebalikan dari mendorong. Item paling atas dalam stack dihapus dan stack pointer diperbarui, dalam urutan kebalikan dari yang digunakan dalam operasi push.
[Sunting] Dukungan Hardware
[Sunting] Stack di memori utama
Kebanyakan CPU register yang dapat digunakan sebagai stack pointer. Prosesor keluarga seperti x86, Z80, 6502, dan banyak orang lain telah instruksi khusus yang secara implisit menggunakan (hardware) didedikasikan stack pointer untuk menghemat ruang opcode. Beberapa prosesor, seperti PDP-11 dan 68000, juga memiliki mode pengalamatan khusus untuk pelaksanaan tumpukan, biasanya dengan pointer stack semi-dedicated serta (seperti A7 di 68000). Namun, dalam kebanyakan prosesor, register yang berbeda dapat digunakan sebagai pointer tumpukan tambahan lain yang diperlukan (apakah diperbaharui melalui mode pengalamatan atau via menambah / instruksi sub).
[Sunting] Stack dalam register atau memori khusus
Arsitektur x87 floating point adalah contoh dari satu set register disusun sebagai tumpukan mana akses langsung ke register individu (relatif bagian atas saat ini) juga mungkin. Seperti mesin stack berbasis pada umumnya, memiliki top-of-stack sebagai argumen implisit memungkinkan untuk jejak kode mesin kecil dengan penggunaan yang baik dan bandwidth bus cache kode, tetapi juga mencegah beberapa jenis optimasi yang mungkin pada prosesor mengizinkan random akses ke file mendaftar untuk semua (dua atau tiga) operan. Struktur stack juga membuat implementasi superscalar dengan pengubahan nama (untuk eksekusi spekulatif) agak lebih kompleks untuk melaksanakan, meskipun masih layak, sebagaimana dicontohkan oleh modern x87 implementasi.
Sun SPARC, AMD Am29000, dan Intel I960 merupakan contoh arsitektur menggunakan register windows dalam register-stack sebagai strategi lain untuk menghindari penggunaan memori utama lambat untuk argumen fungsi dan nilai kembali.
Ada juga sejumlah kecil yang mengimplementasikan mikroprosesor setumpuk langsung di hardware dan beberapa mikrokontroler memiliki kedalaman stack-tetap yang tidak langsung dapat diakses. Contohnya adalah mikrokontroler PIC, Cowboys Komputer MuP21, Harris Rtx garis, dan NC4016 Novix. stack mikroprosesor berbasis Banyak digunakan untuk menerapkan Forth bahasa pemrograman di tingkat microcode. Tumpukan juga digunakan sebagai dasar dari sejumlah mainframe dan komputer mini. mesin seperti itu disebut stack mesin, yang paling terkenal sebagai Burroughs B5000.
[Sunting] Aplikasi
Tumpukan yang mana-mana di dunia komputasi.
[Sunting] evaluasi Ekspresi dan sintaks parsing
Kalkulator menggunakan notasi Polandia reverse menggunakan struktur stack untuk menyimpan nilai. Ekspresi dapat diwakili dalam awalan, postfix atau notasi infiks. Konversi dari satu bentuk ekspresi untuk bentuk lain dapat dicapai dengan menggunakan stack. Banyak kompiler menggunakan stack untuk parsing sintaks ekspresi, program dll blok sebelum menerjemahkan ke dalam kode tingkat rendah. Sebagian besar bahasa pemrograman adalah bahasa bebas konteks yang memungkinkan mereka dapat dipecah dengan mesin berbasis stack.
[Sunting] Contoh (umum)
Perhitungan: 1 + 2 * 4 + 3 dapat ditulis seperti ini dalam notasi postfix dengan keuntungan tidak ada aturan didahulukan dan tanda kurung yang dibutuhkan:
1 2 4 * + 3 +
Ekspresi dievaluasi dari kiri ke kanan menggunakan stack:
1. ketika menemukan operan: dorong
2. ketika menemukan operator: pop dua operan, mengevaluasi hasil dan mendorongnya.
Seperti cara berikut (Stack ditampilkan setelah Operasi telah terjadi):
Input Operasi Stack (setelah op)
1 Push operan 1
2 Push operan 2, 1
4 Push operan 4, 2, 1
* Multiply 8, 1
+ Tambah 9
3 Push operan 3, 9
+ Tambah 12
Hasil akhir, 12, terletak di atas tumpukan pada akhir perhitungan.
Contoh di C
#include
int main()
{
int a[100], i;
printf("To pop enter -1\n");
for(i = 0;;)
{
printf("Push ");
scanf("%d", &a[i]);
if(a[i] == -1)
{
if(i == 0)
{
printf("Underflow\n");
}
else
{
printf("pop = %d\n", a[--i]);
}
}
else
{
i++;
}
}
}
[edit] Example (Pascal)
This is an implementation in Pascal, using marked sequential file as data archives.
{
programmer : clx321
file : stack.pas
unit : Pstack.tpu
}
program TestStack;
{this program uses ADT of Stack, I will assume that the unit of ADT of Stack has already existed}
uses
PStack; {ADT of STACK}
{dictionary}
const
mark = '.';
var
data : stack;
f : text;
cc : char;
ccInt, cc1, cc2 : integer;
{functions}
IsOperand (cc : char) : boolean; {JUST Prototype}
{return TRUE if cc is operand}
ChrToInt (cc : char) : integer; {JUST Prototype}
{change char to integer}
Operator (cc1, cc2 : integer) : integer; {JUST Prototype}
{operate two operands}
{algorithms}
begin
assign (f, cc);
reset (f);
read (f, cc); {first elmt}
if (cc = mark) then
begin
writeln ('empty archives !');
end
else
begin
repeat
if (IsOperand (cc)) then
begin
ccInt := ChrToInt (cc);
push (ccInt, data);
end
else
begin
pop (cc1, data);
pop (cc2, data);
push (data, Operator (cc2, cc1));
end;
read (f, cc); {next elmt}
until (cc = mark);
end;
close (f);
end
}
Runtime manajemen memori
Artikel utama: alokasi memori Stack-based dan mesin Stack
Sejumlah bahasa pemrograman yang berorientasi stack, yang berarti mereka menentukan operasi yang paling dasar (menambahkan dua angka, mencetak karakter) sebagai argumen mengambil mereka dari tumpukan, dan menempatkan mengembalikan nilai kembali di stack. Sebagai contoh, PostScript telah kembali tumpukan dan operan stack, dan juga memiliki negara grafis tumpukan dan kamus stack.
Keempat menggunakan dua susunan, satu untuk melewatkan argumen dan satu untuk alamat kembali subrutin. Penggunaan kembali stack sangat biasa, namun agak tidak biasa menggunakan argumen stack untuk bahasa pemrograman terbaca-manusia adalah alasan Forth disebut sebagai bahasa stack-based.
mesin virtual Banyak juga stack-oriented, termasuk mesin p-kode dan Java Virtual Machine.
Hampir semua lingkungan runtime memori komputer menggunakan stack khusus (yang "call stack") untuk menyimpan informasi tentang prosedur / fungsi memanggil dan nesting untuk beralih ke konteks fungsi dipanggil dan mengembalikan ke fungsi pemanggil ketika selesai panggilan. Mereka mengikuti protokol runtime antara pemanggil dan callee untuk menyimpan argumen dan nilai kembali di stack. Tumpukan merupakan cara penting untuk mendukung panggilan fungsi bertelur atau rekursif. Jenis stack yang digunakan secara implisit oleh compiler untuk mendukung pernyataan CALL dan RETURN (atau setara mereka) dan tidak dimanipulasi secara langsung oleh programmer.
Beberapa bahasa pemrograman menggunakan stack untuk menyimpan data yang lokal untuk prosedur. Ruang untuk item data lokal dialokasikan dari stack ketika prosedur dimasukkan, dan deallocated ketika keluar prosedur. Bahasa pemrograman C biasanya diimplementasikan dengan cara ini. Menggunakan stack yang sama untuk kedua panggilan data dan prosedur mempunyai implikasi keamanan yang penting (lihat di bawah), dimana programmer harus menyadari untuk menghindari memperkenalkan bug keamanan serius ke dalam program.
[Sunting] Keamanan
Beberapa lingkungan komputasi menggunakan tumpukan dengan cara yang dapat membuat mereka rentan terhadap pelanggaran keamanan dan serangan. Programmer yang bekerja di lingkungan tersebut harus berhati-hati untuk menghindari perangkap tersebut implementasi.
Sebagai contoh, beberapa bahasa pemrograman menggunakan umum stack untuk menyimpan baik data lokal ke sebuah prosedur yang disebut dan informasi menghubungkan prosedur yang memungkinkan untuk kembali ke pemanggil tersebut. Ini berarti bahwa program tersebut memindahkan data ke dalam dan keluar yang sama stack yang berisi alamat kembali kritis untuk panggilan prosedur. Jika data dipindahkan ke lokasi yang salah di stack, atau item data yang besar tersebut akan dipindahkan ke lokasi stack yang tidak cukup besar untuk berisi itu, mengembalikan informasi untuk panggilan prosedur dapat rusak, menyebabkan program gagal.
pihak berbahaya dapat mencoba melakukan serangan stack smashing yang mengambil keuntungan dari jenis implementasi dengan memberikan masukan besar data untuk program yang tidak mengecek panjang input. Program tersebut dapat menyalin data secara keseluruhan ke lokasi di stack, dan dengan demikian ia dapat mengubah kembali alamat untuk prosedur yang telah disebut itu. Seorang penyerang dapat melakukan percobaan untuk menemukan tipe spesifik data yang dapat diberikan kepada seperti program seperti bahwa alamat kembali prosedur saat ini adalah ulang untuk menunjuk ke suatu daerah dalam tumpukan itu sendiri (dan dalam data yang disediakan oleh si penyerang), yang pada gilirannya berisi instruksi yang melakukan operasi yang tidak sah.
Jenis serangan adalah variasi serangan buffer overflow dan merupakan sumber yang sangat sering pelanggaran keamanan dalam perangkat lunak, terutama karena beberapa bahasa pemrograman yang paling populer (seperti C) menggunakan fitur yang baik stack untuk panggilan data dan prosedur, dan tidak memverifikasi panjang item data. Sering pemrogram tidak menulis kode untuk memverifikasi ukuran item data, baik, dan ketika item data terlalu besar atau terlalu kecil akan disalin ke stack sebuah pelanggaran keamanan mungkin terjadi.
Tidak ada komentar:
Posting Komentar