栈(stack) 是一种后进先出的数据结构。怎么理解呢?可以把栈理解为一个箱子，而箱子的容量仅供一本书放入或拿出。每次可以把一本书放在箱子的最上方，也可以把箱子最上方的书拿出，如图所示。
在图中，依次把1号书、2号书、3号数放入箱中，接下来再分别把3号书和2号书依次拿出，最后把4号书放入箱中。在这个过程中可以注意到，每次都只对栈顶(箱顶)的书进行操作(放入或拿出),满足了后放进的书先拿出的特点。例如，在把3号书放入箱中后，如果不把3号书先拿出，是不能拿出2号书和1号书的。
由上面的例子已经基本可以理解栈是什么了，这里再介绍一下栈顶指针。栈顶指针是始终指向栈的最上方元素的一个标记，当使用数组实现栈时，栈顶指针是一个int 型的变量(数组下标从0开始)，通常记为TOP；而当使用链表实现栈时，则是一个int*型的指针。在图中，从左至右每个操作之后，栈顶指针TOP的值分别为0、1、2、1、0、1,而栈中没有元素(即栈空)时令TOP为-1。
接下来讲解栈的一些常用操作,包含清空(clear)、获取栈内元素个数( size),判空( empty)、进栈(push)、 出栈(pop)、 取栈顶元素(top) 等。
下面将使用数组st[]来实现栈，而int 型变量TOP表示栈顶元素的下标( 数组下标从0开始)，这样栈空时TOP就是1。下面对常见操作进行示范实现：
(1)清空(clear) 栈的清空操作将栈顶指针TOP置为-I,表示栈中没有元素。
void clear() { TOP =-1; }(2)获取栈内元素个数(size) 由于栈顶指针TOP始终指向栈顶元素,而数组下标从0开始，因此栈内元素的数为TOP+1.
int size(){ return TOP +1; }(3)判空(empty) 由栈顶指针TOP的定义可知，仅当TOP=-I时为栈空，返回true;否则，返回false.
bool empty(){ if(TOP ==-1) return true; else return false; }(4)进栈(push) push(x)操作将元素x置于栈顶。由于栈顶指针TOP指向栈顶元素，因此需要先把TOP加1,然后再把x存入TOP指向的位置。
void push(int x) { st[++TOP]=x; }(5)出栈(pop) pop(操作将栈顶元素出栈，而事实上可以直接将栈顶指针TOP减1来实现这个效果。
void pop() { TOP--; }(6)取栈顶元素(top) 由于栈顶指针TOP始终指向栈顶元素，因此可以st[TOP]即为栈顶元素。
int top() { return st [TOP]; }需要特别注意的是，出栈操作和取栈顶元素操作必须在栈非空的情形下才能使用，因此在使用pop()函数和top()函数之前必须先使用empty()函数判断栈是否为空。 事实上,可以使用C++的STL中的stack容器来非常容易地使用栈。STL中的stack为实现好了栈的常用操作，当需要使用时只需要直接调用函数即可。
1. stack 的定义 要使用stack,应先添加头文件include <stack>,并在头文件下面加上“using namespacestd;",然后就可以使用了。 其定义的写法和其他STL容器相同，typename 可以任意基本数据类型或容器:
stack< typename > name;2. stack 容器内元素的访问 由于栈(stack)本身就是一种后进先出的数据结构，在STL的stack中只能通过top()来访问栈顶元素。 3. stack 常用函数实例解析 (1) push() push(x)将x入栈，时间复杂度为0(1). (2) top() top()获得栈顶元素，时间复杂度为O(1)。 (3) pop() pop()用以弹出栈顶元素，时间复杂度为O(1)。 (4) empty() empty()可以检测stack内是否为空，返回true为空，返回false 为非空，时间复杂度为O(1)。 (5) size() size()返回 stack内元素的个数，时间复杂度为0(1)。
最后需要指出，STL中没有实现栈的清空，所以如果需要实现栈的清空，可以用一个while循环反复pop出元素直到栈空。
while(!st.empty()){ st.pop(); }
