Bagaimana untuk melaksanakan java stack dan queue

Timbunan dan Gilir

1. Timbunan ialah struktur data last in first off (LIFO)

2. Baris gilir ialah yang pertama masuk dahulu -keluar (FIFO) struktur

Timbunan (Timbunan)

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.

Pelaksanaan tindanan

接口	说明	复杂度
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

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 .

Pelaksanaan baris gilir

Antaramuka

Penerangan

Kerumitan

void enqueue(E e)

Enqueue

O(1)

接口	说明	复杂度
void enqueue(E e)	入队	O(1) 均摊
E dequeue()	出队	O(n)
E getFront()	获取队首元素	O(1)
int getSize()	获取队列元素个数	O(1)
boolean isEmpty()	判断队列是否为空	O(1)

Kongsi sama rata

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)

Memasuki baris gilir bermula dari penghujung baris gilir, dan mengubah saiz mungkin dicetuskan, jadi pelunasan ialah O(1 ). Nyah gilir berada di kepala baris gilir, dan pelaksanaan tatasusunan memerlukan mengalihkan semua elemen setiap kali, O(n).

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan java stack dan queue. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!