劍指offer之兩個(gè)棧實(shí)現(xiàn)隊(duì)列問題

1 問題

兩個(gè)棧實(shí)現(xiàn)隊(duì)列的插入和獲取頭部元素的功能

2 分析

我們定義連個(gè)棧stack1，stack2，當(dāng)隊(duì)列彈出頭部元素的時(shí)候，我們知道隊(duì)列先進(jìn)后出，我們先把一個(gè)元素壓到stack1,然后再壓一個(gè)元素到stack1,然后我們把stack1的top函數(shù)得到棧頂值然后pop彈出來，push到stack2里面去，這個(gè)時(shí)候后面進(jìn)的元素就在stack2的棧底，然后我們?cè)侔裺tack1的top函數(shù)得到棧頂值然后pop彈出來，push到stack2里面去,這個(gè)時(shí)候我們stack2的top()棧頂函數(shù)也就是我們第一個(gè)壓到stack1的元素，我們只需要把stack2的top()的值獲取就是隊(duì)列的第一個(gè)元素。

簡(jiǎn)言之

隊(duì)列獲取頭部元素的功能：如果stack2里面沒有元素，我們需要把stack1里面的元素從棧頂一個(gè)一個(gè)彈出來壓入到stack2，當(dāng)獲取隊(duì)列的頭部值的時(shí)候，我們只需要獲取stack2的頂部元素值（top方法）就行，然后把這個(gè)值pop出來，如果stack2里面有元素，我們直接獲取stack2的頂部元素值（top方法）就行，然后把這個(gè)值pop出來。

插入隊(duì)列元素的功能，我們只需要把元素直接push到stack1里面就行，不管stack2里面有沒有值。


 
3 代碼實(shí)現(xiàn)

    #include <iostream>
    #include <stack>
     
    using namespace std;
     
    class student
    {
    public:
        student(){}
        ~student(){}
        student(std::string name, std::string age, std::string sex)
        {
            this->name = name;
            this->age = age;
            this->sex = sex;
        }
        void toString()
        {
            std::cout << "name is "<< name << " age is "<< age << " sex is "<< sex << std::endl;
        }
    private:
        std::string name;
        std::string age;
        std::string sex;
    };
     
    template <typename T>
    class Test
    {
    public:
        Test(){}
        ~Test(){}
        Test(const T& t);
        //往隊(duì)列里面添加元素
        void add(const T& t);
        //往隊(duì)列里面刪除元素
        T top();
    private:
        std::stack<T> stack1;
        std::stack<T> stack2;
    };
     
    template <typename T> void Test<T>::add(const T& t)
    {
        stack1.push(t);
    }
     
    template <typename T> T Test<T>::top()
    {
        if (stack2.empty())
        {
            //注意這里是while 不是if，我們需要把stack1里面的數(shù)據(jù)全部彈出來放到stack2里面去
            while (!stack1.empty())
            {
                T& value = stack1.top();
                stack1.pop();
                stack2.push(value);
            }
        }
        
        T top = stack2.top();
        stack2.pop();
        return top;
        
    }
    int main() {
        
        student std1("chenyu", "27", "man");
        student std2("chencaifeng", "27", "woman");
        student std3("chenzixuan", "3", "woman");
        student std4("chenzixi", "2", "woman");
        student std5("chenxuan", "21", "woman");
        
        Test<student> queue;
        queue.add(std1);
        queue.add(std2);
        queue.add(std3);
        queue.add(std4);
        
        student top1 = queue.top();
        top1.toString();
        student top2 = queue.top();
        top2.toString();
        student top3 = queue.top();
        top3.toString();
        
        queue.add(std5);
        student top4 = queue.top();
        top4.toString();
        student top5 = queue.top();
        top5.toString();  
     
        return 0;
    }


 
4 運(yùn)行結(jié)果

    name is chenyu age is 27 sex is man
    name is chencaifeng age is 27 sex is woman
    name is chenzixuan age is 3 sex is woman
    name is chenzixi age is 2 sex is woman
    name is chenxuan age is 21 sex is woman
     
     

 



 



 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)