Struktur Data - Penjelasan Stack / Tumpukan ~ Problem Solver

Stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhir kali dimasukkan akan pertama kali keluar dari stack tersebut.

Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix). Ciri stack:

TOP merupakan sebutan untuk elemen paling atas dari suatu stack
Elemen TOP merupakan elemen yang paling akhir ditambahkan
Elemen TOP diketahui
penambahan dan penghapusan elemen selalu dilakukan di TOP
LIFO

Ilustrasi / Implementasi Stack:

Pemanfaatan Stack:

Perhitungan ekspresi aritmatika (posfix)
algoritma backtraking (runut balik)
algoritma rekursif

Beberapa fungsi atau Operasi di Stack:

Stack Operations

push(new-item:item-type): Adds an item onto the stack.
top():item-type: Returns the last item pushed onto the stack.
pop(): Removes the most-recently-pushed item from the stack.
is-empty():Boolean: True if no more items can be popped and there is no top item.
is-full():Boolean: True if no more items can be pushed.
get-size():Integer: Returns the number of elements on the stack.

All operations except get-size() can be performed in

O(1)

time. get-size() runs in at worst

O(N).

Contoh Stack di Java :

public class MyStack {
   private int maxSize;
   private long[] stackArray;
   private int top;
   public MyStack(int s) {
      maxSize = s;
      stackArray = new long[maxSize];
      top = -1;
   }
   public void push(long j) {
      stackArray[++top] = j;
   }
   public long pop() {
      return stackArray[top--];
   }
   public long peek() {
      return stackArray[top];
   }
   public boolean isEmpty() {
      return (top == -1);
   }
   public boolean isFull() {
      return (top == maxSize - 1);
   }
   public static void main(String[] args) {
      MyStack theStack = new MyStack(10); 
      theStack.push(10);
      theStack.push(20);
      theStack.push(30);
      theStack.push(40);
      theStack.push(50);
      while (!theStack.isEmpty()) {
         long value = theStack.pop();
         System.out.print(value);
         System.out.print(" ");
      }
      System.out.println("");
   }
}

Output :