Timbunan ialah struktur data last in first off (LIFO)
Baris gilir ialah yang pertama masuk dahulu -keluar (FIFO) struktur
Timbunan ialah struktur linear , berbanding dengan tatasusunan, operasi yang sepadan dengan tindanan ialah subset tatasusunan.
Ia hanya boleh menambah elemen dari satu hujung, dan hanya boleh mengambil elemen dari satu hujung (hujung ini dipanggil bahagian atas tindanan).
Timbunan ialah struktur data yang digunakan secara meluas Dalam penggunaan komputer, timbunan digunakan secara meluas, seperti penganalisis leksikal dalam penyusun, mesin maya Java, operasi buat asal (Undo) dalam perisian, dan penyemakan imbas operasi rollback dalam pengkompil, pelaksanaan panggilan fungsi dalam pengkompil, dsb.
| 接口 | 说明 | 复杂度 |
|---|---|---|
| void push(E e) | 向栈中加入元素 | O(1) 均摊 |
| E pop() | 弹出栈顶元素 | O(1) 均摊 |
| E peek() | 查看栈顶元素 | O(1) |
| int getSize() | 获取栈中元素个数 | O(1) |
| boolean isEmpty() | 判断栈是否为空 | O(1) |
Penjelasan: operasi tolak dan pop dilakukan pada penghujung, yang mungkin mencetuskan ubah saiz, tetapi ia adalah O(1) sama rata.
Jika anda ingin mengetahui lebih lanjut tentang analisis kerumitan masa, sila beri perhatian kepada artikel yang akan dikemas kini oleh penulis kemudian: Apakah masalah yang O(n) jelaskan?
Timbunan boleh dilaksanakan melalui tatasusunan atau senarai terpaut Di sini kami menggunakan tatasusunan untuk melaksanakan antara muka di atas.
Dalam reka bentuk tindanan, pengguna hanya memberi perhatian kepada akses elemen atas tindanan dan panjang tindanan, jadi kod reka bentuk adalah seperti berikut:
Pembaca boleh menggunakan Timbunan Struktur data ini menyelesaikan masalah No. 20 pada LeetCode: Kurung Sah Anda juga boleh menyemak Pengiraan Harian: Tanda Kurung Sah.
Baris Gilir juga merupakan struktur data linear Berbanding dengan tatasusunan, operasi yang sepadan dengan baris gilir ialah subset tatasusunan.
Elemen hanya boleh ditambah dari satu hujung (hujung baris gilir), dan elemen hanya boleh dikeluarkan dari hujung satu lagi (kepala baris gilir).
Aplikasi baris gilir boleh dicerminkan dalam senarai main pada pemain, objek aliran data, struktur penghantaran data tak segerak (IO fail, komunikasi paip, soket, dll. Sudah tentu, yang paling intuitif ialah beratur .
| Antaramuka | Penerangan | Kerumitan | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| void enqueue(E e) | Enqueue | O(1)
|
||||||||||||||||||
| E dequeue() | Dequeue | O(n) | ||||||||||||||||||
| E getFront() | Dapatkan elemen pertama pasukan | O(1) | ||||||||||||||||||
| int getSize() | Dapatkan bilangan elemen baris gilir | O(1) | ||||||||||||||||||
| boolean isEmpty() | Nilai sama ada baris gilir kosong | O(1) |
Atas ialah kandungan terperinci Bagaimana untuk melaksanakan java stack dan queue. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
