引言
栈是一种(先进后出)FILO的数据，类似一个箱子，先放入的东西放在底下。它基于线性表实现，与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，栈的结构如下图：
栈基本结构.png
Stack的基本实现
1.接口
public interface IStack<T> {
/**
* 栈是否为空
* @return
*/
boolean isEmpty();
/**
* data元素入栈
* @param data
*/
void push(T data);
/**
* 返回栈顶元素,未出栈
* @return
*/
T peek();
/**
* 出栈,返回栈顶元素,同时从栈中移除该元素
* @return
*/
T pop();
}
2.对堆的操作主要是对栈顶节点的操作,原理比较简单，这里不再详细说明。下面是完全实现代码
package stack;
import List.Node;
/**
* Created by chenming on 16/12/27.
*/
public class Stack<T> implements IStack<T>{
// public String ID;
public Node<T> mTop;//栈顶指针
private int mSize;
/**
* 压栈操作
*
* @param item
*/
public void push(T item) {
if (item == null) {
return;
}
Node<T> newNode = new Node<>(item, null, mTop);//新建节点,next指向当前的top
mTop = newNode;//TOP指针上移
mSize++;
}
/**
* 弹栈操作
*
* @return
*/
public T pop() {
T item = null;
if (!isEmpty()) {
item = mTop.mData;
mTop = mTop.next;
mSize--;
}
return item;
}
/**
* 大小
*
* @return
*/
public int size() {
return mSize;
}
/**
* 判空
* @return
*/
public boolean isEmpty() {
return mTop == null || mTop.mData == null;
}
/**
* 清空
*/
public void clear() {
while (!isEmpty()) {
pop();
}
mSize = 0;
}
/**
* 读栈顶值
* @return
*/
public T peek(){
T item = null;
if(mTop != null){
item = mTop.mData;
}
return item;
}
}
栈应用-中缀表达式转为后缀表达式
所谓中缀表达式就是类似下面的计算式:1+2(4-3)+8,它的运算符放在操作数中间，这就是我们日常见到的普通算式，但是由于运算符和括号都有各自的优先级，而计算机是不知道这些优先级的，所以中序表达式对计算机而言比较复杂，想要让它更容易被计算机处理，需要将它转换为后缀表达式,类似下面这样:
1243-+8+,里面的运算符号优先级从高到低,而括号只是影响了运算符的优先级，并不参与运算，所以需要过滤掉。如何转换呢，这里就需要借助栈存放操作符，栈存放操作符的原则是:优先级高的运算符(包括左括号)先入栈,这样可以保证高优先级的符号先输出。根据运算符的优先级来输出后缀表达式，规则如下:
1>如果遇到操作数，则直接输出;
2>如果遇到左括号，直接入栈；
3>如果遇到右括号，则弹栈，知道左括号弹出;
4>如果遇到普通操作符,则弹栈输出，直到遇到左括号或者优先级比当前操作符小;弹栈完成后，表明优先级高的符号已经全部输出，当前操作符入栈;
5>表达式遍历完毕后，栈中的剩余的操作符弹栈输出。
具体代码如下:
package stack;
import android.util.Log;
/**
* Created by chenming on 16/12/29.
* 栈应用:中缀表达式转后缀表达式
* a+b*c+(d*e+f)*g ---> abc*+de*f+g*+
*/
public class PostFixExpression {
private Stack<Character> mOperationsStack = new Stack<>();//操作符栈
private StringBuilder mResult = new StringBuilder();
private char[] OPERATIONS = {'+', '-', '*', '/'};
private int[] OPERATION_PRIORITYS = {0, 0, 1, 1};
private char LEFT_BRACKET = '(';
private char RIGHT_BRACKET = ')';
/**
* 转换步骤
* 1.遇到字符，直接输出到mResult
* 2.遇到操作符
* 1.当前操作符栈为空,直接入栈，不输出
* 2.当前操作符堆栈不为空:
* 1.新的操作符优先级大于栈顶操作符,入栈， 不输出
* 2.新的操作符优先级小于等于栈顶操作符，遍历栈，将当前所有大于新操作符优先级的操作符弹栈输出!
* 3.括号对处理:遇到闭括号，一直弹栈输出，直到左括号弹出
*
* @param express
*/
public void convertMidToPostFixExpression(String express) {
char[] chars = express.toCharArray();
for (int i = 0; i < chars.length; i++) {
char item = chars[i];
if (!isOperation(item)) {//不是操作符直接输出
mResult.append(item);
} else {//是操作符
if (mOperationsStack.isEmpty()) {
mOperationsStack.push(item);
} else {
if (item == LEFT_BRACKET) {
mOperationsStack.push(item);//左括号直接入栈
} else if (item == RIGHT_BRACKET) {
//直接弹栈，输出,直到遇到左括号
while (mOperationsStack.peek() != null && mOperationsStack.peek() != LEFT_BRACKET) {
char charInnerBracket = mOperationsStack.pop();
if (charInnerBracket != LEFT_BRACKET && charInnerBracket != RIGHT_BRACKET) {
mResult.append(charInnerBracket);
}
}
//弹出左括号
if (mOperationsStack.peek() != null && mOperationsStack.peek() == LEFT_BRACKET) {
mOperationsStack.pop();
}
} else {
int newCharPriority = getPriority(item);
//遍历操作符栈，高于等于新操作符优先级的符号输出
Character topOperation = mOperationsStack.peek();//查看当前栈顶的操作符
int topCharPriority = getPriority(topOperation);
while (newCharPriority <= topCharPriority && !mOperationsStack.isEmpty()) {
if (topOperation == LEFT_BRACKET) {//左括号终止遍历,保证括号内符号优先级
break;
}
//将高于新符号优先级的操作符弹栈输出
char operation = mOperationsStack.pop();//高优先级运算符弹栈，输出
mResult.append(operation);
//下一次比较
topOperation = mOperationsStack.peek();
if (topOperation != null) {
topCharPriority = getPriority(topOperation);
}
}
mOperationsStack.push(item);//新的操作符入栈
}
}
}
}
/**
* 输出剩下的操作符
*/
while (!mOperationsStack.isEmpty()) {
mResult.append(mOperationsStack.pop());
}
Log.e("TAG", "后缀表达式:" + mResult.toString());
}
/**
* 操作符优先级查找
*
* @param op
* @return
*/
private int getPriority(char op) {
if (op == LEFT_BRACKET) {
return Integer.MAX_VALUE;
}
for (int i = 0; i < OPERATIONS.length; i++) {
if (OPERATIONS[i] == op) {
return OPERATION_PRIORITYS[i];
}
}
return 0;
}
/**
* 是否是操作符
*
* @param op
* @return
*/
private boolean isOperation(char op) {
if (op == LEFT_BRACKET || op == RIGHT_BRACKET) {
return true;
}
for (int i = 0; i < OPERATIONS.length; i++) {
if (OPERATIONS[i] == op) {
return true;
}
}
return false;
}
private Stack<Integer> mResultStack = new Stack<>();
/**
* 个位数运算
*
* @param expression
* @return
*/
public int calulateExpression(String expression) {
convertMidToPostFixExpression(expression);
String postFixExpress = mResult.toString();
char[] chars = postFixExpress.toCharArray();
for (int i = 0; i < chars.length; i++) {
char item = chars[i];
if (item >= '0' && item <= '9') {
int data = item - '0';
mResultStack.push(data);//数据入栈
} else {
//操作符
int size = mResultStack.size();
if (size >= 2) {
//第一个参数先压得栈
int secondParam = mResultStack.pop();
int firstParam = mResultStack.pop();
switch (item) {
case '+':
mResultStack.push(secondParam + firstParam);
break;
case '*':
mResultStack.push(secondParam * firstParam);
break;
case '-':
mResultStack.push(firstParam - secondParam);
break;
case '/':
mResultStack.push(firstParam/secondParam);
break;
}
}
}
}
int result = mResultStack.pop();
Log.e("TAG", "计算结果:" + result);
return result;
}
}
至于运算后缀表达式，也是借助栈，每次遇到操作数的时候先取出，遇到操作符，则将最近取出的俩数做相应运算，然后压栈，直到表达式遍历完，最后的结果在栈中取即可.
这里作为测试，后缀表达式为字串，要支持多位数运算的话，操作数作为对象可存放在数组或者链表里面即可。
总结:以上就是栈基本的实现和用例。代码地址:数据结构与算法学习JAVA描述GayHub地址
