DIG1G3 Implementasi Struktur Data Program Studi Diploma III Teknik Informatika Fakultas Ilmu Terapan Telkom University Dosen: Cahyana, S.T., M.Kom. Indra Azimi, S.T., M.T.
2
Stack (Tumpukan) • Stack is a list-like structure in which elements may be inserted or removed from only one end ▫ The “Top”
3
Definisi Stack The elements at the bottom of the stack have been in the stack the longest. The top element of the stack is the last element added to the stack TOP
BOTTOM
4
Aplikasi Stack • Implement function calls Suppose that you have a program with several functions. To be specific, suppose that you have the functions A, B, C, and D in your program. Now suppose that function A calls function B, function B calls function C, and function C calls function D. When function D terminates, control goes back to function C; when function C terminates, control goes back to function B; and when function B terminates, control goes back to function A. During program execution, how do you think the computer keeps track of the function calls?
5
Stack Operations Stack is a LIFO (Last In First Out) data structure Stack operations: Push (insert element) Pop (remove/ delete) initializeStack isEmptyStack isFullStack Top (returns the top element of the stack)
6
Representasi Stack • Array based ▫ Declare an array of fixed size (which determines the maximum size of the stack) ▫ Keep a variable which always points to the “top” of the stack. Contains the array index of the “top” element.
• Linked list ▫ Maintain the stack as a linked list. ▫ A pointer variable top points to the start of the list. ▫ The first element of the linked list is considered as the stack top.
7
Array-based Stack • Stack dibuat dengan array dan top sebagai penanda #define MAXSIZE 100
void create (stack *s){ s->top = -1; } //Inisialisasi awal, top = -1
typedef struct lifo { int st[MAXSIZE]; int top; }stack;
Elemen baru akan masuk lewat top
8
Push Element • Simpan elemen baru ke dalam array yang diindikasikan oleh top • Increment top
y masuk top
top
9
Push Element • Karena menggunakan array, ada kemungkinan stack penuh top = indeks array terakhir ▫ Stack overflow void push (stack *s, int element){ if (s->top == (MAXSIZE-1)) cout<<“Stack overflow”<<endln; else{ s->top ++; s->st[s->top] = element; } }
10
Popped Element • Jika sudah kosong tetap di-pop? ▫ Stack underflow ▫ Top = -1 int pop (stack *s){ if (s->top == -1) cout<<“Stack underflow”<<endln; else{ return (s->st[s->top]); s->top--; } }
11
Linked List Stack • Representasi Stack secara lojik digambarkan sebagai list linier (singly linked list) • Alamat elemen terbaru (TOP) dan alamat elemen terlama (BOTTOM) juga dicatat. Namun dalam implementasi belum tentu BOTTOM digunakan.
12
Traversal Pada Stack • Pada stack jarang sekali dilakukan operasi traversal, karena keunikan stack justru pada operasi yang hanya menyangkut elemen TOP. • Namun jika memang dibutuhkan traversal, misalnya untuk mencetak isi stack, maka skema traversal suatu stack persis sama dengan skema traversal list linier biasa, dengan TOP bertindak sebagai head.
13
Operasi dan Fungsi dasar (Primitif) Pada Stack • StackEmpty :S boolean {Test stack kosong, true jika kosong, false jika tidak} • CreateStack: S {Membuat sebuah stack kosong} • Push : Elmt x S S {Menambahkan sebuah ElmtS sebagai TOP. TOP berubah nilainya} • Pop : S S x ElmtS {Mengambil nilai elemen TOP, sehingga Top yang baru adalah elemen yang datang sebelum elemen TOP, mungkin Stack menjadi kosong}
14
Linked List Stack
15
Create Stack typedef struct lifo { int info; struct lifo *next; } stack; stack *top;
Top menandai ujung stack (seperti head)
void create (stack *top){ top = NULL; /* top points to NULL, indicating empty stack */ }
16
Operasi pada Stack • Karena pada dasarnya stack merupakan suatu singly linked list yang hanya boleh di-insert dan delete dari satu ujung, maka: ▫ Untuk push, metode insert apa yang digunakan? ▫ Untuk pop, metode delete apa yang digunakan? ▫ Bagaimana cara mengambil nilai elemen pada TOP?
17
Reference • Clifford A. Shaffer, Data Structures and Algorithm Analysis, Edition 3.2 (C++ Version), Department of Computer Science, Virginia Tech. 2012 • Slide PI1043 Struktur Data,Stack, IT Telkom • DS Malik, Data Structures Using C++, 2nd Edition • Slide Programming and Data Structure , Linked List, 2009
