Perbedaan Antara Stack dan Antrian

• 2019

Stack dan Queue keduanya adalah struktur data non-primitif. Perbedaan utama antara stack dan antrian adalah bahwa stack menggunakan metode LIFO (last in first out) untuk mengakses dan menambahkan elemen data sedangkan Antrian menggunakan metode FIFO (First in first out) untuk mengakses dan menambahkan elemen data.

Stack hanya memiliki satu ujung terbuka untuk mendorong dan memunculkan elemen data di sisi lain. Antrian memiliki kedua ujung terbuka untuk enqueuing dan dequeuing elemen data.

Stack dan queue adalah struktur data yang digunakan untuk menyimpan elemen data dan sebenarnya didasarkan pada beberapa dunia nyata yang setara. Misalnya, tumpukan adalah tumpukan CD tempat Anda dapat mengeluarkan dan memasukkan CD melalui bagian atas tumpukan CD. Demikian pula, Antrian adalah antrian untuk tiket Teater di mana orang yang berdiri di tempat pertama, yaitu, depan antrian akan dilayani terlebih dahulu dan orang baru yang tiba akan muncul di belakang antrian (ujung belakang antrian).

Grafik perbandingan

Dasar untuk perbandingan	Tumpukan	Antre
Prinsip bekerja	LIFO (Terakhir Keluar Pertama)	FIFO (First in First out)
Struktur	Ujung yang sama digunakan untuk menyisipkan dan menghapus elemen.	Satu ujung digunakan untuk penyisipan, yaitu, ujung belakang dan ujung lainnya digunakan untuk penghapusan elemen, yaitu, ujung depan.
Jumlah pointer yang digunakan	Satu	Dua (Dalam kasus antrian sederhana)
Operasi dilakukan	Push dan Pop	Enqueue dan dequeue
Pemeriksaan kondisi kosong	Atas == -1	Depan == -1 || Depan == Belakang + 1
Pemeriksaan kondisi penuh	Atas == Maks - 1	Belakang == Maks - 1
Varian	Itu tidak memiliki varian.	Ini memiliki varian seperti antrian melingkar, antrian prioritas, antrian berakhir ganda.
Pelaksanaan	Lebih sederhana	Relatif kompleks

Definisi tumpukan

Stack adalah struktur data linier non-primitif. Ini adalah daftar yang dipesan di mana item baru ditambahkan dan elemen yang ada dihapus hanya dari satu ujung, disebut sebagai bagian atas tumpukan (TOS). Karena semua penghapusan dan penyisipan dalam tumpukan dilakukan dari atas tumpukan, elemen terakhir yang ditambahkan akan menjadi yang pertama dihapus dari tumpukan. Itulah alasan mengapa tumpukan disebut jenis daftar Last-in-First-out (LIFO).

Perhatikan bahwa elemen yang sering diakses di tumpukan adalah elemen paling atas, sedangkan elemen terakhir yang tersedia di bagian bawah tumpukan.

Contoh

Beberapa dari Anda mungkin makan biskuit (atau Poppins). Jika Anda berasumsi, hanya satu sisi penutup sobek, dan biskuit dikeluarkan satu per satu. Inilah yang disebut popping, dan demikian pula, jika Anda ingin menyimpan beberapa biskuit untuk beberapa waktu kemudian, Anda akan memasukkannya kembali ke dalam bungkusan melalui ujung yang sama disebut mendorong.

Definisi Antrian

Antrian adalah struktur data linier yang masuk dalam kategori tipe non-primitif. Ini adalah kumpulan elemen sejenis. Penambahan elemen baru terjadi di satu ujung yang disebut ujung belakang. Demikian pula, penghapusan elemen-elemen yang ada terjadi di ujung lain yang disebut Front-end, dan secara logis jenis Pertama masuk pertama keluar (FIFO) daftar.

Contoh

Dalam kehidupan kita sehari-hari kita menemukan banyak situasi di mana kita keluar untuk menunggu layanan yang diinginkan, di sana kita harus masuk ke antrian menunggu giliran kita untuk dilayani. Antrian tunggu ini dapat dianggap sebagai antrian.

Perbedaan utama antara tumpukan dan antrian

1. Stack mengikuti mekanisme LIFO di sisi lain Antrian mengikuti mekanisme FIFO untuk menambah dan menghapus elemen.
2. Dalam tumpukan, ujung yang sama digunakan untuk menyisipkan dan menghapus elemen. Sebaliknya, dua ujung yang berbeda digunakan dalam antrian untuk menyisipkan dan menghapus elemen.
3. Karena Stack hanya memiliki satu ujung terbuka yang merupakan alasan untuk menggunakan hanya satu pointer untuk merujuk ke bagian atas tumpukan. Tetapi antrian menggunakan dua pointer untuk merujuk depan dan ujung belakang antrian.
4. Stack melakukan dua operasi yang dikenal sebagai push dan pop sedangkan dalam Queue dikenal sebagai enqueue dan dequeue.
5. Implementasi stack lebih mudah sedangkan implementasi antrian rumit.
6. Antrian memiliki varian seperti antrian bundar, antrian prioritas, antrian berakhir ganda, dll. Sebaliknya, tumpukan tidak memiliki varian.

Implementasi Stack

Tumpukan dapat diterapkan dengan dua cara:

1. Implementasi statis menggunakan array untuk membuat stack. Implementasi statis meskipun merupakan teknik yang mudah tetapi bukan cara pembuatan yang fleksibel, karena deklarasi ukuran stack harus dilakukan selama desain program, setelah itu ukurannya tidak dapat bervariasi. Selain itu, implementasi statis tidak terlalu efisien dalam penggunaan memori. Karena sebuah array (untuk mengimplementasikan stack) dideklarasikan sebelum dimulainya operasi (pada waktu desain program). Sekarang jika jumlah elemen yang akan diurutkan sangat sedikit di stack memori yang dialokasikan secara statis akan terbuang. Di sisi lain, jika ada lebih banyak jumlah elemen yang akan disimpan di stack maka, kita tidak dapat mengubah ukuran array untuk meningkatkan kapasitasnya, sehingga dapat mengakomodasi elemen baru.
2. Implementasi dinamis juga disebut representasi daftar tertaut dan menggunakan pointer untuk mengimplementasikan tipe tumpukan dari struktur data.

Implementasi antrian

Antrian dapat diimplementasikan dengan dua cara:

1. Implementasi statis : Jika antrian diimplementasikan menggunakan array, jumlah elemen yang ingin kita simpan dalam antrian harus dipastikan sebelumnya, karena ukuran array harus dideklarasikan pada waktu desain atau sebelum pemrosesan dimulai. Dalam hal ini, awal array akan menjadi bagian depan antrian, dan lokasi terakhir array akan bertindak sebagai bagian belakang antrian. Relasi berikut memberi seluruh elemen yang ada dalam antrian ketika diimplementasikan menggunakan array:
   depan - belakang +1
   Jika "belakang <depan" maka tidak akan ada elemen dalam antrian atau antrian akan selalu kosong.
2. Implementasi dinamis : Menerapkan antrian menggunakan pointer, kelemahan utama adalah bahwa sebuah simpul dalam representasi terkait mengkonsumsi lebih banyak ruang memori daripada elemen yang sesuai dalam representasi array. Karena setidaknya ada dua bidang di setiap node satu untuk bidang data dan lainnya untuk menyimpan alamat simpul berikutnya sedangkan dalam representasi terkait hanya bidang data yang ada. Manfaat menggunakan representasi tertaut menjadi jelas ketika diharuskan untuk memasukkan atau menghapus elemen di tengah sekelompok elemen lainnya.

Operasi di Stack

Operasi dasar yang dapat dioperasikan pada stack adalah sebagai berikut:

1. PUSH : ketika elemen baru ditambahkan ke bagian atas tumpukan dikenal sebagai operasi PUSH. Mendorong suatu elemen di tumpukan meminta penambahan elemen, karena elemen baru akan dimasukkan di bagian atas. Setelah setiap operasi push, bagian atas dinaikkan satu. Jika array penuh, dan tidak ada elemen baru dapat ditambahkan, itu disebut kondisi STACK-FULL atau STACK OVERFLOW. PUSH OPERATION - fungsi dalam C:
   Mengingat tumpukan dinyatakan sebagai
   int 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");
}
}
2. POP : Ketika suatu elemen dihapus dari atas tumpukan itu dikenal sebagai operasi POP. Tumpukan berkurang satu, setelah setiap operasi pop. Jika tidak ada elemen yang tersisa di tumpukan dan pop dilakukan, maka ini akan menghasilkan kondisi STACK UNDERFLOW yang berarti tumpukan Anda Kosong. OPERASI POP - fungsi dalam C:
   Mengingat tumpukan dinyatakan sebagai
   int 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 Antrian

Operasi dasar yang dapat dilakukan dalam antrian adalah:

1. Enqueue : Untuk menyisipkan elemen dalam antrian. Menambah fungsi operasi di C:
   Antrian dinyatakan sebagai
   int 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") ;
}
}

2. Dequeue : Untuk menghapus elemen dari antrian. Mengeluarkan fungsi operasi di C:
   Antrian dinyatakan sebagai
   int 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 kompiler.
• Mesin virtual Java.
• Membatalkan dalam pengolah kata.
• Tombol kembali di browser Web.
• Bahasa PostScript untuk printer.
• Menerapkan panggilan fungsi dalam kompiler.

Aplikasi Antrian

• Buffer data
• Transfer data tidak sinkron (file IO, pipa, soket).
• Mengalokasikan permintaan pada sumber daya bersama (printer, prosesor).
• Analisis lalu lintas.
• Tentukan jumlah kasir untuk dimiliki di supermarket.

Kesimpulan

Stack dan Queue adalah struktur data linier yang berbeda dalam beberapa hal seperti mekanisme kerja, struktur, implementasi, varian tetapi keduanya digunakan untuk menyimpan elemen dalam daftar dan melakukan operasi pada daftar seperti penambahan dan penghapusan elemen. Meskipun ada beberapa batasan antrian sederhana yang dapat digunakan kembali dengan menggunakan jenis antrian lainnya.