C++ Stack学习

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）

更新中。。。