Struktur Data dan Algoritma - Stack

Tumpukan adalah Tipe Data Abstrak (ADT), yang umum digunakan di sebagian besar bahasa pemrograman. Dinamai tumpukan karena berperilaku seperti tumpukan dunia nyata, misalnya - setumpuk kartu atau tumpukan piring, dll.

Tumpukan dunia nyata memungkinkan operasi di satu ujung saja. Misalnya, kita dapat menempatkan atau mengeluarkan kartu atau piring hanya dari atas tumpukan. Demikian pula, Stack ADT memungkinkan semua operasi data di satu ujung saja. Pada waktu tertentu, kami hanya dapat mengakses elemen teratas tumpukan.

Fitur ini membuatnya menjadi struktur data LIFO. LIFO adalah singkatan dari Last-in-first-out. Di sini elemen yang ditempatkan (disisipkan atau ditambahkan) terakhir, diakses terlebih dahulu. Dalam terminologi stack, operasi penyisipan disebutPUSH operasi operasi dan pemindahan disebut POP operasi.

Representasi Stack

Diagram berikut menggambarkan tumpukan dan operasinya -

Tumpukan dapat diimplementasikan melalui Array, Structure, Pointer, dan Linked List. Tumpukan dapat berupa ukuran tetap atau mungkin memiliki kesan perubahan ukuran dinamis. Di sini, kita akan mengimplementasikan stack menggunakan array, yang menjadikannya implementasi stack dengan ukuran tetap.

Operasi Dasar

Operasi tumpukan mungkin melibatkan menginisialisasi tumpukan, menggunakannya dan kemudian membatalkan inisialisasi. Terlepas dari hal-hal dasar ini, tumpukan digunakan untuk dua operasi utama berikut -

push() - Mendorong (menyimpan) elemen di stack.
pop() - Menghapus (mengakses) elemen dari stack.

Saat data DITOLAK ke stack.

Untuk menggunakan tumpukan secara efisien, kita perlu memeriksa status tumpukan juga. Untuk tujuan yang sama, fungsi berikut ditambahkan ke tumpukan -

peek() - dapatkan elemen data teratas dari tumpukan, tanpa menghapusnya.
isFull() - periksa apakah tumpukan sudah penuh.
isEmpty() - periksa apakah tumpukan kosong.

Setiap saat, kami mempertahankan penunjuk ke data PUSHed terakhir di tumpukan. Karena penunjuk ini selalu mewakili bagian atas tumpukan, maka dinamaitop. Itutop pointer memberikan nilai teratas dari tumpukan tanpa benar-benar menghapusnya.

Pertama kita harus belajar tentang prosedur untuk mendukung fungsi stack -

mengintip()

Algoritma peek () fungsi -

begin procedure peek
   return stack[top]
end procedure

Implementasi fungsi peek () dalam bahasa pemrograman C -

Example

int peek() {
   return stack[top];
}

penuh()

Algoritma dari fungsi isfull () -

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementasi fungsi isfull () dalam bahasa pemrograman C -

Example

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

kosong()

Algoritma fungsi isempty () -

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

Implementasi fungsi isempty () dalam bahasa pemrograman C sedikit berbeda. Kami menginisialisasi top di -1, karena indeks dalam array dimulai dari 0. Jadi kami memeriksa apakah top di bawah nol atau -1 untuk menentukan apakah stack kosong. Ini kodenya -

Example

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

Operasi Dorong

Proses menempatkan elemen data baru ke dalam tumpukan dikenal sebagai Operasi Dorong. Operasi dorong melibatkan serangkaian langkah -

Step 1 - Memeriksa apakah tumpukan sudah penuh.
Step 2 - Jika tumpukan penuh, menghasilkan kesalahan dan keluar.
Step 3 - Jika tumpukan tidak penuh, tambahkan top untuk menunjukkan ruang kosong berikutnya.
Step 4 - Menambahkan elemen data ke lokasi tumpukan, di mana bagian atas mengarah.
Step 5 - Mengembalikan kesuksesan.

Jika daftar tertaut digunakan untuk mengimplementasikan tumpukan, maka pada langkah 3, kita perlu mengalokasikan ruang secara dinamis.

Algoritma untuk Operasi PUSH

Algoritma sederhana untuk operasi Push dapat diturunkan sebagai berikut -

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

Implementasi algoritma ini di C, sangat mudah. Lihat kode berikut -

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Operasi Pop

Mengakses konten sambil menghapusnya dari tumpukan, dikenal sebagai Operasi Pop. Dalam implementasi array dari operasi pop (), elemen data sebenarnya tidak dihapustopditurunkan ke posisi yang lebih rendah dalam tumpukan untuk menunjuk ke nilai berikutnya. Tapi dalam implementasi linked-list, pop () sebenarnya menghapus elemen data dan membatalkan alokasi ruang memori.

Operasi Pop mungkin melibatkan langkah-langkah berikut -

Step 1 - Memeriksa apakah tumpukan kosong.
Step 2 - Jika tumpukan kosong, menghasilkan kesalahan dan keluar.
Step 3 - Jika tumpukan tidak kosong, mengakses elemen data di mana top menunjuk.
Step 4 - Mengurangi nilai teratas sebanyak 1.
Step 5 - Mengembalikan kesuksesan.

Algoritma untuk Operasi Pop

Algoritme sederhana untuk operasi Pop dapat diturunkan sebagai berikut -

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

Implementasi algoritma ini di C, adalah sebagai berikut -

Example

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

Untuk program stack lengkap dalam bahasa pemrograman C, silakan klik di sini .