【資料結構】堆疊的實作——順序堆疊和鏈堆疊

一、堆疊的定義

定義：限定只在表的一端(表尾)進行插入和洗掉的線性表

特點：后進先出

二、順序堆疊

基于陣列實作

C++實作代碼：

//頭檔案
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

//堆疊的最大存盤
const int MAX_SIZE=100;
//定義一個順序堆疊類(使用模板) 
//使用模板 優點 可以用來實作多種資料型別的存盤
template <class DataType> class Stack{

private:
    DataType *data; //資料域
    int size;       //堆疊的大小
    int top;		//堆疊頂下標
public:
    Stack();
    Stack(int s);
    //~Stack();
    void push(DataType t);  //進堆疊
    DataType pop();         //出堆疊 回傳堆疊頂元素
    DataType getTop();       //回傳堆疊頂元素 不出堆疊
    int length();           //求出堆疊的長度
    void setNull();         //將堆疊置空

    class Empty{};          //定義空類 用于拋例外
    class Full{};

    bool isFull();          //判斷堆疊是否已滿
    bool isEmpty();         //判斷堆疊是否為空

};

typedef Stack<char> CharStack;
typedef Stack<int> IntStack;
#endif // STACK_H_INCLUDED

//.cpp檔案
#include "Stack.h"

//無參構造 堆疊的大小為最大存盤
template <class DataType> Stack<DataType>::Stack(){
    size=MAX_SIZE;
    top=-1;
    data=new DataType[MAX_SIZE];
}

//有參構造 堆疊的大小給定
template <class DataType> Stack<DataType>::Stack(int s){
    size=s;
    top=-1;
    data=new DataType[size];
}

template <class DataType> bool Stack<DataType>::isFull(){
    if(top+1==size){
        return true;
    }else{
        return false;
    }
}

template <class DataType> bool Stack<DataType>::isEmpty(){
    if(top==-1){
        return true;
    }else{
        return false;
    }
}

//壓堆疊 先判斷堆疊是否已滿 然后將top++
template <class DataType> void Stack<DataType>::push(DataType e){
    if(isFull()){
        throw Stack<DataType>::Full();
    }else{
        data[++top]=e;
    }
}

//彈出 先判斷堆疊是否為空 然后top--
template <class DataType> DataType Stack<DataType>::pop(){
    if(isEmpty()){
        throw Stack<DataType>::Empty();
    }else{
        return data[top--];
    }
}

//得到堆疊頂元素 不彈出
template <class DataType> DataType Stack<DataType>::getTop(){
    if(isEmpty()){
        throw Stack<DataType>::Empty();
    }else{
        return data[top];
    }
}

//堆疊的長度
template <class DataType> int Stack<DataType>::length(){
    return top+1;
}

//將堆疊清空
template <class DataType> void Stack<DataType>::setNull(){
    top=-1;
}


template class Stack<char>;
template class Stack<int>;

//主函式
#include <iostream>
#include "Stack.h"
#include "Sta.cpp"
using namespace std;

//順序堆疊
int main(){

    CharStack charStack;
    IntStack intStack(3);
    try{
    intStack.push(2);
    intStack.push(60);
    intStack.push(100);
    cout<<"堆疊的長度："<<intStack.length()<<endl;
    }catch(IntStack::Full){
      cout<<"STACK FULL!"<<endl;
    }
    try{
    intStack.pop();
    }catch(IntStack::Empty){
      cout<<"STACK EMPTY!"<<endl;
    }
    cout<<"堆疊的長度："<<intStack.length()<<endl;
    return 0;
}

三、鏈堆疊

基于鏈表實作(不帶頭節點)

#ifndef LINKSTACK_H_INCLUDED
#define LINKSTACK_H_INCLUDED

template <typename DataType>
struct Node{
    DataType data; //資料域
    Node<DataType> *next;  //指標域
};

template <typename DataType>
class LinkStack{
private:
        Node<DataType> *top; //堆疊頂指標
public:
    LinkStack();
    ~LinkStack();
    void push(DataType x);
    DataType pop();
    DataType getTop();
    bool isEmpty();
    bool isFull();
};

typedef LinkStack<char> CharLinkStack;
typedef LinkStack<int> IntLinkStack;
#endif // LINKSTACK_H_INCLUDED

#include "LinkStack.h"

//建構式 創建top指標
template <class DataType> LinkStack<DataType>::LinkStack(){
    top=NULL;
}
//解構式 釋放資源
template <class DataType>LinkStack<DataType>::~LinkStack(){
    Node<DataType> *p=NULL;
    while(top!=NULL){
        p=top->next;
        delete top;
        top=p;
    }
}
//判斷鏈堆疊是否為空
template <class DataType> bool LinkStack<DataType>::isEmpty(){
        if(top==NULL){
            return true;
        }else{
            return false;
        }
}
/*template <class DataType> bool LinkeStack<DataType>::isFull(){

}*/
//壓入元素
template <class DataType> void LinkStack<DataType>::push(DataType x){
            Node<DataType> *s=new Node<DataType>; //新定義一個Node結點指標
            s->data=x;
            s->next=top;      //將結點的指標域指向堆疊頂top(即壓入了一個新的元素)
            top=s;             //再讓top指向結點
        }

//彈出堆疊頂元素
template <class DataType> DataType LinkStack<DataType>::pop(){
        if(isEmpty()){
            throw "鏈堆疊為空，無法彈出元素";
        }else{
            DataType x=top->data;
            Node<DataType> *p=new Node<DataType>;
            p=top;      //將堆疊頂指標先賦給p
            top=top->next;  //堆疊頂指標指向堆疊頂的下一個存盤空間(即堆疊頂元素彈出)
            delete p;       //銷毀p的空間
            return x;
        }
}

//回傳堆疊頂元素
template <class DataType> DataType LinkStack<DataType>::getTop(){
           return top->data;
}


template class LinkStack<char>;
template class LinkStack<int>;

#include <iostream>
#include "LinkStack.cpp"
using namespace std;

//鏈堆疊
int main()
{
    IntLinkStack intLinkStack;
    intLinkStack.push(20);
    intLinkStack.push(15);
    cout<<"堆疊頂元素："<<intLinkStack.getTop()<<endl;
    intLinkStack.pop();
    cout<<"堆疊頂元素："<<intLinkStack.getTop()<<endl;
    return 0;
}

注意：

• C++分檔案撰寫時需要在 .h中尾部加入代碼，相當于為每個型別的模板定義了一個型別

typedef Stack<char> CharStack;

• .cpp檔案中尾部加入代碼，顯示的宣告要使用的模板類實體

 template class Stack<char>;

• main 函式中實體化類物件

CharStack charStack;

• 利用模板實作，每個類的方法前都要加上

template <class DataType>