数据结构--栈

发表于 | 分类于 | 热度:
字数统计: 3k 字 | 阅读时长 ≈ 11 分钟

1. 栈

栈是指允许在一端就行插入或删除操作的线性表，首先需要确定的是栈是一种线性表。

1)栈的英文为 (stack)

2)栈是一个先入后出 (FILO first In Last Ou的有序列表

3)( stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为機项(Top),另端为固定的一端,称为底( Bottom)

4)根据栈的定义可知,最先放入中元素在機底,最后放入的元素在项,而除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除

栈的应用场景

1)子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中。

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

3)表达式的转换与求值(实际解决)。

4)二叉树的遍历。

5)图形的深度优先{ depth- first)搜素法。

##栈的实现

栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素

使用Java语言对栈进行一个简单实现

用数组模拟栈的使用，由于栈是一种有序表，当然可以使用数据的结构来存储栈的内容、

【思路分析】

  1. 使用数组模拟栈
  2. 定义变量top表示栈顶，初始化为-1
  3. 入栈，当有数据加入栈时，top++。stack（top）=data
  4. 出栈，从栈顶取出数据，定义变量value用来存储栈顶的数据，然后把top–，return value
需要注意的是，入栈是栈顶元素先top++，再放数据。出栈是先取数据，再top–。

用Java定义一个栈，并定义栈中的各种操作方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

//定义一个ArrayStack  表示栈
class ArrayStack{
	private int maxSize; //栈的大小
	private int[] stack; //数组，数组模拟栈，数据放在该数组中
	private int top = -1; // top表示栈顶，初始化为1
	
	//构造方法
	public ArrayStack(int maxSize){
		this.maxSize = maxSize;
		stack = new int[this.maxSize];  //我们上面定义完数组，没有进行初始化，我们需要进行初始化
	}
	
	//判断沾满的方法
	public boolean isFull(){
		return top == maxSize - 1;
	}
	
	//判断栈空的方法
	public boolean isEmpty(){
		return top == -1;
	}
	
	//入栈的操作
	public void push(int value){
		if (isFull()) {
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
			
	}
	
	//出栈的操作，将栈顶的数据返回
	public int pop(){
		if (isEmpty()) {
			System.out.println("栈空");
			new IllegalArgumentException("栈空,没有数据");
		}
		
		int value = stack[top];
		top--;
		return value;
			
	}
	
	
	//遍历栈，需要从栈顶往下遍历
	public void list(){
		if (isEmpty()) {
			System.out.println("栈空");
			return;
		}
		
		for (int i = top; i >=0; i--) {
			System.out.printf("stack[%d]=%d\n",i,stack[i]);
		}
		
	}
		
}

编写测试方法，测试操作能否正常执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static void main(String[] args) {
	//测试栈
	//先创建一个ArrayStack对象，表示栈
	ArrayStack stack = new ArrayStack(4);
	
	stack.push(2);
	stack.push(3);
	stack.push(6);		
	stack.list();		
	System.out.println(stack.pop());
	stack.list();
	
}

我们使用一个计算的式子计算过程来进一步了解栈的实际应用。

eg：使用栈完成计算一个表达式的结果：
722-5+1-5+3-4=？

我们需要定义两个栈，一个是数据栈numStack，用来存放计算式中数据。一个是符号栈，用来存放计算式中的符号。

1568774508177

使用栈完成表达式的计算思路：

  1. 通过一个index值也就是索引，来遍历我们的表达式

  2. 如果我们发现当前索引值是一个数据，就直接入数栈

  3. 如果发现扫描到是一个符号，就分为以下情况进行考虑

      1. 如果发现当前的符号栈为空，就直接入栈
      1. 如果符号栈有操作符，就进行比较。如果当前的操作符的优先级小于或者是等于栈中的操作符，就需要从数据栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将计算得到的结果，放入数据栈，然后将当前的操作符放入符号栈。如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈中。

  4. 当表达式扫描完毕之后，就顺序的从符号栈和数据栈中pop出相应的数和符号，并运行。

  5. 最后数据栈之后一个数字，就是我们的计算结果。

我们根据上面的思路，使用编程实现计算上面中缀表达式的过程。

引入：中缀表达式

形如上面定义的表达式 5+3-6/2 这样的式子就是中缀表达式，是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。
与前缀表达式（例：+ 3 4）或后缀表达式（例：3 4 +）相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。

一般是转换为后缀表达式跟容易的计算。

==++++++++++++++++++++++++++++++++++++++++++++++

中缀表达式转换为后缀表达式的过程如下：

后缀表达式也叫逆波兰表达式，

规则：

中缀表达式a + b*c + (d * e + f) * g，其转换成后缀表达式则为a b c * + d e * f + g * +。

转换过程需要用到栈，具体过程如下：

  • 1）如果遇到操作数，我们就直接将其输出。

  • 2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

  • 3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

  • 4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。

  • 5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

—+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

但是在实际应用时，中缀表达式是应用最多的，下面使用栈模拟计算机计算中缀表达式的过程。

要实现计算中缀表达式的过程，还要在上面我们定义的栈类中新增几个方法。

  1. 新增定义运算符优先级的方法：

返回运算符的优先级，优先级是程序员来定的，优先级使用数字表示，数字越大优先级越高。
我们假定计算式中只含有加减乘除 

1
2
3
4
5
6
7
8
9
10
11
12

// 返回运算符的优先级，优先级是程序员来定的，优先级使用数字表示，数字越大优先级越高。
//我们假定计算式中只含有加减乘除
public int priority(int oper){
	if (oper == '*' || oper == '/') {
		return 1;
	}else if (oper == '+' || oper == '-') {
		return 0;
	}else {
		return -1;
	}		
}
  1. 判断是否是运算符方法
1
2
3
4
//判断是不是一个运算符
public boolean isOper(char val){
	return val == '+' || val == '-' || val =='*' || val == '/';
}
  1. 计算方法，从栈中弹出的两个数字需要进行运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//计算方法，从栈中弹出的两个数需要进行计算
	public int cal(int num1,int num2,int oper){
		int result =0;
		
		switch (oper) {
		case '+':
			result = num1 + num2;
			break;
			
		case '-':
			result = num2 - num1;//注意顺序，这里是num2是栈底元素
			break;
			
		case '*':
			result = num1 * num2;
			break;
			
		case '/':
			result = num2 / num1;
			break;

		default:
			break;
		}
		return result;	
	}
  1. 增加一个用于返回当前栈顶的值，不是真正的pop操作，用于进行栈顶元素的比较
1
2
3
4
//增加一个方法，可以返回当前栈顶的值，但不是真正的pop
public int peek(){
	return stack[top];
}

下面我们进行程序的编写。

我们需要定义两个栈，一个是数据栈numStack，用来存放计算式中数据。一个是符号栈，用来存放计算式中的符号。

  1. 通过一个index值也就是索引，来遍历我们的表达式

  2. 如果我们发现当前索引值是一个数据，就直接入数栈

  3. 如果发现扫描到是一个符号，就分为以下情况进行考虑

      1. 如果发现当前的符号栈为空，就直接入栈
      1. 如果符号栈有操作符，就进行比较。如果当前的操作符的优先级小于或者是等于栈中的操作符，就需要从数据栈中pop出两个数，再从符号栈中pop出一个符号，进行运算，将计算得到的结果，放入数据栈，然后将当前的操作符放入符号栈。如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈中。

  4. 当表达式扫描完毕之后，就顺序的从符号栈和数据栈中pop出相应的数和符号，并运行。

  5. 最后数据栈之后一个数字，就是我们的计算结果。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

public class jisuanshi {
	public static void main(String[] args) {
		//根据上面的思路，进行代码的实现，完成表达式的运算过程
		
		String expression = "2+6*8-4";
		//创建两个栈，一个是数据栈，一个是符号栈
		ArrayStack2 numStack = new ArrayStack2(20);
		ArrayStack2 operStack = new ArrayStack2(20);
		//定义需要的相关变量
		int index = 0;//用于扫描
		int num1 =0;
		int num2 =0;
		int oper = 0; //char和int类型是一样的
		int result = 0;
		char ch = ' ';//将每次扫描得到char保存到ch中
		
		//开始使用while循环的扫描expression
		while(true){
			//依次得到expression中的每个字符
			ch = expression.substring(index, index+1).charAt(0);
			//判断ch是什么然后做相应的处理
			if (operStack.isOper(ch)) {//如果是运算符
				//判断当前的符号栈是否为空
				if (!operStack.isEmpty()) {
					//如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就进行下面的操作
					//再从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
					
					if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
						//从数据栈pop两个数进行计算
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						result = numStack.cal(num1, num2, oper);
						//把运算结果入数栈
						numStack.push(result);
						//然后把操作符入符号栈
						operStack.push(ch);
					}else{
						//如果当前的操作符优先级大于栈中的操作符，就直接入符号栈
						operStack.push(ch);
					}	
				}else{
					//如果为空直接入符号栈
					operStack.push(ch);	
				}
				
			}else{
				//处理是数的情况。则直接入数据栈。因为上面把它转换为字符了，所以需要进行转换
				numStack.push(ch - 48);				
			}
			//让index加1，并判断是否扫描到expression的最后
			index++;
			if (index >= expression.length()) {
				break;
			}				
		}
	
		//当表达式扫描完毕，就顺序的从数据栈和符号栈中pop出相应的数据和符号。并运算
		while(true){
			//如果符号栈为空，则计算到最后的结果，数据栈中只有一个数字，这个就是结果
			if (operStack.isEmpty()) {
				break;
			}
			
				num1 = numStack.pop();
				num2 = numStack.pop();

				oper = operStack.pop();
				result = numStack.cal(num1, num2, oper);
				numStack.push(result);//入栈		
			}			
			//将数据栈中最后的数pop出来，就是结果
				int res2 = numStack.pop();
			System.out.printf("表达式%s = %d", expression,res2);
		
	}	
}

运算结果：表达式2+6*8-4 = 46

本文标题:数据结构--栈

文章作者:雷凯博

发布时间:2019年07月16日 - 10:07

最后更新:2021年05月16日 - 19:05

原始链接:http://yoursite.com/2019/07/16/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%A0%88/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

坚持原创技术分享，您的支持将鼓励我继续创作！
-------------本文结束感谢您的阅读-------------
0%