Stack
STRUKTUR DATA JULIO ADISANTOSO Departemen Ilmu Komputer IPB
Pertemuan 5 : 6 Juli 2015
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
STACK
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Beberapa pengertian Stack pada Struktur Data: tumpukan dari objek sekumpulan data yang seolah-olah diletakkan di atas data yang lain urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja.
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Sifat Stack LIFO : Last In First Out Objek yang terakhir masuk ke dalam Stack akan menjadi yang pertama keluar dari Stack Beberapa contoh penggunaan Stack: Membalik urutan Pemanggilan fungsi rekursif Beberapa algoritme Search, misal DFS
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Operasi dasar Stack ⇒ Spesifikasi PRIMITIF push(objek) : menambah objek ke dalam Stack pop() : menghapus objek paling atas top() : akses objek paling atas empty() : memeriksa Stack kosong size() : ukuran stack full() : memeriksa Stack penuh (in array)
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Implementasi Stack Stack dapat diimplementasikan dengan menggunakan tipe data apa pun, asalkan memenuhi sifat dan kaidah Stack, yaitu LIFO. Contoh implementasi: Array Linked List
Tiap implementasi memiliki plus dan minus. Apa saja?
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan Array (p05a.cpp) #include
#define SIZE 100 using namespace std; class Stack { int stack[SIZE]; int atas; public: Stack() { atas=SIZE; } bool empty() { return atas==SIZE; } bool full() { return atas==0; } void push(int value); void pop(); int top(); int size() { return SIZE-atas; } int getAtas() {return atas;} int *getStack() {return stack;} }; JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan Array Contoh Driver int main() { Stack st; st.push(50); st.push(15); st.push(20); cout << "Stack Awal\n"; cout << st; int nilai=st.top(); st.pop(); cout << "\nHasil pop(): " << nilai << endl; cout << "\nStack Akhir\n"; cout << st; return 0; }
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan Array Fungsi push(value) void Stack::push(int value) { if (full()) cout << "Stack is full\n"; else stack[--atas]=value; } Fungsi pop() void Stack::pop() { if (empty()) cout << "Stack is empty\n"; else ++atas; } Fungsi pop() tidak mengambil nilai dari Stack, tetapi hanya membuang nilai paling atas dari Stack. JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan Array Fungsi top() hanya meng-copy nilai paling atas dari Stack. Fungsi top() int Stack::top() { if (empty()) { cout << "Stack is empty\n"; return 0; } else return stack[atas]; }
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan Array Dalam driver terdapat pernyataan cout<<st; yang menimbulkan error. Kenapa? Oleh karena itu harus dibuat fungsi yang meng-overload operator <<. Fungsi operator<< ostream& operator<< (ostream &out, Stack s) { if (s.empty()) out << "Stack is empty\n"; else for (int i=s.getAtas(); i<s.getAtas()+s.size(); ++i) out << s.getStack()[i] << endl; return out; }
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan DLL (p05b.cpp) #include #include <list> using namespace std; class Stack { list stack; list::iterator atas; public: Stack() { atas=stack.begin(); } bool empty() { return (atas==stack.end()); } int size() { return stack.size(); } void push(int nilai); void pop(); int top(); list::iterator getAtas() {return atas;} list getStack() {return stack;} }; JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan DLL Fungsi push(value) void Stack::push(int value) { stack.push_front(value); atas=stack.begin(); } Fungsi pop() void Stack::pop() { if (empty()) cout << "Stack is empty\n"; else {++atas; stack.pop_front();} } Fungsi pop() tidak mengambil nilai dari Stack, tetapi hanya membuang nilai paling atas dari Stack. JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan DLL Fungsi top() int Stack::top() { return (*atas); } Fungsi operator<< ostream& operator<< (ostream &out, Stack s) { if (s.empty()) out << "Stack is empty\n"; else { list::iterator it=s.getAtas(); for (int i=0; i<s.size(); ++it, ++i) out << (*it) << endl; } return out; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Stack Menggunakan STL Stack Spesifikasi TYPE #include <stack> typedef stack Stack; Fungsi operator<< ostream& operator<< (ostream &out, Stack s) { if (s.empty()) out << "Stack is empty\n"; else { while(!(s.empty())) { int t = s.top(); out << t << endl; s.pop(); } } return out; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Latihan Buat program mengevaluasi eksresi postfix seperti contoh Asumsikan bahwa ekspresi input selalu valid. Contoh Input 45+3-2* Contoh Output 12
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Latihan Algoritme: begin foreach ch ∈ string do if ch is number then push(ch) end else Ambil dua node teratas Lakukan operasi yang sesuai Masukkan ke stack end end return (NilaiStack) end JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Latihan Spesifikasi Type #include #include #include <string> #include #include <stack> using namespace std;
JULIO ADISANTOSO Departemen Ilmu Komputer IPB
STRUKTUR DATA
Stack
Pengertian Implementasi
Latihan Program Utama int main() { stack st; string str; getline(cin, str); for (int i=0; i<str.size(); i++) { char ch=str.at(i); if (isdigit(ch)) { int t = (int)ch-48; st.push(t); } else { // ambil 2 node dan lakukan operasi // simpan hasilnya ke stack } } cout << st.top() << endl; return 0; } JULIO ADISANTOSO Departemen Ilmu Komputer IPB STRUKTUR DATA
