数据结构-栈

 

栈: 一个先入后出的有序序列（First In LastOut）

限制线性表中的插入和删除只在同一端进行，允许插入和删除的一段叫做栈顶（Top）,另外一段叫做栈底（Bottom），所以最先放入的元素在栈底，最后放入的元素在栈顶。

总有一个变量指向栈顶，如果栈为空，那么栈顶变量下标为-1.

常用的场景：

1)子程序的调用，在跳往子程序之前，会将下一个指令的地址存到堆栈中，直到子程序结束再将地址取出，回到原来的程序中。

2)处理递归调用，类似子程序调用，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中

3)表达式的转换与求值

4)二叉树的遍历

5)图的深度优先搜索法（depth-first）

 

package com.dataStructure.heapStack;

import javax.swing.Popup;

public class MyStack {
	private int top = -1;//该栈为空
	private int maxSize = 50;//该栈最大容量
	private Object[] stacks = new Object[maxSize];
	/**
	 * 入栈
	 * @param data
	 */
	public void push(Object data){
		//Check stack if max
		if(this.top == maxSize-1){
			System.out.println("该栈已经最大了，不能存放数据了");
			return;
		}
		this.top++;
		this.stacks[this.top] = data;
	}
	/**
	 * 出栈，取栈顶的值
	 */
	public Object pop(){
		if(this.top == -1){
			System.out.println("该栈为空");
			return -1;
		}
		Object topValue = this.stacks[this.top];
		this.top--;
		return topValue;
	}
	public int getResult(int num1, int num2, String operation){
		char[] operationCharArray = operation.toCharArray();
		int result = 0;
		switch (operationCharArray[0]) {
		case '+':
			result = num1 + num2;
			break;
		case '-':
			result = num2 - num1;
			break;
		case '*':
			result = num1 * num2;
			break;
		case '/':
			result = num2 / num1;
			break;
		default:
			break;
		}
		return result;
	}
	public boolean isOperation(String character){
		return character.equals("+") || character.equals("-") || character.equals("*") || character.equals("/");
	}
	
	public boolean isEmpty(){
		return this.top == -1;
	}
	
	public int getOperationPrior(String character){
		return (character.equals("*") || character.equals("/")) ? 1 : 0;
	}
	
	public Object getTopValue(){
		return this.stacks[this.top];
	}
	public void showStack(Object[] stacks){
		if(this.top == -1){
			return;
		}
		for(int x = this.top; x > -1; x--){
			System.out.println("当前第"+x+"元素: "+stacks[x]);
		}
	}
	public static void main(String[] args) {
		MyStack myStack = new MyStack();
		myStack.push(3);
		myStack.push(25);
		myStack.push(12);
		myStack.push(15);
		myStack.pop();

		myStack.showStack(myStack.getStacks());
	}

	public int getTop() {
		return top;
	}

	public void setTop(int top) {
		this.top = top;
	}

	public int getMaxSize() {
		return maxSize;
	}

	public void setMaxSize(int maxSize) {
		this.maxSize = maxSize;
	}
	public Object[] getStacks() {
		return stacks;
	}
	public void setStacks(Object[] stacks) {
		this.stacks = stacks;
	}

	
}

 

package com.dataStructure.heapStack;

public class Calculate {
	private String expression = "100-60/2+2*14/4-12";
	private MyStack numStack = new MyStack();
	private MyStack operationStack = new MyStack();
	
	private void scanExpression(String expression){
		int index = 0;
		while(true){
			//依次取出字符
			String singleCharacter = expression.substring(index, 1);
			//判断singleCharacter是不是运算符
			if(this.operationStack.isOperation(singleCharacter)){
				//如果为空，直接入符号栈
				if(this.operationStack.isEmpty()){
					this.operationStack.push(singleCharacter);
				}else{//表示不为空
					this.operationStack.push(singleCharacter);
					int currentOperation = this.operationStack.getOperationPrior(singleCharacter);
					
					int topOperation = Integer.valueOf((String)this.operationStack.getTopValue());
					if(currentOperation <= topOperation){
						//数栈弹出两个数，
						int num1 = Integer.valueOf((String)this.numStack.pop());
						int num2 = Integer.valueOf((String)this.numStack.pop());
						String operationTop = (String)this.operationStack.pop();
						int result = this.numStack.getResult(num1, num2, operationTop);
						this.numStack.push(result);
					}
				}
			}else{
				//如果是数字就入数栈
				this.numStack.push(singleCharacter);
			}
			index++;
			//check if complete the scan
			if(index == this.expression.length()){
				break;
			}
		}
	}
}