C++ Data Structure: Hàng Đợi C++ , Queue C++

Chào mừng các bạn đến với chủ đề thuật toán lập trình tại blog: Phát Triển Phần Mềm 123AZ

Bài viết ngày hôm nay chúng ta sẽ cùng tìm hiểu về hàng đợi, (Queue)

1. Kiến thức cơ bản về hàng đợi.

– Là một cấu trúc tuyến tính và nó cũng được dựa trên nguyên ký xếp hàng. Nên thường gọi là hàng đợi.

– Phần tử nào vào trước sẽ được ra trước, phần tử nào vào sau sẽ được ra sau.

– Xây dựng hàng đợi dựa trên nguyên lý của danh sách liên kết.

2. Xây dựng Queue dựa theo nguyên lý của danh sách liên kết.

Chúng ta thấy hàng đợi tính chất ngược so với stack. Do đó việc xây dựng hàng đợi cũng khá tương đồng với việc xây dựng stack.

Chúng ta chỉ việc sửa lại hàm pop của stack về mức đơn giản hơn đó là remove phần tử đầu tiên đi là ok.

a. Xây dựng class NoteData.

template <typename T>
class NodeData
{
public:
    NodeData() : next_(NULL) { ; }
    void         set_data(T val) { data_ = val; }
    T            get_data() const { return data_; }
    void         set_next(NodeData<T>* next) { next_ = next; }
    NodeData<T>* get_next() const { return next_; };
private:
    T            data_;
    NodeData<T>* next_;
};

b. Xây dựng lớp Queue.

template<typename T>
class Queue
{
public:
    Queue() : p_head_(NULL) {};
    ~Queue() { ; };

    void push(T val)
    {
        NodeData<T>* last = p_head_; // Tim ra node cuoi cung.
        if (last == NULL)            // neu chua co node nao
        {
            NodeData<T>* temp = new NodeData<T>(); \
                temp->set_data(val);
            p_head_ = temp;
        }
        else
        {
            while (last->get_next() != NULL)
            {
                last = last->get_next();
            }

            NodeData<T>* temp = new NodeData<T>(); \
                temp->set_data(val);
            temp->set_next(NULL); // next temp = NULL
            last->set_next(temp); // next cua last la temp
        }
    }

    void pop() // remove first element
    {
        if (p_head_ != NULL)
        {
            NodeData<T>* temp = p_head_;
            p_head_ = p_head_->get_next();
            delete temp;
            temp = NULL;
        }
    }

    NodeData<T>* head() { return p_head_; };

public:
    NodeData<T>* p_head_;
};

c. Sử dụng Queue

#include <conio.h>
#include <iostream>
#include "Queue.h"


int main()
{
    Queue<int> stack_list;
    stack_list.push(1);
    stack_list.push(2);
    stack_list.push(3);
    stack_list.push(4);
    stack_list.push(5);
    stack_list.push(6);

    std::cout << "Danh sach sau khi push: \n";
    NodeData<int>* p_head = stack_list.head();
    if (p_head != NULL)
    {
        NodeData<int>* temp = p_head;
        while (temp != NULL)
        {
            std::cout << "  " << temp->get_data();
            temp = temp->get_next();
        }
    }

    stack_list.pop();
    stack_list.pop();

    std::cout << "\n\n Danh sach sau khi pop: \n";
    p_head = stack_list.head();
    if (p_head != NULL)
    {
        NodeData<int>* temp = p_head;
        while (temp != NULL)
        {
            std::cout << "  " << temp->get_data();
            temp = temp->get_next();
        }
    }

    _getch();

    return 0;
}

 

Ok. Đó là cơ bản về cấu trúc dữ liệu hàng đợi.