Stack hanya mempunyai satu hujung yang terbuka untuk menolak dan memunculkan unsur-unsur data di lain-lain Barisan yang kedua-duanya berakhir terbuka untuk enqueuing dan dequeuing unsur-unsur data.
Tumpukan dan barisan adalah struktur data yang digunakan untuk menyimpan unsur data dan sebenarnya berdasarkan pada sesetengah dunia yang setara. Sebagai contoh, timbunan adalah timbunan CD di mana anda boleh mengambil dan memasukkan CD melalui bahagian atas timbunan CD. Begitu juga, Baris adalah barisan untuk tiket Theatre di mana orang yang berdiri di tempat pertama, iaitu, barisan depan akan dihidangkan terlebih dahulu dan orang baru yang tiba akan muncul di belakang barisan (barisan belakang barisan belakang).
Carta Perbandingan
| Asas untuk perbandingan | Timbunan | Beratur |
|---|---|---|
| Prinsip kerja | LIFO (Last in First out) | FIFO (Pertama di Pertama keluar) |
| Struktur | Tamat sama digunakan untuk memasukkan dan memadam elemen. | Satu hujung digunakan untuk penyisipan, iaitu hujung belakang dan hujung yang lain digunakan untuk penghapusan elemen, iaitu hujung depan. |
| Bilangan petunjuk yang digunakan | Satu | Dua (Dalam kes giliran mudah) |
| Operasi dilakukan | Tolak dan pop | Enqueue dan dequeue |
| Pemeriksaan keadaan kosong | Atas == -1 | Depan == -1 || Hadapan == Belakang + 1 |
| Pemeriksaan keadaan penuh | Atas == Maksimum - 1 | Belakang == Max - 1 |
| Variasi | Ia tidak mempunyai variasi. | Ia mempunyai variasi seperti giliran pekeliling, giliran keutamaan, giliran berganda. |
| Pelaksanaan | Lebih mudah | Kompleks yang agak kompleks |
Definisi Stack
A Stack adalah struktur data linear bukan primitif. Ia adalah senarai yang diperintahkan di mana item baru ditambah dan unsur yang sedia ada dipadamkan dari hanya satu hujung, dipanggil sebagai bahagian atas timbunan (TOS). Oleh kerana semua penghapusan dan pemasukan dalam timbunan dilakukan dari atas timbunan, elemen terakhir yang ditambah akan menjadi yang pertama untuk dikeluarkan dari timbunan. Itulah sebabnya mengapa timbunan dipanggil senarai jenis Last-in-First-out (LIFO).
Perhatikan bahawa elemen yang sering diakses dalam timbunan adalah elemen paling atas, sedangkan elemen yang ada sekarang berada di bahagian bawah timbunan.
Contoh
Ada di antara kamu yang boleh makan biskut (atau Poppins). Jika anda mengandaikan, hanya satu sampul penutup yang koyak, dan biskut diambil satu persatu. Ini adalah apa yang dipanggil pop, dan begitu juga, jika anda ingin mengekalkan beberapa biskut untuk beberapa waktu kemudian, anda akan meletakkannya kembali ke dalam pek melalui hujung yang sama koyak dipanggil menolak.
Takrifan Beratur
Baris adalah struktur data linear yang datang dalam kategori jenis bukan primitif. Ia adalah koleksi jenis elemen yang serupa. Penambahan unsur-unsur baru berlaku pada satu hujung yang dipanggil hujung belakang. Begitu juga, pemadaman unsur-unsur yang sedia ada berlaku di hujung yang dipanggil Front-end, dan ia secara logiknya adalah jenis pertama dalam senarai pertama (FIFO).
Contoh
Dalam kehidupan seharian kita, kita dapat melihat banyak situasi di mana kita perlu menunggu untuk perkhidmatan yang diinginkan, di sana kita perlu masuk ke barisan menunggu untuk giliran kami untuk diservis. Antrian menunggu ini boleh dianggap sebagai baris gilir.
Perbezaan Utama Antara Stack dan Queue
- Tumpukan mengikut mekanisme LIFO di sebelah yang lain. Giliran mengikut mekanisme FIFO untuk menambah dan mengeluarkan elemen.
- Dalam timbunan, hujung yang sama digunakan untuk memasukkan dan memadam unsur-unsur. Sebaliknya, dua hujung yang berbeza digunakan dalam barisan untuk memasukkan dan memadam unsur-unsur.
- Oleh sebab Stack hanya mempunyai satu buka hujung yang merupakan sebab untuk menggunakan hanya satu penunjuk untuk merujuk kepada bahagian atas timbunan. Tetapi giliran menggunakan dua petunjuk untuk merujuk depan dan belakang barisan.
- Stack menjalankan dua operasi yang dikenali sebagai push and pop sementara dalam Queue yang dikenali sebagai enqueue dan dequeue.
- Pelaksanaan stack adalah lebih mudah sedangkan pelaksanaan Queue adalah rumit.
- Giliran mempunyai variasi seperti giliran pekeliling, baris gilir keutamaan, baris gilir berulang ganda, dan sebagainya. Sebaliknya, timbunan tidak mempunyai variasi.
Pelaksanaan Stack
Tumpukan itu boleh digunakan dalam dua cara:
- Pelaksanaan statik menggunakan array untuk membuat stack. Pelaksanaan statik adalah teknik yang tidak mudah tetapi bukan cara penciptaan yang fleksibel, karena deklarasi ukuran tumpukan harus dilakukan selama rancangan program, setelah itu ukurannya tidak dapat diubah. Di samping itu, pelaksanaan statik tidak begitu berkesan terhadap penggunaan memori. Oleh kerana array (untuk melaksanakan tindanan) diisytiharkan sebelum permulaan operasi (pada masa reka bentuk program). Sekarang jika bilangan elemen yang hendak disusun sangat kurang dalam timbunan memori yang diperuntukkan secara statistik akan dibazirkan. Sebaliknya, jika terdapat lebih banyak unsur yang akan disimpan dalam timbunan maka, kita tidak dapat mengubah saiz array untuk meningkatkan kapasitinya, supaya ia dapat menampung elemen-elemen baru.
- Pelaksanaan dinamik juga dipanggil perwakilan senarai hubungan dan menggunakan petunjuk untuk melaksanakan jenis struktur data.
Pelaksanaan Beratur
Beratur boleh dilaksanakan dalam dua cara:
- Pelaksanaan statik : Sekiranya baris gilir dilaksanakan dengan menggunakan tatasusunan, bilangan sebenar unsur yang ingin kita simpan dalam baris gilir mesti dipastikan terlebih dahulu, kerana saiz array perlu diisytiharkan pada masa reka bentuk atau sebelum proses bermula. Dalam kes ini, permulaan array akan menjadi barisan antrian, dan lokasi terakhir array akan bertindak sebagai barisan belakang. Hubungan berikut memberikan keseluruhan elemen wujud dalam barisan ketika dilaksanakan menggunakan array:
depan - belakang + 1
Jika "belakang <depan" maka tidak akan ada unsur dalam barisan atau barisan akan sentiasa kosong. - Pelaksanaan dinamik : Melaksanakan beratur menggunakan petunjuk, kelemahan utama adalah bahawa nod dalam perwakilan yang dipautkan menggunakan lebih banyak ruang ingatan berbanding elemen yang sepadan dalam perwakilan array. Oleh kerana terdapat sekurang-kurangnya dua bidang di setiap node satu untuk medan data dan lain-lain untuk menyimpan alamat node seterusnya sedangkan dalam perwakilan yang dipautkan hanya bidang data yang ada. Kebaikan menggunakan perwakilan yang dikaitkan menjadi jelas apabila diperlukan untuk menyisipkan atau memadamkan unsur di tengah-tengah sekumpulan unsur-unsur lain.
Operasi pada Stack
Operasi asas yang boleh dikendalikan pada timbunan adalah seperti berikut:
- PUSH : apabila elemen baru ditambahkan ke bahagian atas timbunan dikenali sebagai operasi PUSH. Menolak elemen dalam timbunan menyuruh menambah unsur, kerana elemen baru akan dimasukkan di bahagian atas. Selepas setiap operasi tolak, bahagian atas ditambah satu. Jika array penuh, dan tiada elemen baru boleh ditambah, ia dipanggil keadaan STACK-FULL atau STACK OVERFLOW. PUSH OPERATION - fungsi dalam C:
Memandangkan timbunan diisytiharkan sebagaiint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Apabila elemen dipadamkan dari bahagian atas timbunan ia dikenali sebagai operasi POP. Tumpukan dikurangkan oleh satu, selepas setiap operasi pop. Jika tiada elemen yang tersisa di timbunan dan pop dilakukan, maka ini akan menyebabkan keadaan STACK UNDERFLOW yang bermaksud timbunan anda Kosong. OPERASI POP - berfungsi dalam C:
Memandangkan timbunan diisytiharkan sebagaiint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Operasi pada Baris
Operasi asas yang boleh dilakukan pada baris gilir adalah:
- Enqueue : Untuk menyisipkan elemen dalam giliran. Mematuhi fungsi operasi dalam C:
Baris diisytiharkan sebagaiint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Untuk memadam elemen dari giliran. Memulakan fungsi operasi dalam C:
Baris diisytiharkan sebagaiint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Aplikasi Stack
- Parsing dalam pengkompil.
- Mesin maya jawa.
- Buat asal dalam pemproses perkataan.
- Butang belakang dalam pelayar web.
- Bahasa pasca untuk pencetak.
- Melaksanakan fungsi panggilan dalam pengkompil.
Permohonan Beratur
- Buffer data
- Pemindahan data asynchronous (fail IO, paip, soket).
- Memenuhi permintaan pada sumber yang dikongsi (pencetak, pemproses).
- Analisis lalu lintas.
- Tentukan jumlah juruwang yang ada di sebuah pasar raya.
Kesimpulannya
Stack dan Queue adalah struktur data linier berbeza dalam cara tertentu seperti mekanisme kerja, struktur, pelaksanaan, variasi tetapi kedua-duanya digunakan untuk menyimpan unsur-unsur dalam senarai dan menjalankan operasi dalam senarai seperti penambahan dan penghapusan unsur-unsur. Walaupun terdapat beberapa batasan beratur yang mudah ditarik balik dengan menggunakan jenis barisan lain.
