Tumpukan (Stacks)
Apa itu ADT?
- Abstract Data Type (ADT) adalah kumpulan data ditambah serangkaian operasi di atasnya.
- Anda menggunakan operasinya dan mengabaikan bagaimana ia dibangun di dalamnya.
- Stack, queue, dan linked list semuanya adalah ADTs.
Stack adalah LIFO
- Stack adalah Last In, First Out (LIFO).
- Item terakhir yang Anda tambahkan adalah item pertama yang Anda ambil keluar.
- Pikirkan tumpukan piring: Anda mengambil piring paling atas terlebih dahulu.
push dan pop dengan list
- Kita dapat membangun stack dari list Python.
- push =
stack.append(x)— tambahkan ke akhir (paling atas). - pop =
stack.pop()— hapus dan kembalikan akhir (paling atas).
stack = []
stack.append("a")
stack.append("b")
print(stack.pop())
print(stack)
peek dan empty
- Peek ke bagian atas tanpa mengeluarkannya:
stack[-1]. - Stack kosong ketika
len(stack) == 0. - Mem-pop stack kosong adalah error, jadi periksa terlebih dahulu.
stack = [10, 20, 30]
print(stack[-1]) # peek the top
print(len(stack) == 0) # is it empty?
Dalam pseudocode Cambridge
- Ujian membangun stack dari array plus pointer
top(indeks).
DECLARE stack : ARRAY[1:10] OF INTEGER
DECLARE top : INTEGER
top ← 0 // 0 means empty
// push value
top ← top + 1
stack[top] ← value
// pop into value
value ← stack[top]
top ← top - 1
Kesalahan umum
- Stack adalah last-in, first-out: push ke atas, pop dari atas.
- Periksa apakah tidak kosong sebelum Anda pop.
Sekarang Anda coba
- Gunakan list sebagai stack Anda (
appenduntuk push,popuntuk remove). - Tekan Periksa jawaban untuk menguji kode Anda.
Tumpukan bersifat LIFO
Tumpukan mendorong dan popped di satu ujung — terakhir masuk, pertama keluar.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Mulailah dengan tumpukan kosong. Dorong (push) 1, kemudian 2, lalu 3. Kemudian pop sekali, simpan nilai yang dihapus di top. (top seharusnya bernilai 3 dan tumpukan seharusnya berisi [1, 2].)
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Gunakan tumpukan untuk membalik daftar items. Dorong setiap item ke tumpukan, lalu pop semuanya ke dalam result. (result seharusnya berisi [3, 2, 1].)
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Tulis top(stack) yang mengembalikan item teratas (item terakhir) tanpa menghapusnya. Jika tumpukan kosong, kembalikan None.
Klik Jalankan untuk melihat output di sini.