Queue

Queue (antrian) merupakan struktur data yang meniru antrian orang.
Konsep queue : FIFO (First In First Out)
artinya yang pertama masuk antrian itulah yang pertama dilayani.
Implementasi queue :
type queue : record
<
       count, front, rear : integer;
       isi : array [1 .. maks] of item;
>
Isi : array yang menyimpan isi antrian
Item : tipe data pada queue, misal int, char, dan sebagainya
Count : variabel untuk mencacah jumlah elemen dalam antrian
Front : variabel yang menunjuk pada awal (bagian paling depan) antrian
Rear : variabel yang menunjuk pada bagian akhir (bagian paling belakang) antrian

Proses utama queue :
#  Initialize : proses memulai antrian
#  Enqueue : proses menambahkan elemen
#  Dequeue : proses mengambil elemen
#  Size : proses menghitung jumlah elemen

1. Initialize
Prosedur initialize(in-out q : queue)
{memulai suatu antrian}

Deifinisi Variabel
{tidak ada}

Rincian Langkah
q.count ← 0;
q.front ← 1;
q.rear ← 0;
return;

2. Enqueue
Elemen ditambahkan dari belakang sehingga count bertambah 1, rear juga bertambah 1.

Prosedur enqueue(input x : item; in-out q : queue)
{menambah elemen ke dalam antrian}

Definisi Variabel
{tidak ada}

Rincian Langkah
if (q.count = maks)
        then write("antrian penuh");
else
        q.count ← q.count + 1;
        q.rear ← (rear % maks) + 1;
        q.isi[rear] ← x;
endif

3. Dequeue
Elemen yang diambil dari antrian selalu dari depan, sehingga count berkurang 1, dan front bertambah 1.
Prosedur dequeue(input x : item; in-out q : queue)
{mengambil 1 elemen dari antrian}

Definisi Variabel
{tidak ada}

Rincian Langkah
if (q.count = 0)
        then write("antrian kosong");
else
        q.count ← q.count - 1;
        x ← q.isi[front];
        q.front ← (front % maks) + 1;
endif

4. Size
Fungsi size(in-out q : queue) → integer
{menghitung jumlah elemen dalam antrian}

Definisi Variabel
int n;

Rincian Langkah
n ← q.count;
return n;

Perbedaan Stack & Queue

Stack

Stack (tumpukan) merupakan struktur data yang meniru bagaimana proses menyimpan dan mengambil suatu benda pada tumpukan.

Konsep stack : LIFO (Last In First Out)
artinya benda yang terakhir disimpan pada tumpukan (paling atas) adalah benda pertama yang diambil.
Implementasi stack:
type stack : record
<
       top : integer;
       isi : array [1 .. maks] of item;
>
Isi : array yang memuat data dalam tumpukan
Item : tipe data yang disimpan datam stack, misal int, char, dan sebagainya
Top : posisi teratas dari tumpukan
Top = 0, jika stack kosong
Top = maks, jika stack penuh
Setiap mengisi data, top bertambah 1, setiap menambil data top berkurang 1.

Proses utama dalam stack :
#  Push : proses menyimpan
#  Pop : proses mengambil
Proses tambahan :
#  Initialize : proses memulai, yaitu menciptakan stack kosong
#  Peek : melihat elemen teratas
#  IsEmpty : memeriksa apakah suatu tumpukan kosong

1. Push (Penyimpanan Data)

Prosedur push (input x : item; in-out s : stack)
{prosedur menempatkan item pada posisi top
dari stack}

Definisi Variabel
int atas;

Rincian Langkah
if s.top = maks
       then write ("sudah penuh");
else
       s.top ← s.top + 1;
       atas ← s.top;
       s.isi[atas] ← x;
endif

2. Pop (Pengambilan Data)

Prosedur pop (output x : item; in-out s : stack)
{prosedur mengambil data dari tumpukan pada
posisi top dari stack}

Definisi Variabel
int atas;

Rincian Langkah
if s.top = 0;
       then write ("tumpukan kosong");
else
       atas ← s.top;
       x ← s.isi[atas];
       s.top ← s.top - 1;
endif

3. Initialize (Memulai)

Prosedur initialize (in-out s : stack)
{memulai suatu stack}

Definisi Variabel
{tidak ada}

Rincian Langkah
       s.top ← 0;

4. Peek

Fungsi peek (in s : stack) → item
{fungsi untuk melihat elemen teratas dari suatu stack}

Definisi Variabel
item x;
int  atas;

Rincian Langkah
       atas ← s.top;

       x ← s.isi[atas];
       return x;

5. IsEmpty

Fungsi IsEmpty (in s : stack) → boolean
{fungsi untuk memeriksa apakah stack kosong}

Definisi Variabel
{tidak ada}

Rincian Langkah
if (s.top = 0)
       then return true;
else
       return false;
endif

Soal 1
Membalik suatu kalimat yang dimasukkan lewat keyboard. Misalkan inputnya "program tumpukan" maka outputnya "nakupmut margorp".

Jawaban :
1. Setiap huruf mulai dari kiri dimasukkan ke dalam stack s (proses push), hingga seluruhnya ada di dalam s
2. Satu per satu huruf diambil dari s (proses pop)

Algoritma balik_kalimat
{membalikkan kalimat yang diinput dengan memakai stack}

Definisi Variabel
int maks = 128;
char item;
type stack : record;
<
        top : integer;
        isi : array[1 .. maks] of item;
>
stack s;
Prosedur push(input x : item; in-out s : stack);
Prosedur pop(input x : item; in-out s : stack);
Prosedur initialize(in-out s : stack);
string kalimat;
int panjang, i;
char x;

Rincian Langkah
initialize(s);
write("masukkan 1 kalimat : ");
read(kalimat);
panjang ← len(kalimat);
{masukkan huruf per huruf ke stack}
for (i = 1 to panjang step 1)
        x ← substr(kalimat, i, 1);
        push(x, s);
endfor
{baca kembali huruf per huruf dari stack}
for (i = 1 to panjang step 1)
        pop(x, s);
        write(s);
endfor

Soal 2 (UAS Struktur Data 2013/2014 Informatika UNDIP)
Misalkan data 5, 7, 10, 11, dan 3 di push ke stack yang kosong dengan urutan tesebut, kemudian di pop empat kali, hasil poppedelement di push lagi dengan urutan terbalik (yang di pop terakhir di push pertama). Maka top elemen dari stack adalah...

Jawaban :