主題

資料結構筆記:以list實現Stack堆疊

huninm | 2023-10-17 12:07:49 | 巴幣 0 | 人氣 94

這次使用list實現Stack堆疊會直接使用STL

所以要先呼叫這個函式庫

#include <list>

因為是使用List實現，不同於使用陣列，列表能夠自由的刪除元素或插入元素，所以只要創建名為stack的list容器和紀錄容量的capacity就可以了。

private:
list<DataType> stack;
int capacity;

使用list實現最直接的好處就是靠著list的STL就能夠實現Stack的多數功能

回傳stack目前大小的size()可以用list的size()實現

檢查目前容器是否為空、是否已滿的isEmpty()和isFull()都能用list的size()回傳list中元素數量和stack紀錄的容量對比實現。

    int size()
    {
        return stack.size();
    }
    bool isEmpty()
    {
        if (stack.size() == 0)
            return true;
        else
            return false;
    }
    bool isFull()
    {
        int temp = stack.size();
        if (temp == capacity)
            return true;
        else
            return false;
    }

最後就是實現push() pop() peek()三個功能

要完成stack的push()功能需要使用到list的push_front()功能，這個函式能直接在list的頭部插入一個元素，就跟堆疊從容器頂部放入元素的概念一樣，最早放進去的元素在最底層，最晚放進去的元素在頂層，然後實現pop()功能，先用front()將一個變數temp存入list的頭元素再用pop_front()刪除，每次呼叫pop都是拿出最頂層的元素，也是最晚進去的元素，這就是先進後出(First In Last Out,FILO)

最後的 peek()就是單純的查看最頂層的內容return stack.front();就能解決

    void push(DataType content)
    {
        if (isFull())
        {
            exit(EXIT_FAILURE);
        }
        stack.push_front(content);
    }
    DataType pop()
    {
        if (isEmpty())
        {
            exit(EXIT_FAILURE);
        }
        DataType temp = stack.front();
        stack.pop_front();
        return temp;
    }
    DataType peek()
    {
        return stack.front();
    }

以下是完整程式碼

#include <iostream>
#include <cstdlib>
#include <list>
using namespace std;

template <class DataType>
class Stack
{
private:
    list<DataType> stack;
    int capacity;

public:
    Stack(int size)
    {
        capacity = size;
    } // constructor
    ~Stack()
    {
        stack.clear();
    } // destructor

    void push(DataType content)
    {
        if (isFull())
        {
            exit(EXIT_FAILURE);
        }
        stack.push_front(content);
    }
    DataType pop()
    {
        if (isEmpty())
        {
            exit(EXIT_FAILURE);
        }
        DataType temp = stack.front();
        stack.pop_front();
        return temp;
    }
    DataType peek()
    {
        return stack.front();
    }
    int size()
    {
        return stack.size();
    }
    bool isEmpty()
    {
        if (stack.size() == 0)
            return true;
        else
            return false;
    }
    bool isFull()
    {
        int temp = stack.size();
        if (temp == capacity)
            return true;
        else
            return false;
    }
};

int main()
{
    Stack<int> pt(3);

    pt.push(1);
    pt.push(2);

    pt.pop();
    pt.pop();

    pt.push(3);

    cout << "The top element is " << pt.peek() << endl;
    cout << "The stack size is " << pt.size() << endl;

    pt.pop();

    if (pt.isEmpty())
    {
        cout << "The stack is empty\n";
    }
    else
    {
        cout << "The stack is not empty\n";
    }

    return 0;
}

##兒少適宜 #資料結構 #菜鳥筆記