Timbunan dan Baris Gilir dalam C++

Pengenalan kepada tindanan dan baris gilir dalam C++

Timbunan dan baris gilir adalah struktur data yang biasa digunakan dalam C++, dan ia digunakan secara meluas dalam atur cara. Artikel ini akan memperkenalkan konsep, penggunaan dan senario aplikasi tindanan dan baris gilir secara terperinci.

1. Konsep tindanan

Timbunan (Stack) ialah struktur data linear, yang mempunyai ciri-ciri "masuk pertama, keluar terakhir". Dalam tindanan, data yang ditolak ke dalam tindanan adalah lebih dekat dengan bahagian bawah tindanan;

Operasi utama tindanan ialah tolak dan pop. Menolak adalah untuk menambah data pada tindanan, dan pop adalah untuk memadam data daripada tindanan. Tindanan juga mempunyai dua operasi khas yang penting: melihat elemen atas tindanan (atas) dan menentukan sama ada tindanan itu kosong (kosong).

Senario aplikasi tindanan adalah sangat luas, contohnya, penggunaan tindanan terlibat dalam panggilan fungsi. Apabila fungsi dipanggil, parameternya, pembolehubah setempat dan maklumat lain akan ditolak ke timbunan. Apabila pelaksanaan fungsi tamat, maklumat ini akan muncul dari timbunan dan dipulihkan kepada keadaan sebelum panggilan fungsi.

2. Konsep giliran

Barisan (Queue) juga merupakan struktur data linear, yang mempunyai ciri-ciri "masuk dahulu, keluar dahulu". Dalam baris gilir, data yang beratur lebih awal adalah lebih dekat dengan kepala baris gilir;

Operasi utama baris gilir ialah enqueue dan dequeue. Memasuki baris gilir bermakna menambah data ke penghujung baris gilir, manakala nyah gilir bermaksud memadam data daripada kepala baris gilir. Barisan gilir juga mempunyai dua operasi khas yang penting: melihat elemen kepala (depan) dan menentukan sama ada baris gilir kosong (kosong).

Baris gilir juga digunakan secara meluas Contohnya, dalam penjadualan proses dalam sistem pengendalian, baris gilir boleh digunakan untuk menyimpan proses yang menunggu untuk dilaksanakan. Apabila sumber sistem adalah percuma, satu proses dikeluarkan dari kepala baris gilir dan dilaksanakan sehingga semua tugasan selesai.

3. Contoh aplikasi tindanan dan baris gilir

1. Padanan kurungan

Dalam pengaturcaraan, selalunya perlu untuk menentukan sama ada kurungan dalam rentetan sepadan. Sebagai contoh, semasa menulis program Python, jika anda perlu menyemak sama ada blok kod diinden dengan betul, anda boleh menggunakan timbunan untuk mencapai ini.

Kaedah pelaksanaan khusus adalah untuk melintasi setiap aksara dalam rentetan dan menolaknya ke tindanan apabila menemui kurungan kiri. Apabila kurungan yang betul ditemui, elemen teratas timbunan muncul untuk dipadankan. Jika perlawanan berjaya, teruskan melintasi jika tidak, mesej ralat dikembalikan.

2. Penjadualan Proses

Dalam sistem pengendalian, adalah perlu untuk mencapai penjadualan dan penyelarasan proses yang bersatu. Pada masa ini, anda boleh menggunakan baris gilir untuk menyimpan proses menunggu pelaksanaan, dan sistem pengendalian menentukan keutamaan dan susunan pelaksanaan.

Kaedah pelaksanaan khusus adalah untuk mengabstrak setiap proses ke dalam struktur data, termasuk nombor proses, keutamaan dan maklumat lain. Letakkan proses ini ke dalam baris gilir, dan kemudian laksanakan proses dalam baris gilir mengikut urutan. Apabila proses menyelesaikan tugasnya, ia akan muncul daripada baris gilir sehingga baris gilir kosong.

4. Pelaksanaan tindanan dan baris gilir dalam C++

Dalam C++, anda boleh menggunakan kelas kontena yang disediakan oleh perpustakaan standard untuk melaksanakan tindanan dan baris gilir.

1. Pelaksanaan tindanan

Timbunan boleh dilaksanakan menggunakan kelas kontena std::stack.

std::stack ialah kelas templat yang memerlukan penentuan jenis elemen dan jenis bekas asas. Apabila jenis bekas asas tidak dinyatakan, std::deque digunakan secara lalai sebagai bekas asas.

Berikut ialah contoh pelaksanaan tindanan mudah:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << s.top() << std::endl; // 输出3

    s.pop();

    std::cout << s.top() << std::endl; // 输出2

    while (!s.empty()) {
        s.pop();
    }

    return 0;
}

2. Pelaksanaan giliran

Baris gilir boleh dilaksanakan menggunakan kelas kontena std::queue.

std::queue juga merupakan kelas templat dan perlu menentukan jenis elemen dan jenis bekas asas. Apabila jenis bekas asas tidak dinyatakan, std::deque digunakan secara lalai sebagai bekas asas.

Berikut ialah contoh pelaksanaan baris gilir yang mudah:

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << q.front() << std::endl; // 输出1

    q.pop();

    std::cout << q.front() << std::endl; // 输出2

    while (!q.empty()) {
        q.pop();
    }

    return 0;
}

Ringkasan

Seperti yang dapat dilihat daripada pengenalan di atas, tindanan dan baris gilir adalah struktur data yang sangat praktikal yang boleh membantu kita menyelesaikan banyak masalah praktikal. Dalam pengaturcaraan, menguasai prinsip penggunaan dan pelaksanaan kedua-dua struktur data ini boleh meningkatkan kecekapan dan kebolehpercayaan program.

Atas ialah kandungan terperinci Timbunan dan Baris Gilir dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!