Satack array

ARRAY STACK and QUEUE

Pengertian Stack

-çStack atau tumpukan adalah suatu stuktur data yang penting dalam pemrograman

-çBersifat LIFO (Last In First Out)

-çBenda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack

-çContohnya, karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.

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

Stack with Array of Struct

-çDefinisikan Stack dengan menggunakan struct

-çDefinisikan MAX§STACK untuk maksimum isi stack

-çBuatlah variabel array data sebagai implementasi stack secara nyata

-çDeklarasikan operasi-operasi/function di atas dan buat implemetasinya

Deklarasi MAX§STACK

#define MAX§STACK 10 //hati-hati mulai dari 0 jadi 0-9

Deklarasi STACK dengan struct dan array data

typedef struct STACKä

int top;

char dataÄ10ÑÄ10Ñ; //misalkan : data adalah array of string

//berjumlah 10 data, masing-masing string

//menampung maksimal 10 karakter

ñ;

Deklarasi/buat variabel dari struct

STACK tumpuk;

Inisialisasi Stack

-çPada mulanya isi top dengan -1, karena array dalam C dimulai dari 0,yang berarti stack adalah KOSONG!

-çTop adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!

-çIlustrasi stack pada saat inisialisasi:

Fungsi IsFull

-çUntuk memeriksa apakah stack sudah penuh?

-çDengan cara memeriksa top of stack, jika sudah sama dengan MAX§STACK-1 maka full, jika belum (masih lebih kecil dari MAX§STACK-1) maka belum full

-çIlustrasi:

Fungsi IsEmpty

-çUntuk memeriksa apakah stack masih kosong?

-çDengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong!

-çProgram:

Fungsi Push

-çUntuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack

-çTambah satu (increment) nilai top of stack terlebih dahulu setiap kali ada penambahan elemen stack, asalkan stack masih belum penuh, kemudian isikan nilai baru ke stack berdasarkan indeks top of stack setelah ditambah satu (diincrement)

-çIlustrasinya:

Fungsi Pop

-çUntuk mengambil elemen teratas dari stack.

-çAmbil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru didecrement nilai top of stack sehingga jumlah elemen stack berkurang

-çIlustrasinya:

Programnya:

Fungsi Print

-çUntuk menampilkan semua elemen-elemen stack

-çDengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil!

Program:

STUDI KASUS

Pembuatan Kalkulator SCIENTIFIC

Misalkan operasi: 3 + 2 * 5

Operasi di atas disebut notasi infiks, notasi infiks tersebut harus diubah lebih dahulu menjadi notasi postfix 3 + 2 * 5 notasi postfiksnya adalah 2 5 * 3 + Kemudian diimplementasikan stack sebagai berikut:

Stack Soal (dalam bentuk postfiks) dan Stack Hasil (masih kosong):

Pop Stack Soal:

-çJika berupa operand, maka masukkan ke Stack Hasil

-çJika berupa operator, maka:

-çPop nilai pertama dari Stack Hasil

-çPop nilai kedua dari Stack Hasil

-çLakukan operasi sesuai dengan operator yang didapat.

Misalnya untuk contoh di atas:

Operator * di pop dari Stack Soal, pop Stack Hasil dua kali, yaitu 5 dan 2 kemudian, simpan 5 ke dalam variabel misalnya a, dan 2 ke dalam variabel misalnya b.

Lalu lakukan operasi sesuai dengan operatornya, b a
Jadi b * a, yaitu 2 * 5 kemudian hasilnya disimpan lagi ke dalam StackHasil


Kemudian lakukan langkah yang sama, sampai selesai.
Pada contoh: operator + dipop dari Stack Soal, pop Stack Hasil dua kali, yaitu 3, disimpan pada variabel a, dan 2, disimpan pada variabel b. Kemudian lakukan operasi sesuai dengan operatornya, b a Jadi b + a, yaitu 8 + 3 = 11.
Contoh, cara lain:
For example, The calculation: ((1 + 2) * 4) + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:
1 2 + 4 * 3 +
The expression is evaluated from the left to right using a stack:
-çpush when encountering an operand and
-çpop two operands and evaluate the value when encountering an operation.
-çpush the result
Like the following way (the Stack is displayed after Operation has taken place):


QUEUE DENGAN MENGGUNAKAN ARRAY
-çQueue = Antrian
-çElemen yang pertama kali masuk ke antrian akan keluar pertama kalinya

-çDEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian
-çAntrian dapat dibuat dengan menggunakan: Liniear Array dan Circular Array

QUEUE DENGAN LINIEAR ARRAY
-çTerdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya
-çSehingga membutuhkan variabel Head dan Tail


OPERASI-OPERASI PADA QUEUE
- Create()
o Untuk menciptakan dan menginisialisasi Queue
o Dengan cara membuat Head dan Tail = -1



- IsEmpty()
�çUntuk memeriksa apakah Antrian sudah penuh atau belum
�çDengan cara