Apa yang dimaksud dengan stack

STACK / TUMPUKAN

Table of Contents Show

Backtracking
B. Uraian Materi Materi 1 : Pengertian Stack
Video yang berhubungan

Stack adalah kumpulan elemen - elemen data yang di simpan dalam satu lajur linier dan hanya boleh di akses pada satu lokasi saja yaitu pada posisi top tumpukan. .contoh dalam kebidupan sehari-hari adalah tumpukan piring disebuah restoran yang tumpukanya ditambah pada bagian paling atas dan jika mengambilnya pun dari bagian paling atas pula.

Dalam Struktur STACK. di gunakan istilah :

- Operasi push yaitu operasi menambahkan elemen pada urutan terakhir(paling atas).

PUSH untuk : Simpan, Masuk, Insert atau Tulis.

- Operasi pop yaitu mengambil sebuah elemen data pada urutan terakhir dan menghapus elemen tersebut dari stack.

POP untuk : Ambil, Keluar, Delete, Baca atau Hapus.

Prinsip atau prosesmkonsepnya disebut LIFO ( Last In First Out), Artinya elemen yang terakhir masuk ituyang akan pertama di keluarkan dari tumpukan.

Sebagai contoh misalkan ada data sebagai berikut:
1 3 5 6, maka data tersebut dapat tersimpan dalam bentuk sebagai berikut:

Contoh lain adalah ada sekumpulan perintah stack yairu push(5),push(7),pop,push(3),pop.jika dijalankan, maka akan terjadi adalah:

A.1 Ilustrasi Single Stack

B.Proses Operasi Stack
   Selain operasi dasar stack ada lagi operasi lain dapat terjadi dalam stack yaitu:
   1.Proses Deklarasi yaitu proses pendeklarasian stack.
   2.Proses IsEmpty yaitu proses pemeriksaan apakah stack dalam keadaan kosong.
   3.Proses IsFull yaitu proses pemeriksaan apakah stack telah penuh.
   4.Proses Inisialisasi yaitu proses pembuangan stack kosong,biasanya dengan pemberian nial untuk top.

C.Representasi Stack
   Representasi Stack dengan array dalam pemograman dapat dilakukan dengan 2 cara yaitu:
   1.Representasi stack dengan aray
   2.Representasi stack dengan singke linked list.

D. Oprasi Dasar Pada Stack/Tumpukan

1. Push : di gunakan untuk menambah item pada stack pada tumpukan paling atas

2. Pop : digunakan untuk mengambil item pada stack pada tumpukanpaling atas

3. Cear : digunakan untuk mengosongkan stack

4. IsEmpty : fungsi ini di gunakan untuk mengecek apakh stack sudahkosong

5. IsFull : fungsi yang di gunakan untuk mengecek apakah stack sudah penuh.

Dalam ilmu komputer, tumpukan (bahasa Inggris: stack) merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari tumpukan tersebut. Operasi untuk memasukkan data biasa disebut push dan operasi untuk mengeluarkan biasanya disebut pop. Tumpukan dapat diimplementasikan sebagai senarai berantai atau larik. Tumpukan tergolong struktur data linear dan operasi push dan pop hanya bisa dilakukan di satu ujung struktur yang biasa disebut top dari tumpukan. Untuk melihat data yang ada di top tanpa mengeluarkannya, biasanya dilakukan menggunakan operasi peek.

Di kalkulator yang menggunakan notasi Polandia terbalik (letak operator bersifat posfiks) menggunakan tumpukan untuk menyimpan nilai. Selain itu, kebanyakan kompilator menggunakan tumpukan untuk menguraikan sintaks ekspresi dan blok program sebelum diterjemahkan ke bahasa level rendah.

Backtracking

Tumpukan bisa dimanfaatkan untuk algoritma backtracking. Misalkan ada sebuah maze. Kita bisa menyimpan daftar lokasi yang kita kunjungi menggunakan Tumpukan. Jadi, apabila kita mencapai jalan buntu, kita tinggal melakukan pop pada tumpukan daftar lokasi lalu mencoba jalan lain. Contoh algoritma backtracking yang sering digunakan adalah pencarian depth-first search pada struktur data pohon.

Wikimedia Commons memiliki media mengenai Stack data structures.

Artikel bertopik komputer ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

Diperoleh dari "https://id.wikipedia.org/w/index.php?title=Tumpukan_(struktur_data)&oldid=16780929"

Stack merupakan salah satu implementasi dari Linked List. Stack merupakan kumpulan-kumpulan data yang menggunakan konsep LIFO (Last In First Out) atau FILO (First In Last Out), yaitu data yang paling terakhir dimasukan ke dalam stack merupakan data yang pertama kali keluar dari stack.

Berikut operasi yang digunakan di dalam Stack:

Push(x): Menambahkan data x ke dalam stack.
Pop(): Menghapus data paling terkahir dari dalam
Peek() atau Top(): Melihat data paling atas dari stack.

Apabila kalian telah mempelajari Single Linkend List (https://socs.binus.ac.id/2017/03/15/single-linked-list/) atau Doubly Linked List (https://socs.binus.ac.id/2017/03/15/doubly-linked-list/), kalian dapat menerapkan fungsi pushDepan & popDepan untuk mengimlementasikan konsep stack. Representasi stack adalah sebagi berikut:

Sample Input 1:

Sample Ouput 1:

Push(5);

Push(10);

Push(12);

Push(3);

Push(30);

Sample Input 1:

Sample Ouput 1:

Push(5);

Push(10);

Pop();

Push(3);

Stack biasanya digunakan untuk:

Mengubah urutan dari data.
Mengubah notasi infix menjadi postfix
Mengubah notasi postfix menjadi infix
Backtracking problem
Mengubah angka decimal menjadi bilangan binary.

Referensi:
Reema Thareja. (2014). Data structures using C. 02. OXFOR. New Delhi. ISBN: 9780198099307.

Published at : 21 December 2018 Updated at : 03 January 2019

B. Uraian Materi Materi 1 : Pengertian Stack

Stack (tumpukan) adalah struktur data yang memungkinkan penyisipan dan pengambilan data dilakukan dari satu ujung yang disebut puncak. Sesuai namanya, struktur data ini digambarkan seperti keadaan tumpukan piring atau tumpukan buku. Cara yang paling mudah untuk meletakkan piring ke dalam tumpukan yakni dengan menaruhnya dibagian puncak. Begitu juga kalau ingin mengambil piring. Piring diambil dari data yangberada di puncak tumpukan. Penyimpanan data/item dimana data/item yang diakses adalah paling akhir yang disebut top of stack. Item ditempatkan membentuk tumpukan.

Gambar 1. Struktur Data Tumpukan

Tumpukan memiliki sifat Last In First Out (LIFO). Artinya, data yang terakhir kali dimasukkan/disisipkan akan menjadi data yang pertama kali keluar. Pada contoh di atas, yang berisi tumpukan A, B, dan C jelas terlihat bahwa C adalah data yang terakhir kali ditumpukkan. Jika terjadi operasi pengambilan data maka C adalah data yang akan keluar terlebih dulu.

Materi 2 : 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 • )sEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong • )sFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

Operasi dasar pada tumpukan adalah PUSH dan POP.

• PUSH adalah operasi untuk memasukkan data ke dalam tumpukan. Operasi ini biasa dinyatakan dengan push(T,d). T menyatakan tumpukan dan d menyatakan item data yang disisipkan ke dalam tumpukan T.

• POP adalah operasi untuk mengambil data dari tumpukan. Operasi ini biasa dinyatakan dengan pop(T). Dalam hal ini data teratas dari tumpukan T akan dikeluarkan dan menjadi nilai balik pop. Itulah sebabnya, penggunaan pop sering dituangkan dalam bentuk pernyataan : data = pop (T);

Materi 3 : Aplikasi Tumpukan

Aplikasi Tumpukan (Stack) sangat banyak, beberapa penerapan Tumpukan diantaranya adalah membalik string. Jika memproses suatu string dimulai dari yang paling kiri dan menaruh ke tumpukan karakter per karakter maka karakter paling kiri akan berada pada posisi paling bawah dalam tumpukan. Kalau kemudian, karakter dalam tumpukan diambil satu persatu dan disusun dari kiri ke kanan maka string akan terbentuk dengan susunan terbalik terhadap aslinya, seperti diperlihatkan pada gambar di bawah ini.

Mengkonversikan bilangan system decimal ke system biner. Contoh Bilangan 19 identik dengan bilangan biner : 10011. Algoritma untuk melakukannya adalah seperti berikut :

1. Tumpukan <---- kosong

2. While Bilangan > 0

3. Digit <---- sisa pembagian bilangan bulat dengan 2

4. Push(Tumpukan, Digit)

5. Bilangan <---- pembagian bilangan bulat dengan 2

6. End-While

7. While (Tumpukan tidak kosong)

8. Digit <---- Pop

9. Tampilkan digit

10. End-While Mengevaluasi Ekspresi Aritmetika. Misalnya, tumpukan dipakai untuk memproses perhitungan semacam (2+1)*3+5*2 yang melibatkan berbagai operator dengan prioritas yang berbeda. Memproses pasangan tanda kurung dalam suatu ekspresi. Misalnya, ekspresi seperti (a(b{c|d}[]) dianggap valid, sedangkan ekspresi (a(b{c|d] dianggap tidak valid. Menangani fungsi Rekursif. Secara internal komputer menggunakan tumpukan ketika terjadi pemanggilan fungsi secara rekursif.

Materi 4 : Queue

Queue disebut juga antrian dimana data masuk di satu sisi dan keluar di sisi yang lain. Karena itu, queue bersifat FIFO (First In First Out). Antrian (Queue) merupakan suatu kumpulan data yang penambahan elemennya (masuk antrian) hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang/rear) atau disebut juga enqueue yaitu apabila seseorang masuk ke dalam sebuah antrian. Jika seseorang keluar dari antrian/penghapusan (pengambilan elemen) dilakukan lewat ujung yang lain (disebut dengan sisi depan/front) atau disebut juga dequeue yaitu apabila seseorang keluar dari antrian. Jadi, dalam antrian menggunakan prinsip masuk pertama keluar pertama atau disebut juga dengan prinsip FIFO (first in first out). Dengan kata lain, urutan keluar akan sama dengan urutan masuknya. Contoh : antrian mobil saat membeli karcis di pintu jalan tol, antrian di bioskop dan sebagainya.

Dasar Teori

Queue atau antrian adalah suatu kumpulan data yang penambahan elemennya hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut dengan sisi depan atau front). Kalau tumpukan dikenal dengan menggunakan prinsip LIFO (Last In First Out), maka pada antrian prinsip yang digunakan adalah FIFO (First In First Out).

Operasi / Prosedur Standar pada QUEUE / ANTRIAN

QUEUE merupakan struktur data dinamis, ketika program dijalankan, jumlah elemennya dapat berubah secara dinamis sesuai keperluan. Berikut ini operasi-operasi standar pada queue :

a. Inisialisasi, merupakan prosedur untuk membuat queue pada kondisi awal, yaitu queue yang masih kosong (belum mempunyai elemen).

b. InQueue, Insert Queue merupakan prosedur untuk memasukkan sebuah elemen baru pada queue. Jumlah elemen Queue akan bertambah satu dan elemen tersebut merupakan elemen belakang.

c. DeQueue, Delete Queue merupakan prosedur untuk menghapus/mengambil sebuah elemen dari queue. Elemen yang diambil adalah elemen depan dan jumlah elemen queue akan berkurang satu.

Operasi-operasi yang berhubungan dengan jumlah elemen suatu queue adalah :

1. Size, yaitu operasi untuk mendapatkan banyaknya elemen queue.

2. Empty, yaitu prosedur untuk mengetahui apakah queue dalam keadaan kosong atau tidak. Dengan status ini maka dapat dicegah dilakukannya operasi Dequeue dari suatu queue yang kosong.

3. Full, merupakan prosedur untuk mengetahui apakah Queue penuh atau tidak. Prosedur ini hanya berlaku untuk queue yang jumlahnya terbatas.

Materi 5 : Implementasi Queue dengan Array Linear dan Sirkular

Karena antrian merupakan suatu kumpulan data, maka tipe data yang sesuai untuk menyajikan antrian adalah menggunakan array atau list (senarai berantai).

Gambar di atas menunjukkan contoh penyajian antrian menggunakan array. Antrian di atas berisi 6 elemen, yaitu A, B, C, D, E dan F. Elemen A terletak di bagian depan antrian dan elemen F terletak di bagian belakang antrian. Jika ada elemen baru yang akan masuk, maka elemen tersebut akan diletakkan di sebelah kanan F. Dan jika ada elemen yang akan dihapus, maka A akan dihapus terlebih dahulu. Elemen A terletak di bagian depan, kemudian disusul elemen B dan elemen yang paling akhir atau paling belakang adalah elemen F. Misalkan ada elemen baru yang akan masuk maka akan terletak di belakang elemen F, sehingga elemen baru akan menempati posisi yang paling belakang. Seperti pada tumpukan atau stack di dalam antrian juga dikenal 2 operasi dasar yaitu menambah elemen baru yang akan diletakkan di bagian belakang antrian dan menghapus elemen yang terletak di bagian depan antrian. Untuk memahami penggunaan antrian dalam array, kita membutuhkan deklarasi antrian, misalnya sebagai berikut :

# define MAXN 6 Typedef enum { NOT_OK, OK } Tboolean; Typedef struct { Titem array [MAXN]; int first; int last; int number_of_items; } Tqueue

Dengan deklarasi di atas, elemen antrian dinyatakan dalam tipe integer yang semuanya terdapat dalam struktur. Variabel first menunjukkan posisi elemen pertama dalam array, dan variabel last menunjukkan posisi elemen terakhir dalam array. Algoritma dari penggalan program di atas adalah :

1. Tentukan elemen yang akan dimasukkan ke dalam antrian (dalam hal ini adalah 6 elemen).

2. Deklarasikan struktur untuk menampung elemen pada antrian.

3. Selesai Untuk menambah elemen baru dan mengambil elemen dari antrian dalam antrian, diperlukan deklarasi berikut ini :

void initialize_queue ( Tqueue *Pqueue) { Pqueue -> firs = 0; Pqueue -> last = -1; Pqueue -> number_of_items = 0; } Tboolean enqueue ( Tqueue *Pqueue, Titem item) { if (Pqueue -> number_of_items >= MAXN) return (NOT_OK); else { Pqueue -> last++; if (Pqueue -> last > MAXN -1) Pqueue -> = 0; Pqueue -> array[Pqueue->last] = item; Pqueue -> number_of_items++; return (OK); } } Tboolean dequeue (Tqueue *Pqueue, Titem, item) { if (Pqueue -> number_of_items == 0) return (NOT_OK); else { *Pitem = Pqueue -> array[Pqueue->first++]; if (Pqueue -> first > MAXN -1) Pqueue -> first = 0; Pqueue -> number_of_items--; return (OK); } }

Materi 6 : Implementasi Queue dengan Linked List

Untuk memanipulasi sebuah antrian bisa digunakan dua buah variabel yang menyimpan posisi elemen paling depan dan elemen paling belakang. Apabila antrian diimplementasikan menggunakan linked list maka cukup 2 pointer yang bisa dipakai yaitu elemen paling depan (kepala) dan elemen paling belakang (ekor). Untuk mengimplementasikan antrian dengan menggunakan pointer, algoritma berikut ini :

1. Tentukan struktur untuk menampung node yang akan dimasukkan pada antrian. Deklarasi struktur pada penggalan program berikut ini : struct queueNode

{ char data; struct queueNode *nextPtr; }; typedef struct queueNode QUEUENODE; ypedef QUEUENODE * QUEUENODEPTR; QUEUENODEPTR headPtr = NULL, tailPtr = NULL;

2. Deklarasikan penambahan elemen baru pada antrian, dimana letaknya adalah paling belakang. Deklarasi penambahan elemen baru tersebut dapat dilihat pada penggalan program berikut ini : void enqueue ( QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr, char value )

{ QUEUENODEPTR newPtr = malloc ( sizeof ( QUEUENODE ) ); If ( newPtr != NULL ) { newPtr -> data = value; newPtr -> nextPtr = NULL; if ( isEmpty ( *headPtr ) ) *headPtr = newPtr; { QUEUENODEPTR newPtr = malloc ( sizeof ( QUEUENODE ) ); If ( newPtr != NULL ) { newPtr -> data = value; newPtr -> nextPtr = NULL; if ( isEmpty ( *headPtr ) ) *headPtr = newPtr;

3. Lakukan pengecekan terhadap antrian, apakah antrian dalam kondisi kosong atau tidak. Kalau kondisi antrian kosong, maka elemen bisa dihapus. Penggalan program berikut ini akan menunjukkan kondisi tersebut.

int isEmpty ( QUEUENODEPTR headPtr ) { return headPtr == NULL;