Apa perbedaan antara Array dan Stack?

Menurut Wikipedia, tumpukan :

adalah jenis data abstrak terakhir, pertama keluar (LIFO) dan struktur data linier.

Sementara sebuah array :

adalah struktur data yang terdiri dari kumpulan elemen (nilai atau variabel), masing-masing diidentifikasi oleh setidaknya satu indeks atau kunci array.

Sejauh yang saya mengerti, mereka cukup mirip. Jadi, apa perbedaan utama? Jika mereka tidak sama, apa yang bisa dilakukan oleh array yang stack tidak bisa dan sebaliknya?

Nah, Anda tentu dapat mengimplementasikan stack dengan array. Perbedaannya terletak pada akses. Dalam sebuah array, Anda memiliki daftar elemen dan Anda bisa mengaksesnya kapan saja. (Pikirkan sekelompok balok kayu yang semuanya diletakkan berjajar.)

Tetapi dalam tumpukan, tidak ada operasi akses acak; hanya ada Push, Peekdan Pop, yang semuanya berurusan secara eksklusif dengan elemen di bagian atas tumpukan. (Pikirkan balok kayu yang ditumpuk secara vertikal sekarang. Anda tidak dapat menyentuh apa pun di bawah puncak menara atau itu akan jatuh.)

Dalam tumpukan murni, satu-satunya operasi yang diijinkan adalah Push, Pop, dan Peektetapi dalam hal praktis, itu tidak sepenuhnya benar. Atau lebih tepatnya, Peekoperasi sering memungkinkan Anda untuk melihat posisi apa pun di tumpukan, tetapi yang menarik adalah bahwa itu relatif terhadap salah satu ujung tumpukan.

Jadi, seperti yang orang lain katakan, array adalah akses acak dan semuanya dirujuk ke awal array .

Dalam tumpukan, Anda hanya dapat menambah / menghapus di akhir kerja tumpukan, tetapi Anda masih memiliki akses acak dibaca tetapi itu dirujuk ke ujung yang berfungsi . Itulah perbedaan mendasar.

Misalnya, ketika Anda melewatkan parameter pada tumpukan ke suatu fungsi, callee tidak harus mematikan parameter untuk melihatnya. Itu hanya mendorong variabel lokal pada stack dan merujuk semua variabel dan parameter lokal berdasarkan offset dari pointer stack. Jika Anda hanya menggunakan array, lalu bagaimana callee tahu di mana mencari parameternya? Ketika callee selesai, ia memunculkan variabel lokalnya, mendorong nilai kembali, mengembalikan kontrol ke pemanggil, dan penelepon mengeluarkan nilai kembali (jika ada), dan kemudian mengeluarkan parameter dari tumpukan. Keindahannya adalah ia bekerja tidak peduli seberapa jauh Anda bersarang ke pemanggilan fungsi (dengan asumsi Anda tidak kehabisan ruang stack).

Itu satu penggunaan / implementasi tertentu, tetapi menggambarkan perbedaan: array selalu direferensikan dari awal tetapi tumpukan selalu direferensikan dari beberapa posisi ujung yang bekerja.

Salah satu kemungkinan implementasi stack adalah array plus indeks untuk mengingat di mana akhir pekerjaan.

Saya pikir kebingungan terbesar yang terjadi di sini adalah implementasi versus struktur data dasar.

Dalam sebagian besar (bahasa yang lebih mendasar), sebuah array mewakili kumpulan elemen dengan panjang tetap yang dapat Anda akses pada waktu tertentu. Fakta bahwa Anda memiliki banyak elemen seperti ini tidak memberi tahu Anda tentang bagaimana seharusnya digunakan (dan terus terang komputer tidak akan tahu / peduli bagaimana Anda menggunakannya, selama Anda tidak melanggar penggunaan).

Tumpukan adalah abstraksi yang digunakan untuk mewakili data yang harus ditangani dengan cara tertentu. Ini adalah konsep abstrak karena hanya mengatakan bahwa ia harus memiliki beberapa subrutin / metode / fungsi yang dapat menambah ke atas atau menghapus dari atas, sementara data di bawah atas tidak disentuh. Murni pilihan Anda untuk menggunakan array dengan cara ini.

Anda dapat membuat tumpukan dari berbagai jenis struktur data: array (dengan ukuran maksimal), array dinamis (dapat tumbuh ketika kehabisan ruang) atau daftar yang ditautkan. Secara pribadi saya merasa bahwa daftar tertaut mewakili pembatasan tumpukan yang terbaik karena Anda harus berusaha sedikit untuk melihat hal-hal di luar elemen pertama dan sangat mudah untuk menambahkan ke depan dan menghapus dari depan.

Jadi Anda bisa menggunakan array untuk membuat stack, tetapi mereka tidak setara

Tanggung jawab mereka berbeda:

• Stack harus dapat memunculkan elemen ke stack dan mendorong elemen dari stack, karenanya mengapa ia memiliki metode Pop()danPush()

• Tanggung jawab Array adalah untuk mendapatkan / mengatur elemen pada indeks yang ditentukan

Anda dapat mengambil item dari indeks apa pun dari array A \.

Dengan tumpukan, Anda dapat mengambil item di tengah tumpukan A, dengan menggunakan tumpukan lain: B.

Anda terus mengeluarkan item teratas dari A dan memasukkannya ke B sampai Anda berada di item yang diinginkan dari A, lalu Anda meletakkan item dari B kembali di atas tumpukan A.

Jadi, untuk data yang membutuhkan kemampuan untuk mengambil indeks arbitrer, tumpukan lebih sulit untuk dikerjakan.

Dalam situasi di mana Anda ingin perilaku "last in, first out", tumpukan akan memberi Anda lebih sedikit overhead daripada array.

Saya tidak akan mengatakan bahwa mereka "sangat mirip."

Array digunakan untuk menampung hal-hal yang nantinya akan diakses secara berurutan atau melalui indeks. Struktur data tidak menyiratkan semacam metode akses (FIFO, LIFO, FILO, dll ...) tetapi dapat digunakan seperti itu jika Anda inginkan.

Tumpukan adalah cara melacak hal-hal yang dihasilkan. Metode akses tersirat / diperlukan tergantung pada jenis tumpukan yang dibuat. Frame stack akan menjadi contoh LIFO. Penafian - Saya mungkin mencampur taksonomi struktur data saya di sini dan setumpuk mungkin hanya mengizinkan LIFO. Itu akan menjadi jenis antrian yang berbeda.

Jadi saya bisa menggunakan array sebagai stack (walaupun saya tidak mau) tetapi saya tidak bisa menggunakan stack sebagai array (kecuali saya bekerja sangat keras untuk itu).

Data dalam sebuah array dapat diakses oleh kunci atau indeks. Data dalam tumpukan dapat diakses saat dikeluarkan dari bagian atas tumpukan. Ini berarti bahwa mengakses data dari sebuah array mudah jika Anda mengetahui indeksnya. Mengakses data dari tumpukan berarti Anda harus terus mengeluarkan elemen sampai Anda menemukan elemen yang Anda cari, yang berarti akses data bisa lebih lama.

Array adalah dari perspektif programmer, tetap di tempat dan ukuran, Anda tahu di mana Anda berada di dalamnya dan di mana semuanya berada. Anda memiliki akses ke semua itu.

Dengan tumpukan, Anda duduk di salah satu ujungnya tetapi tidak tahu ukurannya atau seberapa jauh Anda bisa pergi dengan aman. Akses Anda ke itu terbatas pada jumlah yang telah Anda alokasikan, Anda bahkan sering tidak tahu jika ketika mengalokasikan jumlah yang Anda inginkan jika Anda hanya menabrak tumpukan atau ruang program. Pandangan Anda tentang tumpukan adalah array kecil yang telah Anda alokasikan sendiri, ukuran yang Anda inginkan, Anda memiliki kendali atas dan dapat melihatnya. Porsi Anda tidak berbeda dengan array. Perbedaannya terletak pada array Anda ditempelkan ke salah satu ujung array lain demi argumen dan terminologi, yang Anda tidak memiliki visibilitas, tidak tahu seberapa besar atau kecil, dan Anda tidak bisa menyentuhnya tanpa kemungkinan menyebabkan kerusakan. Array, kecuali global, sering diimplementasikan pada stack, jadi array dan stack berbagi ruang yang sama selama durasi fungsi itu.

Jika Anda ingin masuk ke sisi perangkat keras, maka itu adalah prosesor tertentu saja, tetapi umumnya array didasarkan dari titik awal / alamat yang diketahui, ukurannya diketahui oleh kompiler / pemrogram, dan alamat dihitung ke dalamnya, kadang-kadang menggunakan pengalamatan register offset (memuat nilai dari alamat yang ditentukan oleh nilai register dasar ini ditambah nilai register offset ini, juga ketika dikompilasikan itu bisa berupa offset langsung yang tidak harus berbasis register, tergantung pada prosesor tentunya) yang dalam perakitan sangat banyak menyerupai mengakses array dalam kode tingkat tinggi. Demikian juga dengan stack, jika tersedia, Anda dapat menggunakan register atau pengalamatan offset langsung, seringkali meskipun menggunakan register khusus, baik pointer stack itu sendiri, atau register yang dipesan oleh kompiler / pemrogram yang akan digunakan untuk mengakses frame stack untuk itu. fungsi. Dan untuk beberapa prosesor, fungsi akses stack khusus digunakan dan / atau diperlukan untuk mengakses stack. Anda memiliki petunjuk push dan pop tetapi itu tidak digunakan sesering yang Anda pikirkan dan tidak benar-benar berlaku untuk pertanyaan ini. Untuk beberapa prosesor, push dan pop adalah alias untuk instruksi yang dapat digunakan dengan register apa pun, di mana saja, bukan hanya stack pointer di stack, lebih lanjut menghilangkan push dan pop agar tidak terkait dengan pertanyaan ini.