目錄：資料結構系列文章

堆疊(Stack)是一種Last-In-First-Out的資料結構
最晚進入Stack的資料會最先被取出
最早進入Stack的資料則最晚被取出
簡單來說就是像一個容器或是放書本的箱子
只能從上面拿出來，只能從上面放進去

使用c++實作

使用陣列實作

最重要的想法就是當目前配置的陣列空間如果不足時
另外new一個大小是原本兩倍的空間
再取代掉原本的陣列

#include <iostream>
using namespace std;

template <typename T>
class StackArray
{
public:
    StackArray() : top(-1), capacity(1)
    {
        ptr = new T[capacity];
    }
    void Push(T data) // 把資料放到頂端
    {
        if (top == capacity - 1) // 如果配置空間不足，把配置陣列大小變為2倍再放資料
        {
            DoubleCapacity();
        }
        ptr[++top] = data;
    }
    void Pop() // 把頂端的資料移除
    {
        if (isEmpty())
        {
            cout << "Stack is empty." << endl;
        }
        else
        {
            top--; // 只需要把top減1就行，因為之後如果有資料Push進來，會直接覆蓋掉原本的，不須花費成本再delete跟new
        }
    }
    bool isEmpty() // 回傳Stack是否為空
    {
        return (top == -1);
    }
    T Top() // 回傳頂端的資料
    {
        if (isEmpty())
        {
            cout << "Stack is empty." << endl;
            return 0; // 回傳0是因為不知道T是什麼型態，如果回傳別的數值會很容易出錯
        }
        return ptr[top];
    }
    int getSize() // 回傳Stack大小
    {
        return top + 1;
    }

private:
    int top;              // 最頂端的index
    int capacity;         // 目前配置空間的大小
    int *ptr;             // 目前配置的陣列(第一個元素的指標)
    void DoubleCapacity() // 把配置的陣列變成兩倍的大小
    {
        capacity *= 2;
        int *newptr = new int[capacity];
        for (int i = 0; i < capacity / 2; i++) // 把舊的陣列裡的資料複製到新的陣列
        {
            newptr[i] = ptr[i];
        }
        delete[] ptr;
        ptr = newptr;
    }
};

int main()
{
    StackArray<int> s;
    s.Pop();
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(2);
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(4);
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(6);
    cout << s.Top() << " " << s.getSize() << endl;
    s.Pop();
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Pop();
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(8);
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(10);
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Pop();
    cout << s.Top() << " " << s.getSize() << endl;
    cout << s.isEmpty() << endl;
    return 0;
}

output:

Stack is empty.
1
Stack is empty.
0 0
0
2 1
4 2
6 3
0
4 2
2 1
8 2
0
10 3
8 2
0

使用鏈結串列實作

既然要用LinkList實作，那我們就使用class的繼承
把上一篇的class做一些修改後獨立寫成
SinglyLinkedList.h 再做繼承

#include <iostream>
using namespace std;

template <typename T>
class SinglyLinkedList; // 為了將class SinglyLinkedList設成class ListNode的friend，必須先宣告

template <typename T>
class ListNode
{
public:
    ListNode(T x) : value(x), next(0) {} // 使用c++的成員初始化串列，將value初始化為x，next初始化為0
private:
    T value;
    ListNode<T> *next;
    friend class SinglyLinkedList<T>; // 將class SinglyLinkedList宣告為friend，讓class SinglyLinkedList可以存取ListNode的private成員
};

template <typename T>
class SinglyLinkedList
{
public:
    SinglyLinkedList() : head(0), size(0) {}
    int getSize() // 回傳list資料個數
    {
        return size;
    }
    bool isEmpty() // 回傳list是否為空
    {
        return head == 0;
    }

protected: // 設為protected是因為不想讓非成員函式可以存取到
    ~SinglyLinkedList()
    {
        ListNode<T> *current = head;
        while (current != 0)
        {
            ListNode<T> *NextNode = current->next;
            delete current;
            current = NextNode;
        }
        head = 0; // 當指標被delete後, 將其指向NULL, 可以避免不必要bug
    }
    void PushFront(T data) // 在list的最前端塞入資料
    {
        ListNode<T> *NewNode = new ListNode<T>(data);
        if (head == 0)
        {
            head = NewNode;
        }
        else
        {
            NewNode->next = head;
            head = NewNode;
        }
        ++size;
    }
    void PopFront() // 移除list中的第一個資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else
        {
            ListNode<T> *NextNode = head->next;
            delete head;
            head = NextNode;
        }
        --size;
    }
    T getHead() // 回傳第一個資料
    {
        if (isEmpty())
        {
            cout << "List is empty." << endl;
            return 0;
        }
        else
        {
            return head->value;
        }
    }

private:
    ListNode<T> *head;
    int size;
};

#include <iostream>
#include "SinglyLinkedList.h"
using namespace std;

template <typename T>
class StackList : public SinglyLinkedList<T> // 繼承類別
{
public:
    void Push(T data) // 把資料放到頂端
    {
        SinglyLinkedList<T>::PushFront(data); // 存取父類別的private成員語法，當然你也可以把要存取的成員設成protected就能直接存取
    }
    void Pop() // 把頂端的資料移除
    {
        SinglyLinkedList<T>::PopFront();
    }
    T Top() // 回傳頂端的資料
    {
        return SinglyLinkedList<T>::getHead();
    }
};

int main()
{
    StackList<int> s;
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(2);
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(4);
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(6);
    cout << s.Top() << " " << s.getSize() << endl;
    s.Pop();
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Pop();
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(8);
    cout << s.Top() << " " << s.getSize() << endl;
    s.Push(10);
    cout << s.isEmpty() << endl;
    cout << s.Top() << " " << s.getSize() << endl;
    s.Pop();
    cout << s.Top() << " " << s.getSize() << endl;
    cout << s.isEmpty() << endl;
    return 0;
}

output:

List is empty.
1
List is empty.
0 0
0
2 1
4 2
6 3
0
4 2
2 1
8 2
0
10 3
8 2
0

使用python實作

最簡單的方法當然就是用串列啦~真輕鬆

class Stack:
    def __init__(self):
        self.stack = []  # 使用串列來實作
        self.size = 0

    def Push(self, data):  # 把資料放到頂端
        self.stack.append(data)  # append函式 把資料加進串列的末端
        self.size += 1

    def Pop(self):  # 把頂端的資料移除
        if self.size == 0:
            print("Stack is empty.")
        else:
            self.stack.pop()  # pop函式 把串列的最後一個元素移除
            self.size -= 1

    def Top(self):  # 回傳頂端的資料
        if self.size == 0:
            print("Stack is empty.")
            return 0
        else:
            return self.stack[self.size - 1]

    def isEmpty(self):  # 回傳Stack是否為空
        return self.size == 0

    def getSize(self):  # 回傳Stack大小
        return self.size


def main():
    s = Stack()
    s.Pop()
    print(s.isEmpty())
    print(s.Top())
    print(s.getSize())
    s.Push(2)
    print(s.isEmpty())
    print(s.Top())
    print(s.getSize())
    s.Push(4)
    print(s.Top())
    print(s.getSize())
    s.Push(6)
    print(s.Top())
    print(s.getSize())
    s.Pop()
    print(s.isEmpty())
    print(s.Top())
    print(s.getSize())
    s.Pop()
    print(s.Top())
    print(s.getSize())
    s.Push(8)
    print(s.Top())
    print(s.getSize())
    s.Push(10)
    print(s.isEmpty())
    print(s.Top())
    print(s.getSize())
    s.Pop()
    print(s.Top())
    print(s.getSize())
    print(s.isEmpty())


if __name__ == "__main__":
    main()

output:

Stack is empty.
True
Stack is empty.
0
0
False
2
1
4
2
6
3
False
4
2
2
1
8
2
False
10
3
8
2
False

上一篇：資料結構 鏈結串列(Linked List)

下一篇：資料結構 佇列(Queue)