Stack

Terminologi

• Top - node paling atas dalam stack.
• LIFO - last in first out.

Definisi

Stack adalah struktur data dinamis yang mengikuti prinsip LIFO. Pada stack, elemen yang terakhir masuk ke dalam stack adalah elemen pertama yang dapat dihapus. Contoh implementasi stack dalam kehidupan sehari-hari adalah tumpukan kursi.

Aplikasi Stack

Salah satu contoh penerapan dari stack adalah mengubah notasi infix menjadi postfix. Notasi infix adalah notasi matematika yang biasa dibaca dan dapat diselesaikan oleh manusia, contoh A + B. Sedangkan notasi postfix adalah notasi matematika yang dapat dibaca dan diselesaikan oleh komputer, contoh A B +. Untuk mengubah notasi infix menjadi postfix salah satunya yaitu dengan cara menggunakan konsep stack. Contoh mengubah notasi infix (A + B) * C - D secara bertahap:

• Stack: (, Hasil:
  (Setiap bertemu operator "(", masukkan saja langsung ke dalam stack).
• Stack: (, Hasil: A
  (Setiap operand, masukkan ke dalam hasil).
• Stack: ( +, Hasil: A
  (Untuk operator "+", masukkan ke dalam stack, karena top dari stack adalah operator "(").
• Stack: ( +, Hasil: A B
  (Setiap operand, masukkan ke dalam hasil).
• Stack: , Hasil: A B +
  (Untuk operator ")", keluarkan semua isi stack hingga bertemu "(").
• Stack: *, Hasil: A B +
  (Untuk operator "*", masukkan ke dalam stack).
• Stack: *, Hasil: A B + C
  (Setiap operand, masukkan ke dalam hasil).
• Stack: -, Hasil: A B + C *
  (Karena yang ingin diproses adalah operator, sedangkan di dalam stack terdapat operator lain, maka harus dilakukan perbandingan. Apabila operator yang ingin masuk derajatnya lebih besar dibandingkan top stack, maka masukkan ke dalam stack. Apabila sebaliknya, maka keluarkan top stack dan bandingkan kembali. Sehingga, operator "*" dikeluarkan dan operator "-" masuk ke dalam stack).
• Stack: -, Hasil: A B + C * D
  (Setiap operand, masukkan ke dalam hasil).
• Stack: , Hasil: A B + C * D -
  (Keluarkan semua isi stack apabila tidak ada lagi yang ingin diproses).

Implementasi ADT Stack (Linked List Based)

Kode Lengkap Dapat Dilihat Disini

Implentasi stack dapat dilakukan dengan menggunakan Singly Linked List dengan mengubah head pada Singly Linked List menjadi Top.

Kompleksitas waktu semua operasi pada stack dilakukan secara konstan O(1).

• Representasi Node

  Setiap node pada stack dapat direpresentasikan oleh sebuah struct StackNode yang menyimpan tipe data int dan referensi pada node selanjutnya menggunakan pointer struct StackNode inu sendiri.

  typedef struct stackNode_t {
    int data;
    struct stackNode_t *next;
  } StackNode;
  

• Struktur Stack

  Keseluruhan stack dapat direpresentasikan oleh sebuah struct Stack yang menyimpan referensi node yang berada pada top menggunakan pointer struct StackNode serta jumlah elemen yang berada pada node menggunakan unsigned.

  typedef struct stack_t {
    StackNode *_top;
    unsigned _size;
  } Stack;
  

• Fungsi isEmpty()

  Fungsi ini digunakan untuk memeriksa apakah stack yang ada kosong atau tidak. Operasinya dilakukan dengan memeriksa apakah top dari stack tersebut bernilai NULL atau tidak.

  bool stack_isEmpty(Stack *stack) {
    return (stack->_top == NULL);
  }
  

• Fungsi push()

  Fungsi ini digunakan untuk menambahkan elemen baru pada stack. Operasinya dilakukan dengan tahap sebagai berikut:

  • Buat node baru dengan struct StackNode.
  • Jika stack sedang kosong, jadikan node baru ini sebagai top.
  • Jika tidak kosong, maka next dari node baru adalah top dan jadikan node baru sebagai top.

  void stack_push(Stack *stack, int value)
  {
    StackNode *newNode = (StackNode*) malloc(sizeof(StackNode));
    if (newNode) {
      stack->_size++;
      newNode->data = value;
  
      if (stack_isEmpty(stack)) newNode->next = NULL;
      else newNode->next = stack->_top;
  
      stack->_top = newNode;
    }
  }
  

• Fungsi pop()

  Fungsi ini digunakan untuk menghapus / mengambil node yang berada pada top stack. Operasinya dilakukan dengan tahap sebagai berikut:

  • Tampung top pada variabel sementara temp.
  • Mengganti top dengan referensi next dari top.
  • Menghapus variabel semetara sebelumnya.

  void stack_pop(Stack *stack)
  {
    if (!stack_isEmpty(stack)) {
      StackNode *temp = stack->_top;
      stack->_top = stack->_top->next;
      free(temp);
      stack->_size--;
    }
  }
  

• Fungsi top()

  Fungsi ini digunakan untuk mendapatkan data top dari stack. Operasinya dilakukan dengan:

  • Apabila stack tidak kosong, maka return data top.
  • Apabila stack kosong, maka return 0.

  int stack_top(Stack *stack)
  {
    if (!stack_isEmpty(stack))
      return stack->_top->data;
    return 0;
  }