以前，我們實現(xiàn)一個棧，輕輕松松，無需考慮太多因素，即可實現(xiàn)。

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比高陽網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式高陽網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋高陽地區(qū)。費用合理售后完善，10年實體公司更值得信賴。

現(xiàn)在，要求在一個數(shù)組里實現(xiàn)兩個棧，那么在數(shù)組里怎么實現(xiàn)棧呢？

無非就是下標(biāo)索引，方法也不局限一種，例如：用奇數(shù)下標(biāo)作為棧s1的結(jié)構(gòu)，用偶數(shù)作為s2的結(jié)構(gòu)；再者：一前一后的結(jié)構(gòu)，棧s1從前往后，棧s2從后往前。

本人只想到了使用這兩中方法實現(xiàn)，當(dāng)然，這兩種方法各有利弊。

第一種方法，倘若其中一個棧只入了一個元素，而另一個入了很多元素，那么會造成內(nèi)存碎片，但是此方法有利于數(shù)組增容；

第二種方法，空間利用率很高，但是不有利于數(shù)組增容。

雖然各有利弊，但是實現(xiàn)的機(jī)制相同。

在這里，使用第一種方法實現(xiàn)：

#include <iostream>
using namespace std;

template <class T>
class arrayWithTwoStack
{
public:
    arrayWithTwoStack(int size)
        : top1(-1)
        , top2(-1)
        , _size(size)
    {
        _array = new T[size + 1];
    }

    ~arrayWithTwoStack()
    {
        if (_array)
        {
            delete[] _array;
        }
    }

public:
    void Push(int index, T data)
    {
        if (_size % 2 == 0)
        {
            if ((top1 > _size - 2) || (top2 >= _size - 1))
            {
                cout << "Stack is overflow!" << endl;
                return;
            }
        }
        else
        {
            if ((top1 > _size - 1) || (top2 >= _size - 2))
            {
                cout << "Stack is overflow!" << endl;
                return;
            }
        }

         0是一號棧， 1是二號棧
        if (index == 0)
        {
            if (top1 == -1)
            {
                top1 = 0;
                _array[top1] = data;
            }
            else
            {
                top1 += 2;
                _array[top1] = data;
            }
        }

        if (index == 1)
        {
            if (top2 == -1)
            {
                top2 = 1;
                _array[top2] = data;
            }
            else
            {
                top2 += 2;
                _array[top2] = data;
            }
        }
    }

    T Pop(int index)
    {
        int ret;
        if (index == 0)
        {
            if (top1 < 0)
            {
                return -1;
                cout << "Stack is underflow!" << endl;
            }
            else
            {
                ret = _array[top1];
                top1 -= 2;
            }
        }
        if (index == 1)
        {
            if (top2 < 1) // top2從下標(biāo)為1開始
            {
                return -1;
                cout << "Satck is underflow!" << endl;
            }
            else
            {
                ret = _array[top2];
                top2 -= 2;
            }
        }
        return ret;
    }

    T top(int index) // 返回棧頂元素
    {
        if (index == 0 && top1 >= 0)
        {
            return _array[top1];
        }

        if (index == 1 && top2 >= 1)
        {
            return _array[top2];
        }

        cout << "No Top!" << endl;
        exit(0);
    }

    bool isEmpty(int index)
    {
        if (index == 0 && top1 < 0)
            return false;
        if (index == 1 && top2 < 1)
            return false;

        return true;
    }

    void Show()
    {
        if (top1 < 0 && top2 < 1)
        {
            cout << "Stack has no data!" << endl;
            return;
        }
        else
        {
            for (int i = 0; i < _size; i++)
                cout << _array[i] << " ";
        }
        cout << endl;
    }

private:
    T top1;
    T top2;
    int _size;
    T* _array;

};


int main()
{
    arrayWithTwoStack<int> s(10);

    s.Push(0, 0);
    s.Push(0, 2);
    s.Push(0, 4);
    s.Push(1, 1);
    s.Push(1, 3);
    s.Push(1, 5);
    s.Push(1, 7);
    s.Push(0, 6);
    s.Push(0, 8);
    s.Push(1, 9);
    s.Push(0, 10);

    s.Show();

    cout << s.Pop(0) << " ";
    cout << s.Pop(0) << " ";
    cout << s.Pop(0) << " ";
    cout << s.Pop(0) << endl;
    cout << s.Pop(1) << " ";
    cout << s.Pop(1) << " ";
    cout << s.Pop(1) << " ";
    cout << s.Pop(1) << endl;

    cout << s.top(0) << endl;
    cout << s.top(1) << endl;

    s.Pop(0);
    cout << (s.isEmpty(0) ?  "Yes" : "No") << endl;
    cout << (s.isEmpty(1) ? "Yes" : "No") << endl;

    system("pause");
    return 0;
}

若有紕漏，歡迎指正。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文題目：【數(shù)據(jù)結(jié)構(gòu)】一個數(shù)組實現(xiàn)兩個棧【面試】-創(chuàng)新互聯(lián)
本文鏈接：http://www.chinadenli.net/article0/coepio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、網(wǎng)站維護(hù)、ChatGPT、Google、小程序開發(fā)、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)