栈是典型的LIFO(Last In First Out)结构;
对一个栈来说，入栈的时候只能把新的元素添加到栈顶， 出栈的时候只能从栈顶弹出；好比装羽毛球的桶，装羽毛球的时候，只能从最上面把羽毛球装入，取球的时候只能从最上面取出
这里用链表形式来实现栈的结构，栈的每个储存单元由一个类node来实现, 为了便于阅读，不用类模板，用int型
1 class node{ 2 public: 3 int val; 4 node *next; 5 node(int x=0){val = x; next = NULL;} 6 };
一个结点包括该结点的值和指向下一个结点的指针
一个栈的常见操作有：出栈，压栈，删除结点，获取栈顶，获取栈的大小, 为了方便检验栈的实验的正确性，还有一个遍历程序；
栈的一个简单结构如下，这个实现肯定存在一定的缺陷，请大家指正
1 class stack{ 2 public: 3 stack(){} 4 int GetSize(){return size;} 5 int GetTop(){if(top==NULL) return -999999; else return top->val;} 6 bool deleteNode(node* n); 7 bool isEmpty(){return size == 0;} 8 void pop(); 9 void push(); 10 void clear(); 11 void traverse(); 12 private: 13 node* top; 14 int size; 15 node* GetPre(node* n); 16 };
分别来实现栈最常用的两个功能：压栈：push， 出栈：pop
1 node* stack::push(int val){ 2 size++; //每次压栈，栈的大小增加1 3 if(top == NULL){ //栈为空栈的时候，建立新的结点并让栈顶top指向该结点 4 top = new node(val); 5 return top; 6 }//更新栈顶 7 node* temp = new node(val); 8 temp->next = top; 9 top = temp; 10 return top; 11 }
1 void stack::pop(){ 2 if(top == NULL) return; 3 node* temp = top; //让栈顶指向栈顶的下一个结点，并把原来的栈顶置空，就实现栈顶的弹出 4 top = top->next; 5 temp = NULL; 6 size--;//每弹出一次，栈的大小减小1 7 }
删除结点是栈里面相对复杂的一种操作，要考虑删除结点的位置，以及要删除的结点是否存在
1 bool stack::deleteNode(node* n){ 2 node* temp = top; 3 bool flag = false; 4 while(temp){ 5 if(temp == n){ 6 size--; 7 flag = true; //标志要删除的结点是否在栈中 8 if(temp == top) { 9 top = top->next; 10 break; 11 } 12 else{//找到要删除结点的前驱，并使其指向要删除结点的后驱，这里存在一个缺陷就是没有在内存中删除掉这个结点，只实现了在栈中删除这个结点，但是依然占用内存 13 node* pre = GetPre(temp); 14 pre->next = temp->next; 15 break; 16 } 17 } 18 temp = temp->next; 19 }21 return flag; 22 }
整个程序的实现：
1 #include<iostream> 2 using namespace std; 3 class node{ 4 public: 5 int val; 6 node* next; 7 node(int x=0){val = x; next = NULL;} 8 }; 9 10 class stack{ 11 public: 12 void pop(); 13 node* push(int val); 14 void traverse(); 15 void clear(); 16 bool deleteNode(node* n); 17 stack(){size = 0; top = NULL;} 18 node* GetTop(){return top;} 19 int GetSize(){return size;} 20 bool isEmpty(){return size == 0;} 21 private: 22 node* top; 23 int size; 24 node* GetPre(node* n); 25 }; 26 27 void stack::pop(){ 28 if(top == NULL) return; 29 node* temp = top; 30 top = top->next; 31 temp = NULL; 32 size--; 33 } 34 35 node* stack::push(int val){ 36 size++; 37 if(top == NULL){ 38 top = new node(val); 39 return top; 40 } 41 node* temp = new node(val); 42 temp->next = top; 43 top = temp; 44 return top; 45 } 46 47 void stack::traverse(){ 48 if(top == NULL) { 49 cout<<"stack is empty!"<<endl; 50 return; 51 } 52 node* temp = top; 53 cout<<"the size of this stack is: "<<size<<endl<<"stack is as follows: "; 54 while(temp){ 55 cout<<temp->val<<" "; 56 temp = temp->next; 57 } 58 cout<<endl; 59 } 60 61 void stack::clear(){ 62 node* temp; 63 size = 0; 64 while(top){ 65 temp = top; 66 top = top->next; 67 temp = NULL; 68 } 69 } 70 71 node* stack::GetPre(node* n){ 72 if(n == NULL) { 73 cout<<"this node has is NULL!"<<endl; 74 return NULL; 75 } 76 if(n == top){ 77 cout<<"this node has no pre node!"<<endl; 78 return NULL; 79 } 80 node* temp = top; 81 while(temp->next){ 82 if(temp->next == n) 83 return temp; 84 } 85 cout<<"this node does not exist in the stack!"<<endl; 86 return NULL; 87 } 88 89 90 91 bool stack::deleteNode(node* n){ 92 node* temp = top; 93 bool flag = false; 94 while(temp){ 95 if(temp == n){ 96 size--; 97 flag = true; 98 if(temp == top) { 99 top = top->next; 100 break; 101 } 102 else{ 103 node* pre = GetPre(temp); 104 pre->next = temp->next; 105 break; 106 } 107 } 108 temp = temp->next; 109 } 110 if(!flag) cout<<"this node does not exist!"<<endl; 111 return flag; 112 } 113 114 int main(){ 115 stack s; 116 cout<<"检测压栈功能"<<endl; 117 cout<<"压入1，2，3"<<endl; 118 s.push(1); 119 s.push(2); 120 s.push(3); 121 s.traverse(); 122 cout<<"检测出栈功能"<<endl; 123 s.pop(); 124 s.traverse(); 125 cout<<"清除这个栈"<<endl; 126 s.clear(); 127 s.traverse(); 128 cout<<"压入1，2，3，4，5"<<endl; 129 s.push(1); 130 s.push(2); 131 s.push(3); 132 s.push(4); 133 s.push(5); 134 s.traverse(); 135 cout<<"删除第二个结点"<<endl; 136 s.deleteNode(s.GetTop()->next); 137 s.traverse(); 138 return 0;}
检验是否正确，检测不是很严谨，只实现了基本的功能
