Stack是一个线性表，存储的数据是LIFO（last in first out）的
程序运行时局部变量存放在栈中，对象存放在堆（heap）中
一般说来，内存泄漏发生在堆中。
代码
/*用链表实现堆栈*/
#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class mystack
{
private:
int length;//数据总数
ListNode* tmp;//临时结点
ListNode* head;//头结点，即堆的top
public:
mystack();
void pop();//删除堆最上面的元素
void push(int x);//加入元素到堆栈里
bool isEmpty();//判断是否栈空
int top();//返回栈top元素
void clear();//清除栈中元素
};
mystack::mystack() :length(0), tmp(NULL), head(NULL) {};
void mystack::push(int x) {
tmp = new ListNode(x);
tmp->next = head;
head = tmp;
length++;
}
void mystack::pop() {
if (isEmpty()) {
return;
}
tmp = head;
head = head->next;
delete(tmp);
length--;
}
bool mystack::isEmpty() {
return length == 0;
}
int mystack::top() {
if (!isEmpty()) {
return head->val;
}
else {
return -1;
}
}
void mystack::clear() {
if (!isEmpty()) {
while (head) {
tmp = head;
head = head->next;
delete(tmp);
length--;
}
}
tmp = NULL;
head = NULL;
}
STL ——stack
- 头文件 #include <stack>
- c++ stl栈stack的成员函数 empty(),top(),size(),pop(),push()
后缀表达式
一般的表达式比如a+bc-d称为中缀表达式，形式如 num1 op1 num2 op2，运算符在字符中间
后缀表达式顾名思义，就是运算符在字符的后面，比如 a b c * + d -就是后缀表达式（即a + bc -d）
中缀->后缀的转化规则（用到栈）
| 表达式 | 栈 | 输出 |
|---|---|---|
| a+b*c-d$ | ||
| +b*c-d$ | a | |
| b*c-d$ | + | a |
| *c-d$ | + | a b |
| c-d$ | + * | a b （解释0） |
| -d$ | + * | a b c |
| d$ | - | a b c * + （解释1） |
| $ | - | a b c * + d |
| $ | a b c * + d - |
ps:
$ 相当于为空
解释0：当表达式运算符（）优先级大于栈顶运算符优先级（+）时，压栈。
解释1：当表达式运算符（-）优先级小于栈顶运算符优先级（）时，将栈顶运算符弹出（弹出*），再重新比较（弹出+），直到该运算符大于栈顶运算符优先级（或者栈空），再把该运算符（-）压栈。
Markdown的表格好难用啊orz
栈的应用（from leetcode）
更新中。。。
