Tumpukan & Antrian dalam Bahasa C

Sebelum membahas mengenai Tumpukan (Stack) & Antrian (Queue), maka kita harus menyinggung dulu tentang link list. link list merupakan rangkaian struktur sejenis (bertipe sama) yang dihubungkan dengan menggunakan salah satu (beberapa) field yang bertipe pointer. Menurut cara pengisian dan pengambilan elemennya, link list dibedakan menjadi dua macam, yaitu tumpukan (Stack) & antrian (Queue).

a. Stack/Tumpukan

Stack adalah jenis link list yang menerapkan konsep LIFO (Last-in First-Out), artyinya elemen struktur yang dimasukkan ke dalam rangkaian terakhir keli apabila ditampilkan kembali maka akan muncul pertama kali. Untuk lebih memahaminya, coba kita bayangkan sebuah tumpukan yang telah selesai dicuci. Di sini piring yang diletakkan pertama kali ke dalam tumpukan tersebut akan di ambil terakhir kali, sedangkan piring yang diletakkan terakhir kali justru akan diambil pertama kali. Cara kerja seperti inilah yang menyebabkan link list ini dinamakan dengan Stack/Tumpukan. Sebagai contoh dari kerja adalah apabila kita memasukkan data secara berurutan seperti di bawah ini:

40

30

20

10

Apabila data tersebut ditampilkan kembali, maka hasil yang akan diberikan adalah sebagai berikut:

10

20

30

40

Untuk membuktikan hal di atas, mari kita perhatikan contoh program berikut ini

#include

#include

/*Mendefinisikan struktur node*/

Operasi-operasi/fungsi Stack

• Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
• Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
• Clear : digunakan untuk mengosongkan stack
• IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
• IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

b. Antrian (Queue)

Queue merupakan kebalikan dari stack, yaitu jenis link list yang menerapkan konsep FIFO (First-In-First-Out). Artinya elemen yang dimasukkan pertama kali apabila ditampilkan akan muncul pertama kali juga. Dengan kata lain, urutan dari keluaran (Output) yang dihasilkan akan sesuai dengan urutan masukan (input) yang dilakuakn. Untuk mempermudah pembahasan, mari kita bayangkan sebuah antrian yang ada di sebuah loket, di situ orang yang dating pertama kali untuk mengantri akan dilayani terlebih dahulu dan yang datang terakhir juga akan dilayani terakhir.

Operasi-Operasi Pada Queue

- Create()

o Untuk menciptakan dan menginisialisasi Queue

o Dengan cara membuat Head dan Tail = -1

- IsEmpty()

o Untuk memeriksa apakah Antrian sudah penuh atau belum

o Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

o Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala

antrian (elemen pertama dalam antrian) yang tidak akan berubahubah

o Pergerakan pada Antrian terjadi dengan penambahan elemen

Antrian kebelakang, yaitu menggunakan nilai Tail

- IsFull()

o Untuk mengecek apakah Antrian sudah penuh atau belum

o Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1

adalah batas elemen array pada C) berarti sudah penuh

- Enqueue(data)

o Untuk menambahkan elemen ke dalam Antrian, penambahan

elemen selalu ditambahkan di elemen paling belakang

o Penambahan elemen selalu menggerakan variabel Tail dengan cara

increment counter Tail

- Dequeue()

o Digunakan untuk menghapus elemen terdepan/pertama dari Antrian

o Dengan cara mengurangi counter Tail dan menggeser semua

elemen antrian kedepan.

o Penggeseran dilakukan dengan menggunakan looping

- Clear()

o Untuk menghapus elemen-elemen Antrian dengan cara membuat

Tail dan Head = -1

o Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus

arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai

-1 sehingga elemen-elemen Antrian tidak lagi terbaca

- Tampil()

o Untuk menampilkan nilai-nilai elemen Antrian

o Menggunakan looping dari head s/d tail