データ構造C++実現---スタック

1:C++を利用してStackを実現するには二つの方案がある.
一つはチェーンテーブルで、二つは配列である.

#include <iostream> 
using namespace std; 
 
typedef int T; 
 
//    
class LinkedList 
{ 
    struct Node 
    { 
        T data; 
        Node* next; 
        //   data next        
        Node(const T& t=T()):data(t),next(NULL) 
        { 
        } 
    }; 
public: 
    //           
    LinkedList():head(NULL) 
    { 
    } 
    ~LinkedList() 
    { 
        clear(); 
    } 
 
    void clear() 
    { 
        Node *p=head; 
        while (p!=NULL) 
        { 
            Node *q = p->next; 
            delete p;//  p     
            p=q; 
        } 
    } 
    //  empty  size    (travel) 
    bool empty() 
    { 
        //                    
        return head==NULL ? true : false; 
    } 
    unsigned int size() 
    { 
        unsigned int size=0; 
        Node* p =head; 
        while (p!=NULL) 
        { 
            size++; 
            p=p->next; 
        } 
        return size; 
    } 
 
    void travel() 
    { 
        //  while         ，     NULL   
        Node* p = head; 
        while (p!=NULL) 
        { 
            cout<<p->data<<endl; 
            p=p->next; 
        } 
    } 
    // (insertAfter insertFront)   (find) 
    void insertFront(const T& t) 
    { 
        Node* p = new Node(t); 
        p->next=head;  //           p next 
        head = p;       // *p    
    } 
    void insertAfter(const T& t) 
    { 
        Node *p = new Node(t); 
        Node *tail = getPointer(size()-1); 
        tail->next = p; 
    } 
    void erase(const T& t) 
    { 
        unsigned int position = find(t); 
        Node* cur = getPointer(position); 
        if (position!=0) 
        { 
            Node* pre = getPointer(find(t)-1); 
            pre->next = cur->next; 
        }else{ 
            head = cur->next; 
        } 
        delete cur; 
    } 
    void update(const T& t,const T& target) 
    { 
        Node *p=getPointer(find(target)); 
        p->data=t; 
    } 
    unsigned int  find(const T& t) 
    { 
        unsigned int position=0; 
        Node* p = head; 
        while(p!=NULL) 
        { 
            if (p->data==t) 
            { 
                return position; 
            } 
            p=p->next; 
            position++; 
        } 
        return position; 
    } 
 
    //        
    T getHead() 
    { 
        return head->data; 
    } 
    T getTail() 
    { 
        Node *p=getPointer(this->size()-1); 
        return p->data; 
    } 
    //               
    Node* getPointer(int position) 
    { 
        Node* p =head; 
        for(int i = 0;i<position;i++) 
        { 
            p=p->next; 
        } 
        return p; 
    } 
private: 
    //           
    Node* head;  
}; 
 
class Stack 
{ 
public: 
    //       （ clear）   (push)   pop   top      empty 
    Stack() 
    { 
        list = new LinkedList; 
    } 
    ~Stack() 
    { 
        clear(); 
    } 
    void clear() 
    { 
        list->clear(); 
    } 
    void push(const T& t) 
    { 
        list->insertFront(t); 
    } 
    void pop() 
    { 
        list->erase(list->getHead()); 
    } 
    T top() 
    { 
        return list->getHead(); 
    } 
    unsigned int size() 
    { 
        return list->size(); 
    } 
    bool empty() 
    { 
        return list->empty(); 
    } 
 
private: 
    LinkedList* list; 
}; 
 
int main() 
{ 
    Stack s; 
    s.push(1); 
    s.push(2); 
    cout<<s.size()<<endl;  
    system("pause"); 
    return 0; 
} 

 
 
二:配列で実現する:
技巧:numと下标の间の関系を探し当てて、核心はnum numが配列を制御しているのが添削して调べる核心で、要素、弾き出すのは-1で、添加した后に+1します

#include <iostream> 
#include <string> 
using namespace std; 
 
typedef string T; 
class Stack 
{ 
public: 
    Stack() 
    { 
        num=0; 
    } 
    ~Stack(){clear();} 
 
    //   
    void clear() 
    { 
        num=0; 
    } 
    //    
    void push(const T& t) 
    { 
        /*arr[num]=t; 
        num++；    */ 
        arr[num++]=t; 
    } 
    void pop() 
    { 
        num--; 
    } 
    T top() 
    { 
        return arr[num-1]; 
    } 
    //     
    unsigned int size() 
    { 
        return num; 
    } 
    bool empty() 
    { 
        return num==0; 
    } 
private: 
    T arr[10]; 
    unsigned int num; 
};