PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA
BAB. 5 STACK
5.1. Definisi Stack
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang
terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.
Ada dua cara penerapan prinsip stack, yakni dengan array dan linked list. Setidaknya stack haruslah memiliki
operasi-operasi sebagai berikut.
• Push Untuk menambahkan item pada tumpukan paling atas
• Pop Untuk mengambil item teratas
• Clear Untuk mengosongkan stack
• IsEmpty Untuk memeriksa apakah stack kosong
• IsFull Untuk memeriksa apakah stack sudah penuh
• Retreive Untuk mendapatkan nilai dari item teratas
5.2. Stack dengan Array
Sesuai dengan sifat stack, pengambilan / penghapusan di elemen dalam stack harus dimulai dari elemen
teratas. Operasi-operasi pada Stack dengan Array.
Ø IsFull Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika puncak stack terdapat tepat
di bawah jumlah maksimum yang dapat ditampung stack atau dengan kata lain Top = MAX_STACK -1.
Ø Push Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bisa dilakukan lagi jika stack sudah
penuh.
Ø IsEmpty Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack kosong adalah Top bernilai
kurang dari nol.
Ø Pop Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh kosong.
Ø Clear Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika Top bernilai kurang dari nol
maka stack dianggap kosong.
Ø Retreive Fungsi ini untuk melihat nilai yang berada pada posisi tumpukan teratas
Contoh Program :
Program untuk Insert (Push) Nilai dan Delete (Pop) Nilai dalam Stack
Contoh Program 19
1. #include <iostream> 16. do
2. #include <stdio.h> 17. {
3. #include <stdlib.h> 18. cout<<"Masukkan Nilai yang akan di Push :";
4. #define MAX 3 19. cin>>value;
5. using namespace std; 20. push(stack,&top,value);
6. 21. cout<<"Tekan 1 untuk melanjutkan Push, 2 unt
7. void push(int stack[],int *top,int value); uk Pop"<<endl;
8. void pop(int stack[],int *top,int *value); 22. cin>>n;
9. int main() 23. } while (n == 1);
10. { 24. cout<<"Tekan 2 untuk Melakukan Pop"<<endl;
11. int stack[MAX]; 25. cin>>n;
12. int top = -1; 26. while (n == 2)
13. int n, value; 27. {
14. do 28. pop(stack,&top,&value);
15. { 29. cout<<"Nilai yang di Pop :"<<value<<endl;
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 20
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA
30. cout<<"Tekan 2 untuk Pop sebuah Elemen, 1 un 48. exit(0);
tuk push"<<endl; 49. }
31. cin>>n; 50. }
32. } 51.
33. cout<<endl; 52. void pop(int stack[],int *top,int *value)//f
34. cout<<"Tekan 1 untuk Melanjutkan"<<endl; ungsi untuk insert nilai
35. cin>>n; 53. {
36. }while (n == 1); 54. if(*top >= 0)
37. } 55. {
38. void push(int stack[], int *top, int value)/ 56. *value = stack[*top];
/fungsi untuk insert nilai 57. *top = *top - 1;
39. { 58. }
40. if(*top < MAX) 59. else
41. { 60. {
42. *top = *top + 1; 61. cout<<"Stack Kosong, Pop Tidak dapat dilakuk
43. stack[*top] = value; an!"<<endl;
44. } 62. exit(0);
45. else 63. }
46. { 64. }
47. cout<<"Stack Penuh, Push nilai tidak dapat d
ilakukan"<<endl;
65.
Hasil output programnya adalah :
Masukkan Nilai yang akan di Push :23 Tekan 2 untuk Pop sebuah Elemen, 1 untuk
Tekan 1 untuk melanjutkan Push, 2 untuk Pop push
1 2
Masukkan Nilai yang akan di Push :45 Nilai yang di Pop :45
Tekan 1 untuk melanjutkan Push, 2 untuk Pop Tekan 2 untuk Pop sebuah Elemen, 1 untuk
1 push
Masukkan Nilai yang akan di Push :67 2
Tekan 1 untuk melanjutkan Push, 2 untuk Pop Nilai yang di Pop :23
2 Tekan 2 untuk Pop sebuah Elemen, 1 untuk
Tekan 2 untuk Melakukan Pop push
2 2
Nilai yang di Pop :67 Stack Kosong, Pop Tidak dapat dilakuk
Contoh program Stack dengan array :
Contoh Program 20
1. #include<iostream> 25. }
2. #include<stdio.h> 26. else
3. using namespace std; 27. return p->elemen[p->top--];
4. #define size 50 28. }
5. 29. //menampilkan stack
6. struct stack { 30. void display (STACK *p) {
7. int elemen[size]; 31. int i;
8. int top; 32. if(p->top==-1)
9. }; 33. cout<<"\n STACK kosong\n";
10. typedef struct stack STACK; 34. else
11. 35. cout<<"\nIsi STACK adalah : \n";
12. // operasi push 36. for (i=p->top;i>=0; --i)
13. void push(STACK *p,int value){ 37. cout<<p->elemen[i]<<"\n";
14. if(p->top==size-1) 38. }
15. cout<<"STACK penuh "; 39.
16. else 40. int main() {
17. p->elemen[++p->top]=value; 41. STACK s ;
18. } 42. int x,c,i;
19. //operasi pop 43. [Link]=-1;
20. int pop(STACK *p) { 44. do
21. if (p->top==-1) 45. {
22. { 46. cout<<"MENU PILIHAN";
23. cout<<"STACK kosong"; 47. cout<<"\n1: Operasi PUSH\n";
24. return -1; 48. cout<<"2: Operasi POP\n";
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 21
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA
49. cout<<"3: Tampilkan Stack\n"; 64. case 4:
50. cout<<"4: Hapus Stasck\n"; 65. if([Link]==-1)
51. cout<<"5: Keluar\n"; 66. cout<<endl<<"STACK kosong";
52. cout<<"\n\n Pilihan anda : ";cin>>c; 67. else
53. switch(c) { 68. cout<<endl<<"STACK dihapus"<<endl;
54. case 1: cout<<"\nMasukkan Elemen Stack: 69. //Menghapus STACK
";cin>>x; 70. for (i=[Link];i>=0; --i)
55. push (&s,x); 71. cout<<"Elemen yang dihapus adalah : "<<
56. display(&s); pop(&s)<<endl;
57. break; 72. [Link]=-1;
58. case 2: x=pop(&s); 73. }
59. if(x!=-1) 74. getc;
60. cout<<"\nMenghapus Element = "<<x; 75. system("clear");
61. break; 76. }
62. case 3: display(&s); 77. while(c!=5);
63. break; 78. }
79.
Hasil output programnya adalah :
MENU PILIHAN Isi STACK adalah :
1: Operasi PUSH 45
2: Operasi POP 23
3: Tampilkan Stack MENU PILIHAN
4: Hapus Stasck 1: Operasi PUSH
5: Keluar 2: Operasi POP
Pilihan anda : 1 3: Tampilkan Stack
4: Hapus Stasck
Masukkan Elemen Stack: 23 5: Keluar
Pilihan anda : 3
Isi STACK adalah :
23 Isi STACK adalah :
MENU PILIHAN 45
1: Operasi PUSH 23
2: Operasi POP MENU PILIHAN
3: Tampilkan Stack 1: Operasi PUSH
4: Hapus Stasck 2: Operasi POP
5: Keluar 3: Tampilkan Stack
Pilihan anda : 1 4: Hapus Stasck
5: Keluar
Masukkan Elemen Stack: 45 Pilihan anda :
5.3. Stack dengan Single Linked List
Operasi-operasi untuk Stack dengan Linked List :
IsEmpty Fungsi memeriksa apakah stack yang adamasih kosong.
Push Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked
list biasa.
Pop Fungsi ini mengeluarkan elemen teratas dari stack
Program Stack dengan link list :
Contoh Program 21
1. #include <iostream> 10. class stack
2. using namespace std; 11. {
3. // Creating a NODE Structure 12. struct node *top;
4. struct node 13. public:
5. { 14. stack() // constructor
6. int data; 15. {
7. struct node *next; 16. top=NULL;
8. }; 17. }
9. // Creating a class STACK 18. void push(); // to insert an element
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 22
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA
19. void pop(); // to delete an element 58. cout<<ptr1->data<<" ->";
20. void show(); // to show the stack 59. ptr1=ptr1->next;
21. }; 60. }
22. // PUSH Operation 61. cout<<"NULL\n";
23. void stack::push() 62. }
24. { 63. // Main function
25. int value; 64. int main()
26. struct node *ptr; 65. {
27. cout<<"\nPUSH Operationn"; 66. stack s;
28. cout<<"Enter a number to insert: "; 67. int choice;
29. cin>>value; 68. while(1)
30. ptr=new node; 69. {
31. ptr->data=value; 70. cout<<"\n-----------------------------------
32. ptr->next=NULL; ";
33. if(top!=NULL) 71. cout<<"\n\t\tSTACK USING LINKED LIST\n\n";
34. ptr->next=top; 72. cout<<"1:PUSH\n2:POP\n3:DISPLAY STACK\n4:EXI
35. top=ptr; T";
36. cout<<"\nNew item is inserted to the stack!! 73. cout<<"\nEnter your choice(1-4): ";
!"; 74. cin>>choice;
37. } 75. switch(choice)
38. // POP Operation 76. {
39. void stack::pop() 77. case 1:
40. { 78. [Link]();
41. struct node *temp; 79. break;
42. if(top==NULL) 80. case 2:
43. { 81. [Link]();
44. cout<<"\nThe stack is empty!!!"; 82. break;
45. } 83. case 3:
46. temp=top; 84. [Link]();
47. top=top->next; 85. break;
48. cout<<"\nPOP Operation.\nPoped value is "<<t 86. case 4:
emp->data; 87. return 0;
49. delete temp; 88. break;
50. } 89. default:
51. // Show stack 90. cout<<"\nPlease enter correct choice(1-
52. void stack::show() 4)!!";
53. { 91. break;
54. struct node *ptr1=top; 92. }
55. cout<<"\nThe stack is\n"; 93. }
56. while(ptr1!=NULL) 94. return 0;
57. { 95. }
Hasil output programnya adalah :
------------------------------------------- 3:DISPLAY STACK
STACK USING LINKED LIST 4:EXIT
1:PUSH Enter your choice(1-4): 1
2:POP PUSH OperationnEnter a number to insert: 67
3:DISPLAY STACK New item is inserted to the stack!!!
4:EXIT -------------------------------------------
Enter your choice(1-4): 1 STACK USING LINKED LIST
PUSH OperationnEnter a number to insert: 23 1:PUSH
New item is inserted to the stack!!! 2:POP
------------------------------------------- 3:DISPLAY STACK
STACK USING LINKED LIST 4:EXIT
1:PUSH Enter your choice(1-4): 3
2:POP The stack is
3:DISPLAY STACK 67 ->45 ->23 ->NULL
4:EXIT -------------------------------------------
Enter your choice(1-4): 1 STACK USING LINKED LIST
PUSH OperationnEnter a number to insert: 45 1:PUSH
New item is inserted to the stack!!! 2:POP
------------------------------------------- 3:DISPLAY STACK
STACK USING LINKED LIST 4:EXIT
1:PUSH Enter your choice(1-4):
2:POP
PEMROGRAMAN C++ : ALGORITMA & STRUKTUR DATA TEKINIK INFORMATIKA 23