데이터 구조 - 스 택 (링크 설명)

스 택 은 자주 사용 하 는 데이터 구조 이다.스 택 이라는 데이터 구 조 는 배열 이나 링크 두 가지 방식 으로 설명 할 수 있 습 니 다. 지난 편 에 스 택 의 배열 설명 을 소 개 했 습 니 다. 여 기 는 예 를 들 어 스 택 의 링크 설명 을 소개 하고 스 택 링크 형식의 구축, 스 택 에 들 어가 고 스 택 에 나 가 는 등 기본 적 인 작업 을 소개 합 니 다.

//           ，   Item       ，   Stack ，      、  、  、      ，  Stack Item    。


#include <iostream>
using namespace std;
const int Size=5;
class Stack;
class Item
{
public:
    Item(const int& val):item(val){}    //      item     

private:
    int item;
    Item* next;
    friend class Stack;    //   Stack  Item    
};

class Stack
{
public:
    Stack():top(NULL){}   //           ，        
    ~Stack();                       //        
    int Pop();                      //  
    void Push(const int&);          //  
private:
    Item *top;
};

Stack::~Stack()                 
{
    Item *p=top,*q;
    while(p!=NULL)
    {
        q=p->next;     // p next  q， q        
        delete [] p;   //         p，  p      
        p=q;//  p      ，      ，          
    }
}

//           Item     ，Item      ， int item;   Item* next;               int item   
int Stack::Pop()                  //    ，         
{
    Item* temp;                   //        
    int ret;                      //       
    temp=top;                     // temp      

    ret=top->item;
    top=top->next;   // top      ， top       ，          
    delete temp;                  //          
    return ret;
}

void Stack::Push(const int& val)   //  （  ）  ，          
{
    Item* temp=new Item(val);      //        
    temp->next=top;                //     next      （  ）
    top=temp;                      //            
}


int main()
{
    Stack s;
    for(int i=1;i<Size;i++)
    s.Push(i);
    cout<<"The element of stack are: ";
    for(i=1;i<Size;i++)
    cout<<s.Pop()<<'\t';
    cout<<endl;
    return 0;
}