Struktur Data Stack

Dalam tutorial ini, Anda akan belajar tentang struktur data tumpukan dan implementasinya dalam Python, Java, dan C / C ++.

Stack adalah struktur data yang berguna dalam pemrograman. Ini seperti tumpukan piring yang diletakkan di atas satu sama lain.

elemen pada tumpukan ditambahkan di atas dan dihapus dari atas seperti tumpukan piring — Representasi stack mirip dengan tumpukan piring

Pikirkan tentang hal-hal yang dapat Anda lakukan dengan tumpukan piring seperti itu

Taruh piring baru di atasnya
Hapus pelat atas

Jika Anda ingin piring di bagian bawah, Anda harus melepaskan semua piring di atas terlebih dahulu. Pengaturan seperti itu disebut Terakhir Masuk Pertama Keluar – item terakhir yang merupakan item pertama yang keluar.

Prinsip LIFO Stack

Dalam istilah pemrograman, meletakkan item di atas tumpukan disebut Dorong dan menghapus item disebut pop.

mewakili prinsip LIFO dengan menggunakan operasi push dan pop — Operasi Stack Push dan Pop

Pada gambar di atas, meskipun item 2 disimpan terakhir, itu dihapus terlebih dahulu – jadi mengikuti The Last In First Out (LIFO) prinsip.

Kita dapat mengimplementasikan tumpukan dalam bahasa pemrograman apa pun seperti C, C ++, Java, Python, atau C #, tetapi spesifikasinya hampir sama.

Operasi Dasar Stack

Tumpukan adalah objek (tipe data abstrak – ADT) yang memungkinkan operasi berikut:

Dorong: Tambahkan elemen ke atas tumpukan
Pop: Hapus elemen dari atas tumpukan
Kosong: Periksa apakah tumpukan kosong
Penuh: Periksa apakah tumpukan sudah penuh
Mengintip: Dapatkan nilai elemen teratas tanpa menghapusnya

Cara Kerja Struktur Data Stack

Operasi bekerja sebagai berikut:

Sebuah penunjuk dipanggil PUNCAK digunakan untuk melacak elemen teratas dalam tumpukan.
Saat menginisialisasi tumpukan, kami menetapkan nilainya ke -1 sehingga kami dapat memeriksa apakah tumpukan kosong dengan membandingkan TOP == -1.
Saat mendorong elemen, kami meningkatkan nilai PUNCAK dan tempatkan elemen baru pada posisi yang ditunjuk oleh PUNCAK.
Saat memunculkan elemen, kami mengembalikan elemen yang ditunjuk oleh PUNCAK dan mengurangi nilainya.
Sebelum mendorong, kami memeriksa apakah tumpukan sudah penuh
Sebelum bermunculan, kami memeriksa apakah tumpukan sudah kosong

Menambahkan elemen ke atas tumpukan dan menghapus elemen dari tumpukan teratas — Cara Kerja Struktur Data Stack

Implementasi Stack dengan Python, Java, C, dan C ++

Implementasi tumpukan yang paling umum menggunakan array, tetapi juga dapat diimplementasikan menggunakan daftar.

Python
Java
C
C +

# Stack implementation in python


# Creating a stack
def create_stack():
    stack = []
    return stack


# Creating an empty stack
def check_empty(stack):
    return len(stack) == 0


# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)


# Removing an element from the stack
def pop(stack):
    if (check_empty(stack)):
        return "stack is empty"

    return stack.pop()


stack = create_stack()
push(stack, str(1))
push(stack, str(2))
push(stack, str(3))
push(stack, str(4))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))

// Stack implementation in Java

class Stack {
  private int arr[];
  private int top;
  private int capacity;

  // Creating a stack
  Stack(int size) {
    arr = new int[size];
    capacity = size;
    top = -1;
  }

  // Add elements into stack
  public void push(int x) {
    if (isFull()) {
      System.out.println("OverFlownProgram Terminatedn");
      System.exit(1);
    }

    System.out.println("Inserting " + x);
    arr[++top] = x;
  }

  // Remove element from stack
  public int pop() {
    if (isEmpty()) {
      System.out.println("STACK EMPTY");
      System.exit(1);
    }
    return arr[top--];
  }

  // Utility function to return the size of the stack
  public int size() {
    return top + 1;
  }

  // Check if the stack is empty
  public Boolean isEmpty() {
    return top == -1;
  }

  // Check if the stack is full
  public Boolean isFull() {
    return top == capacity - 1;
  }

  public void printStack() {
    for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
    }
  }

  public static void main(String[] args) {
    Stack stack = new Stack(5);

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();
    System.out.println("nAfter popping out");

    stack.printStack();

  }
}

// Stack implementation in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

int count = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  count++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("n STACK EMPTY n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  count--;
  printf("n");
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < count; i++) {
    printf("%d ", s->items[i]);
  }
  printf("n");
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  printf("nAfter popping outn");
  printStack(s);
}

// Stack implementation in C++

#include <stdlib.h>
#include <iostream>

using namespace std;

#define MAX 10
int size = 0;

// Creating a stack
struct stack {
  int items[MAX];
  int top;
};
typedef struct stack st;

void createEmptyStack(st *s) {
  s->top = -1;
}

// Check if the stack is full
int isfull(st *s) {
  if (s->top == MAX - 1)
    return 1;
  else
    return 0;
}

// Check if the stack is empty
int isempty(st *s) {
  if (s->top == -1)
    return 1;
  else
    return 0;
}

// Add elements into stack
void push(st *s, int newitem) {
  if (isfull(s)) {
    printf("STACK FULL");
  } else {
    s->top++;
    s->items[s->top] = newitem;
  }
  size++;
}

// Remove element from stack
void pop(st *s) {
  if (isempty(s)) {
    printf("n STACK EMPTY n");
  } else {
    printf("Item popped= %d", s->items[s->top]);
    s->top--;
  }
  size--;
  cout << endl;
}

// Print elements of stack
void printStack(st *s) {
  printf("Stack: ");
  for (int i = 0; i < size; i++) {
    cout << s->items[i] << " ";
  }
  cout << endl;
}

// Driver code
int main() {
  int ch;
  st *s = (st *)malloc(sizeof(st));

  createEmptyStack(s);

  push(s, 1);
  push(s, 2);
  push(s, 3);
  push(s, 4);

  printStack(s);

  pop(s);

  cout << "nAfter popping outn";
  printStack(s);
}

Stack Time Complexity

Untuk implementasi stack berbasis array, operasi push dan pop membutuhkan waktu yang konstan, yaitu O(1).

Aplikasi Struktur Data Stack

Meskipun stack adalah struktur data yang sederhana untuk diimplementasikan, ia sangat kuat. Penggunaan tumpukan yang paling umum adalah:

Untuk membalikkan kata – Taruh semua huruf di tumpukan dan keluarkan. Karena urutan tumpukan LIFO, Anda akan mendapatkan huruf dalam urutan terbalik.
Di kompiler – Penyusun menggunakan tumpukan untuk menghitung nilai ekspresi seperti 2 + 4 / 5 * (7 - 9) dengan mengubah ekspresi menjadi bentuk prefiks atau postfix.
Di browser – Tombol kembali di browser menyimpan semua URL yang telah Anda kunjungi sebelumnya dalam satu tumpukan. Setiap kali Anda mengunjungi halaman baru, itu ditambahkan di atas tumpukan. Saat Anda menekan tombol kembali, URL saat ini dihapus dari tumpukan, dan URL sebelumnya diakses.