91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

【數據結構】 一個數組實現兩個棧【面試】

發布時間:2020-07-15 18:44:13 來源:網絡 閱讀:709 作者:Vs呂小布 欄目:編程語言

以前,我們實現一個棧,輕輕松松,無需考慮太多因素,即可實現。

現在,要求在一個數組里實現兩個棧,那么在數組里怎么實現棧呢?

無非就是下標索引,方法也不局限一種,例如:用奇數下標作為棧s1的結構,用偶數作為s2的結構;再者:一前一后的結構,棧s1從前往后,棧s2從后往前。


【數據結構】 一個數組實現兩個棧【面試】


本人只想到了使用這兩中方法實現,當然,這兩種方法各有利弊。

第一種方法,倘若其中一個棧只入了一個元素,而另一個入了很多元素,那么會造成內存碎片,但是此方法有利于數組增容;

第二種方法,空間利用率很高,但是不有利于數組增容。

雖然各有利弊,但是實現的機制相同。


在這里,使用第一種方法實現:

#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從下標為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;
}

若有紕漏,歡迎指正。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

隆回县| 抚顺市| 海原县| 大石桥市| 宽甸| 双城市| 思茅市| 抚顺市| 长寿区| 竹北市| 芮城县| 休宁县| 淮阳县| 益阳市| 隆昌县| 千阳县| 永靖县| 武定县| 莫力| 景洪市| 明水县| 洪洞县| 溧水县| 全南县| 汾西县| 股票| 南宁市| 沂水县| 东乡| 嘉鱼县| 黄骅市| 灵山县| 北京市| 峡江县| 麻江县| 库伦旗| 石首市| 乐都县| 天镇县| 绩溪县| 嘉祥县|