本篇写了一段栈的代码，参考了很多人的代码，而且这段代码也完成了很久了。不过里面有很多细节耐人寻味。其实就是很多C++的知识不是很明白，毕竟栈的思想很简单。

栈

FILO(先进后出)总所周知。栈的实现可以用数组或链表，一个基本的栈应该具有入栈、出栈、判断栈空等功能。这里用链表来实现： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;
//符号的预处理
typedef int T;
typedef struct stack_node StackNode;
//链表节点
struct stack_node
{
	StackNode* next;
	T data;
};
//栈类
template <class T>
class Stack
{
protected:
	StackNode* top;
public:
	Stack();
	~Stack(){delete top;}
	bool IsEmpty() const{return top->next==NULL;}
	bool Pop(T& x);
	bool Push(const T& x);
};
/*
 * 出栈
 */
template <class T>
bool Stack<T>::Pop(T& x)
{
	if(IsEmpty() == true)
		return false;
	StackNode *p = top->next;
	x = p->data;					//数据弹出
	top->next = p->next;
	delete p;						//删除P节点
    p=NULL;
	return true;
}
/*
 * 入栈
 */
template <class T>
bool Stack<T>::Push(const T& x)
{
	StackNode *p = new StackNode;	//分配新的空间
	p->data = x;						//数据存入
	p->next = top->next;
	top->next = p;						//插到头点后
	return true;
}
/*
 * 初始化栈
 */
template <class T>
Stack<T>::Stack()
{
	top = new StackNode;		//栈顶分配空间
	top->next = NULL;						//栈指针域指向空
}
int main()
{
	Stack<int> L;
	for(int i=0; i<5; i++)
		L.Push(i);
	int temp;
	for(int i=0; i<5; i++)
	{
			L.Pop(temp);
			cout<<" "<<temp<<endl;
	}
	return 0;
}

C++

1
2
typedef int T;
template <class T>

这两行代码是为了扩展所需要的，这样我们可以很容易的修改栈元素的数据类型。 

1
2
3
4
Stack<int> L;
Stack<int>* p=NULL;
p=new Stack<int>();

第一行代码是创建了栈，后两行也达到该效果。但是第一行代表一个完整的 C+ + 类，类的生命周期结束,C+ + 会默认执行一系列操作（执行析构函数等）；后两行是指针操作，需要调用者手动释放内存等内存管理操作. 

1
2
bool Pop(T& x);
bool Push(const T& x);

这两行也有很多知识，首先是&，为什么不用指针;其实是const.下文来一一揭晓：
   对于引用，这里几乎都是值操作，使用指针反而有很多麻烦，但是我们又需要传入可以返回元素的值 ，当然引用是最好的选择了。
   对于const,是因为Push这个操作传入的值是不能改变的
最后推荐几篇c++的博客：
堆和栈的区别
C+ + 值传递、指针传递、引用传递详解