资料结构 堆叠(Stack)

目录：资料结构系列文章

堆叠(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.1Stack is empty.0 002 14 26 304 22 18 2010 38 20

使用链结串列实作

既然要用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初始化为0private:    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.1List is empty.0 002 14 26 304 22 18 2010 38 20

使用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.sizedef 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.TrueStack is empty.00False214263False422182False10382False

上一篇：资料结构 链结串列(Linked List)

下一篇：资料结构 伫列(Queue)