Melaksanakan Baris Gilir menggunakan Tindanan

Barisan dan Tindanan ialah Struktur Data yang agak Mudah yang kami gunakan dalam pengekodan harian kami. Sebenarnya, mereka boleh dianggap sebagai struktur yang paling mudah untuk mengekalkan data.

Sepanjang artikel, saya akan menggunakan DS untuk merujuk kepada Struktur Data.

Barisan ialah DS yang berfungsi pada prinsip FIFO. Data yang datang dahulu dibenarkan keluar dahulu. Terdapat banyak cara untuk melaksanakan baris gilir. Kami bebas menggunakan tatasusunan, senarai terpaut dan banyak lagi. Tetapi di sini, saya akan membincangkan pelaksanaan Queue menggunakan DS lain yang dipanggil Stack.

Kini, kita semua tahu, Stack ialah DS yang berfungsi pada prinsip LIFO. Saya sentiasa berfikir tentang menyusun buku satu di atas yang lain jadi jangan ragu untuk menggunakan analogi itu jika ia membantu anda memvisualisasikan.

Saya terjumpa soalan ini dalam peringkat penggodam di mana mereka memerlukan kami melaksanakan Baris Gilir menggunakan 2 Tindanan. Nampak simple kan? Luangkan masa untuk berfikir bagaimana kita boleh mencapai ini.

Anda mungkin telah menghasilkan beberapa penyelesaian kerana terdapat banyak cara untuk melakukan ini. Jadi mengapa anda tidak mencubanya secara langsung?

Soalan

Sekarang, bagi mereka yang mencuba dan mendapat "time-out error" dan bagi mereka yang tidak bersusah payah mencuba, izinkan saya menerangkan kepada anda penyelesaian yang paling mudah dan paling mudah untuk masalah ini.

Mula-mula lihat bagaimana tindanan boleh dilaksanakan.

Seperti yang anda lihat, saya telah melaksanakan tindanan menggunakan senarai. Pada mulanya pembina memulakan senarai kosong. Kami menolak data dengan melampirkannya pada penghujung senarai. Semasa muncul, jika kami tidak menyediakan indeks ia muncul dari hujung senarai. Oleh itu, elemen terakhir yang akan disisipkan ialah elemen pertama yang akan muncul.

Kini, Dengan cara yang sama untuk baris gilir kami telah memulakan dua tindanan berbeza. Satu untuk enqueue dan satu untuk dequeue.

Kami menggunakan enqueueStack serupa dengan tindanan hanya untuk menolak data pada penghujung senarai. Tetapi untuk dequeueStack, kita tahu fungsi pop tindanan mengalih keluar elemen daripada yang terakhir jadi apa yang kita lakukan ialah; kita membalikkan enqueueStack dan meletakkannya dalam dequeueStack.Oleh itu, elemen pertama enqueueStack menjadi elemen terakhir dequeueStack, kedua enqueueStack menjadi kedua terakhir dequeueStack dan seterusnya. Jadi sekarang jika kita menggunakan fungsi pop untuk dequeueStack maka ia akan mengalih keluar elemen pertama yang kita tolak, dengan itu, meniru baris gilir.

Jangan risau jika ini kedengaran mengelirukan sekarang! Sebaik sahaja anda melihat kod anda akan menyedari apa yang saya perkatakan. Malah lihat sekarang juga!

Anda mungkin tertanya-tanya untuk apa cek tambahan tersebut. Seperti menyemak dequeueStack kosong atau tidak. Jika kita tidak menyemaknya pada mulanya. Unsur-unsur enqueueStack melalui pembalikan akan berada di dalam dequeueStack dan apa yang berlaku ialah elemen Dequeue Stacks yang sepatutnya dihidupkan dahulu kini akhirnya menjadi yang terakhir. Jadi dequeueStack pertama perlu dikosongkan seperti yang ditunjukkan dalam kod.

Sama seperti ini, printFront mencetak item yang sepatutnya berada di hadapan baris gilir.

Selepas pelaksanaan ini, kami membaca input daripada STDIN dan mencetak output ke STDOUT.

Input kami agak seperti ini:

Dan fungsi utama yang lengkap ialah:

Saya telah cuba melaksanakan ini dengan cara yang semudah mungkin. Mungkin terdapat beberapa cara lain dan lebih baik untuk melaksanakan ini. Salah satu daripadanya dibentangkan di sini!

Atas ialah kandungan terperinci Melaksanakan Baris Gilir menggunakan Tindanan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!