STACK ATAU TUMPUKAN

STACK ATAU TUMPUKAN

Secara bahasa, Stack berarti tumpukan. Jika dikaitkan dengan struktur data, Stack berarti sekumpulan data yang organisasi atau strukturnya bersifat tumpukan atau menyerupai tumpukan. Secara ilustrasi, stack dapat digambarkan dengan gambar di samping. 

“Top “ merupakan pintu untuk keluar masuknya elemen – elemen stack. A, B, dan C merupakan suatu koleksi. Dari ilustrasi dapat digambarkan bahwa C merupakan elemen yang terakhir memasuki stack namun pertama keluar dari stack. Begitu sebaliknya dengan A. A merupakan elemen pertama yang memasuki tumpukan namun terakhir saat keluar dari tumpukan. 

Di dalam gambar juga terlihat urutan masuk dan keluar yang berkebalikan. Elemen yang masuk pertama akan keluar erakhir dan sebaliknya. Prinsip ini telah dikenal dalam struktur data dengan nama prinsip LIFO (Last In First Out). 

Operator penghapusan elemen pada stack disebut POP, sedangkan operator pemasukan elemen, disebut PUSH.

Di dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian tersebut yaitu Single Stack dan Double Stack. 


Single Stack 

Single Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus dilakukan bertahap dari indeks TOP-nya. 
Di dalam proses single stack terdapat tiga macam proses utama, yaitu : 
- Inisialisasi 
- PUSH (Insert, Masuk, Simpan, Tulis) 
- POP (Delete, Keluar, Ambil, Baca, Hapus)

INISIALISASI

Proses inisialisasi merupakan proses awal yang dilakukan untuk menyimpan indeks penunjuk stack. Roses ini dilakukan dengan intruksi :
top = -1; 

PUSH 

Proses push adalah proses memasukkan data baru ke stack indeks selanjutnya. Algoritma dasar proses PUSH adalah : 
top = top + 1;array[top] = variable_tampung;

POP 

Proses pop adalah proses mengeluarkan / mengambil data dari stack dengan indeks yang disimpan pada variable top. Algoritma dasar proses POP adalah : 
variable_tampung = array[top];top = top – 1;

Double Stack 

Double Stack atau Stack Ganda adalah stack yang hanya terdiri dari dua single stack. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus melalui salah satu arah. Di dalam proses double stack terdapat lima macam proses utama, yaitu : 

- Inisialisasi 
- PUSH1 (Proses Push untuk Single Stack pertama) 
- POP1 (Proses Pop untuk Single Stack pertama) 
- PUSH2 (Proses Push untuk Single Stack kedua) 
- POP2 (Proses Pop untuk Single Stack kedua) 

 OPERASI PADA STACK 
Terdapat empat operasi pada stack, yakni CREATE (stack), ISEMPTY(stack), PUSH(elemen, stack), dan POP (stack). CREATE(S) adalah operator yang menyebabkan stack S menjadi satu stack hampa. Jadi NOEL(CREATE(S)) adalah 0, dan TOP(CREATE(S)) tak terdefinisi. 

Sedangkan operator ISEMPTY(S) bermaksud memeriksa apakah stack S hampa atau tidak. Operandnya adalah data bertipe stack, sedangkan hasilnya merupakan data bertipe boolean. ISEMPTY(S) adalah true, jika S hampa, yakni bila NOEL(S) = 0, dan false dalam hal lain. Jelas bahwa ISEMPTY(CREATE(S)) adalah true. 

Operator PUSH (E,S) akan bekerja menambahkan elemen E pada stack S. E ditempatkan sebagai TOP(S). Operator POP(S) merupakan operator yang bekerja mengeluarkan elemen TOP(S) dari dalam stack. POP(S) akan mengurangi nilai NOEL(S) dengan 1. Suatu kesalahan akan terjadi apabila, kita mencoba melakukan POP(S) terhadap stack S yang hampa. 

Kesalahan overflow akan terjadi jika kita melakukan operasi pemasukan data (PUSH) pada stack yang sudah penuh (dalam hal ini jika banyaknya elemen yang kita masukkan ke dalam sebuah stack sudah melampaui batas kemampuan memori atau telah didefinisikan sebelumnya).

Sebaliknya, kesalahan underflow akan terjadi jika stack sudah dalam keadaan hampa, kita lakukan operasi pengeluaran atau penghapusan (POP).  


SUMBER REFERENSI :

dewa, "Struktur Data – Pengertian Stack " 17 Maret 2018,  https://updoc.tips/download/free-pdf-ebook-struktur-data-pengertian-stack

lily, "STACK ATAU TUMPUKAN" from staff.gunadarma.ac.id/Downloads/files/25037/bab3-stack.pdf

LINGKED LIST (NON CIRCULAR)

,

LINKED LIST

(NON CIRCULAR)

Linked list

• Daftar item tertaut diatur secara berurutan

• Ukuran perubahan daftar yang ditautkan sebagai item

disisipkan atau dihapus

• Alokasi memori dinamis sering digunakan

dalam implementasi daftar terkait

• Sepuluh fungsi dasar digunakan

memanipulasi daftar tertaut (lihat buku teks).

Definisi Linked

List Pengolahan data yang kita lakukan menggunakan komputer seringkali mirip dengan ilustrasi di atas, yang antara lain berupa penyimpanan data dan pengolahan lain dari sekelompok data yang telah terorganisir dalam sebuah urutan tertentu. Salah satu cara untuk menyimpan sekumpulan data yang kita miliki adalah menggunakan larik. Telah kita bicarakan dalam Bab 1, keuntungan dan kerugian pemakaian larik untuk menyimpan sekelompok data yang banyaknya selalu berubah dan tidak diketahui dengan pasti kapan penambahan atau penghapusan akan berakhir

Fundamental

• Daftar tertaut adalah urutan item yang diatur satu

sesudah yang lain.

• Setiap item dalam daftar terhubung ke item berikutnya melalui a

Link

• Setiap item ditempatkan bersama dengan tautan ke

item berikutnya, menghasilkan komponen sederhana yang disebut a

simpul.

Mendeklarasikan Kelas untuk Node

struct Node

{

               typedef ganda Item;

               Data barang; // data disimpan dalam node

               Tautan Node *; // arahkan ke simpul berikutnya

};

Sebuah struct adalah jenis kelas khusus di mana semua anggotanya berada

publik. Dalam hal ini ada dua anggota masyarakat

variabel: data, tautan.

Setiap kali sebuah program perlu merujuk ke jenis barang, kami

dapat menggunakan ekspresi Node :: Item.

Kepala Pointer, Tail Pointer

Biasanya, program tidak benar-benar menyatakan

variabel node. Sebaliknya, daftar itu diakses

melalui satu atau lebih pointer ke node.

Struct Node

{

typedef ganda Item;

Data barang;

Tautan Node *;

};

Node * head_ptr;

Node * tail_ptr;

Single linked list

• Simpul terakhir dalam daftar tertaut tidak

arahkan ke simpul berikutnya.

• Jika tautan tidak menunjuk ke suatu simpul, nilainya adalah

diatur ke NULL.

• NULL adalah konstanta C ++ khusus, dari

fasilitas perpustakaan standar <stdlib.h>

• Penanda NULL sering ditulis 0 (nol).

Penggunaan penunjuk NULL di node terhubung terakhir

daftar:

Untuk mengakses elemen dalam linked list, dimulai dari head dan menggunakan pointer next dari elemen selanjutnya untuk berpindah dari elemen ke elemen berikutnya sampai elemen yang diminta dicapai. Dengan single linke list, list dapat dilintasi hanya satu arah dari head ke tail karena masing-masing elemen tidak terdapat link dengan elemen sebelumnya. Sehingga, apabila kita mulai dari head dan berpindah ke beberapa elemen dan berharap dapat mengakses elemen sebelumnya, kita harus mulai dari head.

Secara konseptual, linked list merupakan deretan elemen yang berdampingan. Akan tetapi, karena elemen-elemen tersebut dialokasikan secara dinamis (menggunakan malloc), sangat penting untuk diingat bahwa kenyataannya, linked list akan terpencarpencar di memori Pointer dari elemen ke elemen berarti sebagai penjamin bahwa semua elemen dapat diakses.

Alokasi Simpul

Ketika sebuah variabel dideklarasikan, terlebih dahulu harus diinisialisasi. Demikian juga dengan pengalokasian secara dinamis. Sehingga, fungsi untuk mengalokasikan sebuah node baru, fungsi allocate_node() menggunakan malloc() untuk mendapatkan memori aktual, yang akan menginisialisasi suatu field data. next selalu diinisialisasi sebagai NULL.

 Untuk melihat kemungkinan alokasi memori gagal, maka fungsi allocate_node menghasilkan 0, bila berhasil maka menghasilkan 1. Untuk membebaskan node digunakan fungsi free_node. Fungsi dari alokasi node adalah sebagai berikut :

int allocate_node(int data, list *new)

{

new = (list) malloc (sizeof(node));

if(new==NULL)

return 0;

new->datalist = data;

new->next=NULL;

return 1;

}

Memasukkan Node di List Head

Void list_head_insert (Node * head_ptr, const Node :: Item & entri)

{

// Prekondisi: head_ptr adalah penunjuk kepala ke daftar tertaut

// Postcondition: node baru ditambahkan ke depan daftar yang berisi entri, dan

// head_ptr diatur ke titik di node baru.

Node *insert_ptr;

insert_ptr = new Node;

insert_ptr->data = entry; 

insert_ptr->link = head_ptr; 

head_ptr = insert_ptr; }

Mencari Daftar untuk Item

Node* list_search(Node* head_ptr, const Node::Item& target) 

{ 

// Prekondisi: head_ptr adalah penunjuk kepala ke daftar tertaut

// Postcondition: nilai kembalian adalah pointer ke node pertama yang berisi

// target yang ditentukan. Mengembalikan NULL jika tidak ditemukan simpul yang cocok.

Node *cursor; 

for(cursor = head_ptr; cursor != NULL; cursor = cursor->link) 

               if(target == cursor->data) 

                               return cursor; 

return NULL; 

}

Menghapus Node di List Head

void list_head_remove(Node* head_ptr)

{

// Prekondisi: head_ptr adalah penunjuk kepala ke daftar tertaut

// Postcondition: node pertama dihapus dari daftar depan, dan

// head_ptr diatur untuk menunjuk pada head_ptr-> tautan. Node yang dihapus dihapus

Node *remove_ptr; 

remove_ptr = head_ptr; 

head_ptr = head_ptr->link; 

delete remove_ptr; 

}

Menghapus bukan Node di List Head

void list_remove(Node* previous_ptr)

{

// Prekondisi: previous_ptr adalah pointer ke node dalam daftar tertaut

// Postcondition: node dihapus dari daftar depan, dan

// dihapus node dihapus

Node *remove_ptr;

remove_ptr = previous_ptr->link;

previous_ptr->link = remove_ptr->link;

delete remove_ptr;

}

Daftar pustaka:

Kruse and Ryba Textbook.”Lngked List” from cs.bu.edu/fac/gkollios/cs113/Slides/linkedlist.pdf

Martiana,E,K.(2009). “Senarai berantai (linked list)” from entin.lecturer.pens.ac.id

ARRAY BERDIMENSI BANYAK

ARRAY

BERDIMENSI BANYAK

Sebuah array dimensi banyak atau multi-dimensional array didefinisikan sebagai sebuah array yang elemennya berupa array pula. Misal array B mempunyai M elemen berupa array pula, yang terdiri dari N elemen. Kalau hal tersebut kita gambarkan, akan terbentuk baris dan kolom seperti terlihat pada Gambar

Untuk itu diperlukan dua buah subscript. Yang pertama digunakan untuk menyatakan posisi baris, sedangkan yang kedua untuk posisi kolom. Secara umum array dimensi dua B, dengan elemen bertipe data T, subscript baris dari l sampai M, subscript kolom dari l sampai N, ditulis sebagai B(1:M, 1:N) = (B(I,J)), I = 1, 2, ...,M dan J = 1, 2,...,N dengan setiap elemen B(I,J) bertipe data T. Array B tersebut dikatakan berukuran atau berorder M x N. Di sini banyak elemen array adalah M*N. 

Contoh dari array dimensi dua sangat banyak kita jumpai. Misalnya nilai ujian 500 mahasiswa Gunadarma tingkat 3, untuk 8 mata kuliah dapat kita sajikan sebagai array dimensi dua yang berorder 500 x 8. Elemen B(I,J) menyatakan nilai mahasiswa ke-I untuk mata kuliah ke-J.

Seperti halnya pada array dimensi satu, pada array dimensi dua batas bawah untuk subscript I maupun J dapat diambil secara umum. Misalnya, batas bawah subscript baris adalah L1 subscript kolom adalah L2 sedangkan batas atas subscript baris adalah U1 dan untuk kolom adalah U2, maka array dimensi dua tersebut dapat dinotasikan sebagai :

B(L1:U1, L2:U2) = (B(I,J)), L1 <= 1 <= U1, L2 <=J <= U2 

dengan setiap elemen B(I,J) bertipe data T. Banyaknya elemen pada setiap baris adalah U2 – L2 + 1 dan pada setiap kolom adalah U1–L1+l, sehingga banyaknya elemen pada array B semua ada = (U2-L2 +1) * (U1-L1 +1). 

Yang dimaksud dengan cross-section suatu array berdimensi dua adalah pengambilan salah satu subscript, misalnya subscript baris untuk tetap atau konstan, sementara subscript yang satunya lagi kita ubah-ubah sepanjang rangenya. Notasi yang umum digunakan adalah notasi * (asterisk) bagi subscript yang berubah-ubah nilainya tersebut.

Contohnya, penulisan B(*,4) menyatakan semua elemen pada kolom ke-4, yakni (B(1,4),B(2,4), B(3,4) ...., B(M,4)), seperti terlihat pada Gambar 

Dengan mudah dapat dimengerti bahwa B(11,*) menunjukkan semua elemen pada baris ke-11.

Transpose dari suatu array dimensi dua adalah penulisan baris menjadi kolom (kolom menjadi baris) dari suatu array. Jadi transpose dari array berorder M x N adalah array berorder N x M. Transpose dari array B dinotasikan sebagai BT . Berdasarkan definisi, maka jelas B(I,J) =BT (J,I). Contohnya B(3,5) = BT (5,3). 

Pengertian di atas dapat kita perluas untuk array dimensi tiga, dimensi empat, sampai dimensi N. Array dimensi N kita tulis sebagai :

 A(L1:U1, L2:U2, …, LN: UN) = (A(I1, I2, …, IN))

 dengan Lk <= Ik <= Uk, untuk setiap k = 1, 2, …, N.  

Banyaknya elemen dari array A tersebut adalah : 

PI(Uk - Lk + 1) = (U1-L1+1) * (U2 – L2+1) … * (UN -LN + 1) 

Contoh array dimensi tiga adalah penyajian data mengenai banyaknya mahasiswa dari-20 perguruan tinggi di Jakarta, berdasarkan tingkat (tingkat 1, 2 sampai dengan 5), dan jenis kelamin (pria atau wanita). Misalnya array tersebut dinamakan MHS. Ambil sebagai subscript pertama, tingkat : I = 1, 2,...,5; subscript kedua, jenis kelamin (pria = 1, wanita = 2): J = 1,2, dan subscript ke-3, Perguruan Tinggi adalah K = 1,2,...,20. Jadi MHS(4,2,17) menyatakan jumlah mahasiswa tingkat 4, wanita, dari perguruan tinggi ke 17.

Array dimensi tiga dapat kita bayangkan seperti Gambar 

Pengertian cross-section pada array dimensi banyak, adalah sama seperti pada array dimensi dua. Misalnya MHS(4,*,17) menunjukkan jumlah mahasiswa tingkat 4 dari perguruan tinggi 17 (masing-masing untuk pria serta wanita). MHS(*,*,3) menun-jukkan jumlah mahasiswa untuk masing-masing tingkat, pria serta wanita, dari perguruan tinggi 3. 

C memungkinkan untuk membuat array yang dimensinya lebih dari 2. bentuk umum pendeklarasian array dimensi banyak:

tipe nama_varchar[ukuran1] [ukuran2] ... [ukuranN]

sumber referensi: 

entin "array" entin.lecturer.pens.ac.id  

julio, 2011"array (larik) record" julio.staff.ipbc.ac.id/files/2011/12/6.pdf 

REPRESENTASI DATA

 REPRESENTASI DATA

Komputer menggunakan dan memanipulasi data untuk perhitungan aritmatik, pemrosesan data, dan operasi logik.

Type data yang digunakan dalam komputer digital diklasifikasikan:

• Data Numerik: merepresentasikan integer, pecahan, real, dan desimal berkode biner. 

• Data Logikal: digunakan oleh operasi seperti OR, AND, COMPLEMENT, COMPARE dan SHIFT.

• Data Bit Tunggal: digunakan oleh operasi seperti SET, CLEAR, dan TEST. 

• Data Alfanumerik: digunakan untuk manipulasi string oleh instruksi seperti MOVE dan SEARCH

Data : bilangan biner atau informasi berkode biner lain yang dioperasikan untuk mencapai beberapa hasil penghitungan penghitungan aritmatik, pemrosesan data dan operasi logika.

Tipe data : 

1. Data Numerik : merepresentasikan integer dan pecahan fixed-point, real floating-point dan desimal berkode biner.

2. Data Logikal : digunakan oleh operasi logika dan untuk menentukan atau memriksa kondisi seperti yang dibutuhkan untuk instruksi bercabang kondisi. 

3. Data bit-tunggal : untuk operasi seperti SHIFT, CLEAR dan TEST. 

4. Data Alfanumerik : data yang tidak hanya dikodekan dengan bilangan tetapi juga dengan huruf dari alpabet dan karakter khusus lainnya

Representasi Eksternal adalah suatu cara untuk merepresentasikan dan memanipulasi informasi oleh programmer dengan suatu bahasa pemrograman atau notasi bahasa perintah lainnya  agar nyaman bagi programmer (user).

Representasi Internal adalah suatu cara untuk menyimpan dan memanipulasi informasi secara aktual di dalam sistem komputer agar mudah dalam membangun perangkat keras.

Representasi sign-magnitude

• Dalam sistem biner, representasi bilangan signed berisi: tanda (sign) dan besar nilai (magnitude) ◦ Tanda diyatakan oleh bit paling kiri (0: bilangan positif, 1: bilangan negatif) • Bilangan n-bit: 1 bit paling kiri menyatakan tanda, n-1 bit berikutnya menunjukan besar nilai bilangan

• Di bilangan signed, terdapat 3 format yang umum digunakan untuk representasi bilangan negatif

1. Sign-Magnitude 

2. 1’s Complement 

3. 2’s Complement 

• Bilangan sign-magnitude menggunakan 1 bit paling kiri untuk menyatakan tanda (0: positif, 1: negatif) dan bit sisanya menyatakan magnitude (besar nilai bilangan). Bilangan 4-bit:

	0	1	2	3	4	5	6	7
Positif	0000	0001	0010	0011	0100	0101	0110	0111
Negatif	1000	1001	1010	1011	1100	1101	1110	1111

•Walaupun ini mudah dipahami, tapi ini tidak cocok digunakan di sistem komputer (dibahas di Operasi Bilangan)

Representasi complemen 1

• Skema komplemen 1:

 Bilangan n-bit negatif K dapat diperoleh dari mengurangkan 2n − 1 dengan bilangan positif   ekivalennya P 

K = (2n − 1) − P 

• Misalnya untuk bilangan 4-bit (n=4):

 K = (24 − 1) − P = 15 − P = (1111)2 − P

	0	1	2	3	4	5	6	7
Positif	0000	0001	0010	0011	0100	0101	0110	0111
Negatif	1000	1001	1010	1011	1100	1101	1110	1111

• Terlihat bahwa complemen 1 dapat dibentuk dengan mengkomplemenkan tiap bit bilangan,     termasuk bit tanda 

• Masih ada kekurangan dari penggunaan complemen 1 (dibahas di Operasi Bilangan)

Representasi complemen 2

• Skema Complemen 2: 

Bilangan n-bit negatif K dapat diperoleh dari mengurangkan 2n dengan bilangan positif    ekivalennya P 

K = 2n − P 

• Misalnya untuk bilangan 4-bit (n=4):

K = 24 − P = 16 − P = (10000)2 − P

	0	1	2	3	4	5	6	7
Positif	0000	0001	0010	0011	0100	0101	0110	-
Negatif	1000	1001	1010	1011	1100	1101	1110	1111

• Penjumlahan bilangan biner dilakukan sama seperti penjumlahan bilangan-bilangan desimal. 

• Operasi pengurangan, perkalian dan pembagian seperti yang dilakukan pada komputer dan     kalkulator digital sesungguhnya menggunakan penjumlahan sebagai operasi dasarnya. 

• Ada 4 kondisi dalam penjumlahan bilangan biner:

 0 + 0 = 0

 1 + 0 = 1 

 0 + 1 = 1

 1 + 1 = 0 (carry out 1) 

Maksud dari carry out, hasilnya tidak bisa memuat lebih dari 1 digit, tetapi disimpan ke    dalam kolom sebelah yang lebih tinggi nilainya (digit paling kiri yang diabaikan).

Konversi Angka Biner ke Desimal 

Perhatikan contoh! 

1. 11001101(2)

Note: 

• Angka desimal 205 didapat dari penjumlahan angka yang di arsir (128+64+8+4+1)

• Setiap biner yang bertanda “1” akan dihitung, sementara biner yang bertanda “0” tidak dihitung,     alias “0” juga. 

2. 00111100(2)

Mengubah Angka Desimal ke Biner Untuk mengubah angka desimal menjadi angka biner digunakan metode pembagian dengan angka 2 sambil memperhatikan sisanya. Perhatikan contohnya! 

1. 205(10) 

205 : 2 = 102 sisa 1 

102 : 2 = 51 sisa 0 

51 : 2 = 25 sisa 1 

25 : 2 = 12 sisa 1 

12 : 2 = 6 sisa 0 

6 : 2 = 3 sisa 0 

3 : 2 = 1 sisa 1 

1   sebagai sisa akhir “1” 

Note: 

Untuk menuliskan notasi binernya, pembacaan dilakukan dari bawah yang berarti 11001101(2) 

2. 60(10) 

60 : 2 = 30 sisa 0 

30 : 2 = 15 sisa 0 

15 : 2 = 7 sisa 1 

7 : 2 = 3 sisa 1 

3 : 2 = 1 sisa 1 

1   sebagai sisa akhir “1” 

Note: 

Dibaca dari bawah menjadi 111100(2) atau lazimnya dituliskan dengan 00111100(2). Ingat bentuk umumnnya mengacu untuk 8 digit! Kalau 111100 (ini 6 digit) menjadi 00111100 (ini sudah 8 digit)

Konversi bilangan Desimal ke Oktal 

Konversi bilangan desimal bulat ke bilangan oktal: Gunakan pembagian dgn 8 secara suksesif sampai sisanya = 0. Sisa-sisa pembagian membentuk jawaban, yaitu sisa yang pertama akan menjadi least significant bit (LSB) dan sisa yang terakhir menjadi most significant bit (MSB). 

Contoh:

 Konersi 17910 ke oktal: 

 179 / 8 = 22 sisa 3 (LSB)  

 /8 = 2 sisa 6

/ 8 = 0 sisa 2 (MSB) 

  17910 = 2638

 MSB LSB 

Konversi bilangan Desimal ke Hexadesimal 

Konversi bilangan desimal bulat ke bilangan hexadesimal: Gunakan pembagian dgn 16 secara suksesif sampai sisanya = 0. Sisa-sisa pembagian membentuk jawaban, yaitu sisa yang pertama akan menjadi least significant bit (LSB) dan sisa yang terakhir menjadi most significant bit (MSB). 

Contoh: 

Konersi 17910 ke hexadesimal: 179 

/ 16 = 11 sisa 3 (LSB) 

 / 16 = 0 sisa 11 (dalam bilangan hexadesimal berarti B)MSB 

17910 = B316 MSB LSB 

REFERENSI:

Eko didik,W(2011). Representasi Bilangan dan Operasi Aritmatika. from didik.blog.undip.ac.id

Feoh, G(2011). sistem bilagan dan konversi bilangan. from lulu_mawadah.staff.gunadarma.ac.id