Bekerja dengan stack

Struktur Data dan Algoritma di Python

Miriam Antona

Software Engineer

Stack

LIFO: Last-In First-Out
- Item terakhir dimasukkan akan pertama dikeluarkan

Gambar tumpukan buku.

Stack

LIFO: Last-In First-Out
- Item terakhir dimasukkan akan selalu pertama dikeluarkan
Hanya bisa menambah di atas
- Push ke stack

Gambar tumpukan buku dengan satu buku baru ditambahkan di atas.

Stack

LIFO: Last-In First-Out
- Item terakhir dimasukkan akan selalu pertama dikeluarkan
Hanya bisa menambah di atas
- Push ke stack
Hanya bisa mengambil dari atas
- Pop dari stack

Gambar tumpukan buku dengan sebuah buku diambil dari bagian atas.

Stack

LIFO: Last-In First-Out
- Item terakhir dimasukkan akan pertama dikeluarkan
Hanya bisa menambah di atas
- Push ke stack
Hanya bisa menghapus dari atas
- Pop dari stack
Hanya bisa membaca elemen terakhir
- Peek pada stack

Gambar tumpukan buku dengan panah menunjuk sampul buku di bagian atas tumpukan.

Stack - penggunaan nyata

Fitur undo

Sebuah stack dengan satu elemen.

Stack - penggunaan nyata

Fitur undo
- push tiap ketikan

Sebuah stack dengan elemen baru ditambahkan di atas.

Stack - penggunaan nyata

Fitur undo
- push tiap ketikan

Sebuah stack dengan elemen baru ditambahkan di atas.

Stack - penggunaan nyata

Fitur undo
- push tiap ketikan

Sebuah stack dengan elemen baru ditambahkan di atas.

Stack - penggunaan nyata

Fitur undo
- push tiap ketikan

Sebuah stack dengan elemen baru ditambahkan di atas.

Stack - penggunaan nyata

Fitur undo
- push tiap ketikan
- pop ketikan terakhir

Sebuah stack dengan satu elemen di bagian atas telah dihapus.

Stack - penggunaan nyata

Pengecek simbol: ( [ { } ] )
- push simbol buka

Sebuah stack dengan satu simbol buka.

Stack - penggunaan nyata

Pengecek simbol: ( [ { } ] )
- push simbol buka

Sebuah stack dengan simbol buka baru ditambahkan di atas.

Stack - penggunaan nyata

Pengecek simbol: ( [ { } ] )
- push simbol buka

Sebuah stack dengan simbol buka baru ditambahkan di atas.

Stack - penggunaan nyata

Pengecek simbol: ( [ { } ] )
- push simbol buka
- cek simbol tutup

Sebuah stack dengan simbol buka dan kata "cek "}"".

Stack - penggunaan nyata

Pengecek simbol: ( [ { } ] )
- push simbol buka
- cek simbol tutup
- pop simbol buka yang cocok

Sebuah stack di mana satu simbol buka di bagian atas dihapus.

Stack - penggunaan nyata

Pemanggilan fungsi
- push blok memori
- pop setelah eksekusi selesai

Stack - implementasi dengan singly linked list

Sebuah stack direpresentasikan sebagai linked list.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

Stack - implementasi dengan singly linked list

Sebuah stack sebagai linked list dengan nama bagian-bagian node.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Stack - implementasi dengan singly linked list

Sebuah stack sebagai linked list dengan kata "TOP" menunjuk ke atas stack.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Stack - push

Representasi stack kosong dan stack berisi elemen.

def push(self, data):

Stack - push

Representasi stack kosong dan stack berisi elemen dengan node baru akan disisipkan.

def push(self, data): 
  new_node = Node(data)

  if self.top:

Stack - push

Representasi stack kosong dan stack berisi elemen, dengan node baru terhubung ke elemen di atas stack.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

Stack - push

Representasi stack kosong dan stack berisi elemen dengan node baru telah disisipkan.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

Stack - pop

def pop(self):

  if self.top is None:

    return None

  else:

Representasi stack dengan kata "TOP" menunjuk node di bagian atas.

Stack - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

Representasi stack dengan kata "popped_node" menunjuk node di atas stack.

Stack - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

Representasi stack dengan kata "popped_node" menunjuk node di atas dan kata "TOP" menunjuk node kedua.

Stack - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

Representasi stack dengan kata "popped_node" menunjuk node yang terlepas dari stack dan kata "TOP" menunjuk node di atas stack.

Stack - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

Representasi stack dengan kata "TOP" menunjuk node di bagian atas stack.

Stack - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue di Python

LifoQueue:
- Modul queue Python
- berperilaku seperti stack

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

Ayo berlatih!

Struktur Data dan Algoritma di Python