• Top - merupakan node paling atas dari stack.

Stack adalah struktur data dinamis yang mengikuti prinsip Last In First Out (LIFO). Pada LIFO, Elemen terakhir yang dimasukkan pada stack akan menjadi elemen yang pertama dihapus. Sebagai contoh dari Stack adalah tumpukan piring, dimana piring baru diletakkan pada tumpukan paling atas dan dikeluarkan juga dari paling atas.

• isEmpty – untuk memeriksa apakah stack kosong atau tidak.
• size – untuk mendapatkan data size pada stack.
• push – operasi untuk menambahkan data pada tumpukan paling atas.
• pop – operasi untuk menghapus data pada tumpukan paling atas.
• top/peek – untuk mendapatkan data pada tumpukan paling atas.

Salah satu contoh penerapan Stack adalah bagaimana mengubah notasi infix menjadi postfix. Notasi infix adalah notasi yang biasa dibaca dan diselesaikan oleh manusia dalam persoalan matematika, contoh ‘x + y / (10 + z)’ namun komputer tidak dapat membedakan operator dan tanda kurung (parentheses) dengan mudah sehingga komputer akan mengubah notasi infix menjadi postfix, contoh ‘x y + 10 z + /’. Untuk mengubah notasi infix menjadi postfix digunakanlah struktur data stack.

Link Implementasi Lengkap Stack dapat dilihat di sini

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

  Node direpresentasikan oleh struct bernama StackNode yang menyimpan data bertipe int dan referensi pada node selanjutnya next.

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

• Struktur Stack

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

  #include <bits/stdc++.h>
  using namespace std;
  
  int main(){
      stack<int> st;
      
      return 0;
  }

  Catatan: STL Stack tidak memiliki iterator

• isEmpty

  Untuk memeriksa apakah stack kosong, cukup dengan memeriksa apakah top dari stack tersebut bernilai NULL atau tidak.

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

  #include <bits/stdc++.h>
  using namespace std;
  
  int main(){
      stack<int> st;
  
      if(st.empty()){
          cout << "stack ini kosong" << endl;
      }
      
      return 0;
  }

• push

  • Buat node baru.

  • Jika stack kosong, jadikan node baru sebagai top.

  • Jika tidak kosong, maka jelas bahwa next dari node baru adalah top, 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;
        }
    }

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        stack<int> st;
    
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        
        return 0;
    }

• pop

  Untuk melakukan pop, dilakukan langkah langkah berikut.

  • Tampung top pada variabel temp (temporary).

  • Mengganti top dengan referensi next dari top.

  • Menghapus node temp.

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

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        stack<int> st;
    
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        
        st.pop();
        
        return 0;
    }

• top

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

  #include <bits/stdc++.h>
  using namespace std;
  
  int main(){
      stack<int> st;
  
      st.push(1);
      st.push(2);
      st.push(3);
      st.push(4);
  
      while(!st.empty()){
          cout << st.top() << endl;
          st.pop();
      }
      
      return 0;
  }

Selengkapnya mengenai std::stack dapat dibaca di sini atau pada dokumentasi bahasa C++ di sini.

Lanjut ke Queue >