Struktur Data
Pertemuan 4
Stack
Disampaikan untuk Proses Belajar Mengajar untuk Mata Kuliah Pemrograman Web
Teknik Informatika Institut Teknologi Nasional Malang
Dosen Pengampu :
1. Yosep Agus Pranoto, S.T., M.T.
2. Dr. Agung panji Sasmito,[Link].,[Link].
3. Nurlaily Vendyansyah, S.T.,M.T.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
Stack
Stack adalah tipe data abstrak yang umum digunakan pada seluruh
pemrograman komputer.
Stack adalah struktur data linier yang mengikuti urutan tertentu di
mana operasi dilakukan.
Penyisipan dan penghapusan item pada stack terjadi di satu ujung
yang disebut bagian atas tumpukan.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 2
Ilustrasi Stack (cont’d)
Konsep dasar dapat diilustrasikan
dengan memikirkan set data Anda
sebagai tumpukan (stack) piring
yang telah selesai dicuci, akan
ditumpuk dari bawah ke atas (LIFO:
Last In First Out) atau (FILO : First
In Last Out), kemudian setelah
semua bersih maka diambil satu
persatu dari atas ke bawah untuk di
masukkan ke lemari atau rak piring.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 3
Implementasi (cont’d)
1) Penerapatan Queue menggunakan Stack
2) Desain dan Implementasikan Struktur Data Stack Khusus | Menambahkan Versi Optimasi
Ruang
3) Implementasi dua stack pada array
4) Implement Stack using Queues
5) Design a stack with operations on middle element
6) How to efficiently implement k stacks in a single array?
7) How to create mergable stack?
8) Design a stack that supports getMin() in O(1) time and O(1) extra space
9) Implement a stack using single queue
10) How to implement stack using priority queue or heap?
11) Create a customized data structure which evaluates functions in O(1)
12) Implement Stack and Queue using Deque
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 4
Operasi pada Stack
Operasi utama pada stack yaitu push untuk menambahkan data ke
dalam stack dan pop untuk mengeluarkan atau menghapus data dari
stack.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 5
Operasi pada Stack
1. Push : digunakan untuk menembah item pada Stack pada Tumpukan
paling atas.
2. Pop : digunakan untuk mengambil item pada Stack pada Tumpukan
paling atas.
3. Clear : digunakan untuk mengosongkan Stack.
4. Create Stack : membuat Tumpukan baru S, dengan jumlah elemen
kosong.
5. IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah
kosong.
6. Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah
penuh.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 6
Operasi pada Stack (cont’d)
1. Menambahkan Data ke Stack
Proses penambahan data ke dalam stack disebut operasi Push.
Langkah - langkah operasi push diantaranya.
Memeriksa apakah tumpukan(stack) penuh
Jika tumpukan penuh, maka sudah tidak ada ruang untuk memasukkan data ke tumpukan, jadi cukup
tampilkan pesan bahwa tumpukan sudah penuh.
Jika masih ada ruang, tambahkan satu nilai pada atas(top) tumpukan untuk menunjukkan ke ruang kosong
selanjutnya
Menambahkan data dimana ruang kosong yang telah ditunjuk oleh top.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 7
Operasi pada Stack (cont’d)
2. Menghapus Data dari Stack
Mengambil data bersamaan dengan menghapus data dari stack disebut dengan
operasi Pop.
Langkah - langkah operasi Pop diantaranya.
Memeriksa apakah tumpukan kosong.
Jika tumpukan kosong, maka sudah tidak ada lagi data untuk dihapus, maka cukup
tampilkan pesan bahwa tumpukan kosong.
Jika masih ada data pada tumpukan, maka akses data yang paling atas (top)
kemudian mengurangi nilai penunjuk top.
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 8
Kode Program Stack (cont’d)
1. Preprocessor dan Headerfile
#include <iostream>
#define MAX 3
using namespace std;
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 9
Kode Program Stack (cont’d)
2. Struct Data
//Deklarasi struct tumpukan
struct Stack {
int top, data[MAX];
}Tumpukan;
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 10
Kode Program Stack (cont’d)
3. Inisialisasi Nilai Top
void init(){
[Link] = -1;
}
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 11
Kode Program Stack (cont’d)
4. Memeriksa Tumpukan
Kedua fungsi ini akan digunakan untuk memeriksa bool isEmpty() {
apakah tumpukan penuh isFull() (fungsi pertama) dan return [Link] == -1;
tumpukan kosong isEmpty(), keduanya mengembalikan }
nilai boolean, jadi kita cukup mengembalikan nilai
perbandingan pada fungsi masing - masing.
bool isFull() {
Pada fungsi isEmpty() akan mengembalikan nilai true return [Link] ==
jika nilai [Link] sama dengan -1, atau false jika MAX-1;
tidak sama. }
Pada fungsi isFull() akan mengembalikan nilai true jika
nilai [Link] sama dengan maksimum data array
yang telah ditentukan dikurang satu MAX-1, atau false
jika tidak sama.
[Link]@[Link] 12
Kode Program Stack (cont’d)
void push() {
5. Menambahkan Data ke Tumpukan if (isFull()) {
cout << "\nTumpukan
Untuk menginputkan data ke tumpukan hal utama yang penuh"<<endl;
perlu kita lakukan adalah memeriksa apakah tumpukan
penuh atau tidak, jika penuh, maka kita tidak dapat }
menambahkan data ke tumpukan karena sudah tidak ada else {
ruang lagi yang tersedia. Jadi cukup tampilkan pesan [Link]++;
bahwa Tumpukannya penuh. cout << "\nMasukkan data = ";
Jika masih ada ruang maka tambahkan nilai cin >>
[Link] dengan 1. Kemudian masukkan data ke [Link][[Link]];
ruang yang ditunjukkan oleh top. cout << "Data " <<
[Link][[Link]] << "
masuk ke stack"<<endl;
}
Teknik Informatika S1 }
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 13
Kode Program Stack (cont’d)
void pop() {
6. Mengambil Data dari Tumpukan if (isEmpty()) {
cout << "\nData
Sebelum mengambil data, kita perlu memeriksa apakah kosong\n"<<endl;
tumpukan kosong atau tidak, karena kita tidak dapat
mengambil data yang tidak ada pada tumpukan. }
else {
Jika tumpukan kosong maka cukup tampilkan pesan cout << "\nData
bahwa tidak ada data di tumpukan tersebut. "<<[Link][[Link]]<<"
Jika masih ada data pad tumpukan maka Tampilkan data sudah terambil"<<endl;
dengan mengambil data teratas dari tumpukkan dan [Link]--;
menghapus data tersebut dengan mengurangi nilai top.. }
}
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 14
Kode Program Stack (cont’d)
void printStack() {
7. Menampilkan Data pada Tumpukan if (isEmpty()) {
cout << "Tumpukan
Sama halnya pada saat mengambil data dari tumpukan, kosong";
kita juga perlu memeriksa apakah tumpukan tersebut
kosong atau tidak. }
else {
Jika tidak ada data di tumpukan maka tampilkan pesan cout << "\nTumpukan : ";
bahwa Tumpukan kosong dan data tidak dapat di for (int i =
tampilkan.
[Link]; i >= 0; i--)
Jika masih ada data maka tampilkan data satu -persatu cout <<
dari tumpukan dengan menggunakan perulangan. [Link][i] << ((i == 0) ?
"" : ",");
}
}
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 15
Kode Program Stack (cont’d)
8. Menampilkan Menu case 1:
push();
int main() { break;
int pilihan; case 2:
init(); pop();
do { break;
printStack(); default:
cout << "\n1. Input (Push)\n" cout << "Pilihan tidak
<<"2. Hapus (Pop)\n" tersedia" << endl;
<<"3. Keluar\n"
break;
<<"Masukkan Pilihan: ";
cin >> pilihan; }
switch (pilihan) } while (pilihan!=3);
{ }
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 16
#include <iostream> int penuh(Stack *s)
#define MAXSTACK 2 {
using namespace std; return (s->jml==MAXSTACK);
}
typedef int itemType;
typedef struct void isi(itemType x, Stack *s)
{ {
int item[MAXSTACK]; if(penuh(s))
int jml; {
} Stack; cout<<" Maaf data sudah penuh"<<endl;
cout<<"--------------------------"<<endl;
void init(Stack *s) }
{ else
s->jml=0; {
}; s->item[s->jml]=x;
++(s->jml);
int kosong(Stack *s) }
{ }
return (s->jml==0);
}
void ambil(Stack *s, itemType *x)
{
if(kosong(s))
{
cout<<" Maaf data masih kosong"<<endl;
cout<<"--------------------------------------------------"<<endl;
}
else
{
--(s->jml);
*x=s->item[s->jml];
s->item[s->jml]=0;
cout<<" Data "<<*x<<" berhasil diambil"<<endl;
cout<<"--------------------------------------------------"<<endl;
}
}
void tampil(Stack *s)
{
if(kosong(s))
{
cout<<" Maaf data masih kosong"<<endl;
cout<<"--------------------------------------------------"<<endl;
}
else cout<<endl;
for(int i=s->jml-1;i>=0;i--)
{
cout<<"Data "<<s->item[i]<<endl;
}
}
void hapus(Stack *s)
{
s->jml=0;
cout<<" Semua data berhasil dihapus"<<endl;
cout<<"--------------------------------------------------"<<endl;
}
int main()
{
int pil;
Stack tumpukan;
itemType data;
init(&tumpukan);
do
{
cout<<"Selamat datang di Aplikasi stack"<<endl;
cout<<"1. PUSH(Memasukan)"<<endl;
cout<<"2. POP(Mengangkat/Memanggil)"<<endl;
cout<<"3. Display(Menampilkan)"<<endl;
cout<<"4. Delete(Hapus)"<<endl;
cout<<"5. Exit"<<endl;
cout<<"Masukkan pilihan : ";cin>>pil;
cout<<"--------------------------------------------------"<<endl;
switch(pil)
{
case 1:
cout<<"Masukkan data : ";cin>>data;
cout<<"--------------------------------------------------"<<endl;
isi(data,&tumpukan);
break;
case 2:
ambil(&tumpukan,&data);
break;
case 3:
tampil(&tumpukan);
break;
case 4:
hapus(&tumpukan);
break;
}
}
while(pil!=5);
cout<<" Terima Kasih"<<endl;
cout<<"--------------------------------------------------"<<endl;
return 0;
}
Teknik Informatika S1
Fakultas Teknologi Industri
Institut Teknologi Nasional Malang
[Link]@[Link] 22