http://www.cnblogs.com/jingliming/p/4602458.html
棧是一種限定只在表尾進行插入或刪除操作,棧也是線性表表頭稱為棧的底部,表尾稱為棧的頂部,表為空稱為空棧，棧又稱為后進先出的線性表,棧也有兩種表示:順序棧與鏈式棧順序棧是利用一組地址連續的存儲單元，依次存放從棧底到棧頂的數據元素,附設一個指針指示棧頂的元素在棧中的位置。
? ? ?
1 //順序棧的實現 2 #define INFINITY 65535 3 #define MAXSIZE 1000 4 #define ElemType int 5 6 typedef struct { 7 ElemType data[MAXSIZE]; //棧的大小 8 int top; //棧頂的游標 9 }Stack; 10 11 class ArraryStack{ 12 public: 13 void initStack(Stack *s); //初始化棧 14 15 bool isEmpty(Stack *s); //判斷棧是否為空 16 17 ElemType Top(Stack *s); //返回棧頂的元素 18 19 ElemType Pop(Stack *s); //返回并刪除棧頂的元素 20 21 void Push(Stack *s,ElemType e); //將元素e壓棧 22 23 void Print(Stack *s); //輸出從棧底到棧頂的元素 24 25 void Clear(Stack *s); //清空棧元素 26 27 }; 28 29 void ArraryStack::initStack(Stack *s) 30 { 31 s->top=-1; 32 } 33 34 bool ArraryStack::isEmpty(Stack *s) 35 { 36 if (s->top==-1) 37 { 38 return true; 39 } 40 return false; 41 } 42 43 ElemType ArraryStack::Top(Stack *s) 44 { 45 if (!isEmpty(s)) 46 { 47 return s->data[s->top]; 48 } 49 return INFINITY; 50 } 51 52 ElemType ArraryStack::Pop(Stack *s) 53 { 54 if (!isEmpty(s)) 55 { 56 return s->data[s->top--]; 57 } 58 return INFINITY; 59 } 60 61 void ArraryStack::Push(Stack *s,ElemType e) 62 { 63 if(s->top>=MAXSIZE-1) 64 return; 65 ++s->top; 66 s->data[s->top]=e; 67 68 } 69 70 void ArraryStack::Print(Stack *s) 71 { 72 for (int i=0;i<=s->top;i++) 73 { 74 printf("%d ",s->data[i]); 75 } 76 printf("\n"); 77 } 78 79 void ArraryStack::Clear(Stack *s) 80 { 81 s->top=-1; 82 }
?第二部分：鏈式棧的實現
1 //鏈式棧的聲明 2 template<typename T> 3 struct LinkNode{ 4 5 LinkNode* next; 6 T data; 7 }; 8 9 //鏈式棧的實現 10 template<typename T> 11 class LinkStack 12 { 13 public: 14 LinkStack(); 15 ~LinkStack(); 16 void Push(T value); 17 T Pop(); 18 T Top(); 19 int Size(); 20 bool isEmpty(); 21 22 private: 23 LinkNode<T> *pHead; 24 }; 25 26 template<typename T> 27 LinkStack<T>::LinkStack() 28 { 29 30 pHead=new LinkNode<T>; 31 if(pHead==NULL) 32 cout<<"構建頭結點空間失敗。"<<endl; 33 else 34 { 35 pHead->next=NULL; 36 pHead->data=NULL; 37 } 38 } 39 40 template<typename T> 41 LinkStack<T>::~LinkStack() 42 { 43 44 } 45 46 template<typename T> 47 void LinkStack<T>::Push(T value) 48 { 49 LinkNode<T> *p=new LinkNode<T>; 50 p->data=value; 51 p->next=pHead->next; 52 pHead->next=p; 53 } 54 55 template<typename T> 56 T LinkStack<T>::Pop() 57 { 58 T value; 59 LinkNode<T> *p=pHead->next; 60 if (p!=NULL) 61 { 62 value= p->data; 63 pHead->next=p->next; 64 delete p; 65 p=NULL; 66 return value; 67 } 68 else 69 { 70 71 cout<<"沒有結點"<<endl; 72 return NULL; 73 } 74 75 } 76 77 template<typename T> 78 T LinkStack<T>::Top() 79 { 80 LinkNode<T> *p=pHead->next; 81 if (p!=NULL) 82 { 83 T value=p->data; 84 return value; 85 } 86 else 87 { 88 89 cout<<"頭結點為空。"<<endl; 90 return NULL; 91 } 92 } 93 94 template<typename T> 95 int LinkStack<T>::Size() 96 { 97 int count=0; 98 LinkNode<T> *p=pHead->next; 99 while(p!=NULL) 100 { 101 102 ++count; 103 p=p->next; 104 } 105 return count; 106 } 107 108 template<typename T> 109 bool LinkStack<T>::isEmpty() 110 { 111 LinkNode<T> *p=pHead->next; 112 if (p==NULL) 113 { 114 return true; 115 } 116 return false; 117 }
測試用例：
1 int main() 2 { 3 LinkStack<int> sta; 4 sta.Push(1); 5 sta.Push(2); 6 sta.Push(3); 7 cout << "The size of the stack now is " << sta.Size() << endl; 8 sta.Pop(); 9 cout << "The top element is " << sta.Top() << endl; 10 cout << "The size of the stack now is" << sta.Size() << endl; 11 if (sta.isEmpty()) 12 { 13 cout << "This stack is empty." << endl; 14 } 15 else 16 { 17 cout << "This stack is not empty." << endl; 18 } 19 system("pause"); 20 return 0; 21 }
