栈和队列

发表于 | | 阅读次数:

ArrayList和LinkedList的实现方式

ArrayList的底层实现是可以增长的数组，LinkedList的底层是使用了双链表。从底层实现来看，我们可以知道，ArrayList 获取元素的时间复杂度仅为常数，而 插入和 删除的时间复杂度都为线性时间复杂度O(n)。而LinkedList则刚好相反，因为底层是链表,所以 插入和 删除的时间复杂度为常数，而 获取元素的时间复杂度却是线性时间复杂度。

另外，ArrayList和LinkedList的contains和remove方法的时间复杂度都为线性时间复杂度O(n)，对于contains方法来说，ArrayList和linkedList都需要遍历操作来实现contains方法，所以时间复杂度都是线性的；对于remove操作，ArrayList删除后需要移动元素，所以时间复杂度是线性的，而LinkedList的remove操作虽然是常数时间的，但是查找到元素的时间复杂度是线性的，所以，对已LinkedList的remove操作来说也是线性时间复杂的。

栈的运用–计算表达式的值

本章用Java来是实现一个计算含有+，-，*，\和括号的表达式的值，包括的知识点有：

  • Java语言中栈Stack和Queue的使用
  • 中缀表达式转后缀表达式的技巧
  • 计算后缀表达式的值

Java提供了栈的实现Stack对象，它继承了Vector类，底层实现是数组。Queue是一个Java队列接口，其中提供了队列必要的方法，而LinkedList实现了Queue接口，可以使用LinkedList来实现队列操作。例如：入队操作为add或insert方法，出队操作为 poll方法，获取队头的元素为peek方法。

中缀表达式是人们常用的算术表示方式，其标志是操作符处于操作数之间。而后缀表达式是操作符处于操作数之后，并且暗含的运算顺序，易于计算机进行计算。形象点的例子，例如1+23+(1+2)是中缀表达式，将其转换成后缀表达式为1, 2, 3, , +, 1, 2, +, +。其转换过程如下：

输入：1

操作：将数字直接加入到结果队列

postfix(结果队列, 从队头到队尾)：1

opStack(操作符队列，从栈底到栈顶，)：空

输入：+

操作：因为opStack栈为空，所以将+号如操作符栈

postfix: 1

opStack: +

输入：2

操作：将数字直接加入结果队列

postfix: 1, 2

opStack: +

输入*

操作：因为*的计算优先级大于站定+号的优先级，所以入栈

postfix: 1,2

opStack: +,*

输入3

操作：数字直接入结果 队列

postfix: 1,2,3

opStack: +,*

输入+

操作：因为+号的优先级不大于栈顶的*，所以*弹栈并且放到结果队列中；此时栈顶的仍为+号，但是输入的+号的优先级不大于栈顶的+号，所以，栈顶的+号出栈；此时栈为空，所以当前的+号入栈

postfix: 1,2,3,*,+

opStack: +

输入(

操作：对于( 的输入来说，直接操作栈即可，也就是说( 在入栈前比任何操作符的优先级都大；而另一中特殊情况是如果栈顶元素是(, 那么只有）的输入才可以使其出栈，也就是或对于其他操作符来说，它们的优先级又比已经入栈的( 的优先级大。

postfix: 1,2,3,*,+

opStack: +,(

输入1

操作：直接加入结果队列

postfix: 1,2,3,*,+,1

opStack: +,(

输入+

操作：遇到栈顶为(, 所以直接+号入操作符栈

postfix: 1,2,3,*,+

opStack: +,(,+

输入2

操作：直接加入结果队列

postfix: 1,2,3,*,+,1,2

opStack: +,(,+

输入)

操作：对于)的输入，应该对操作符栈进行弹栈，直至遇到(, 弹栈才结束，这也就是说，)的在入栈前的优先级比其他操作的优先级都低。在假设表达式合法的前提下，不存在)处在栈顶的情况，)会和(一起出栈，但不会放入结果队列中。这一次，+号和(出栈，+号加入结果队列。

postfix:1,2,3,*,+,1,2,+

opStack:+

如果操作符栈不为空，全部弹出加入结果队列

postfix: 1,2,3,*,+,1,2,+,+

opStack: 空

计算表达式的值–Java版实现

接下来，我将要介绍一下我的小型计算器的实现，表达式的特征是包含+，-，*，/和（），并且数字是整数，可以是多位的。整个实现分为3大部分：

  1. 读取优先级列表
  2. 中缀表达式转换成后缀表达式
  3. 计算后缀表达式的值

当然了，最难的部分是第二步，下面一一介绍。

  • 优先级列表

我是用一个文件来存储操作符和对应的优先级，每行存储一个，采用操作符-空格-优先级的方式，如下：+ 1

完整的优先级列表如下

1
2
3
4
+ 1
- 1
* 2
/ 2

使用HashMap保存优先级列表，这里涉及了如何将一个char转化成一个int值的过程，我们使用了先将char转化成String，然后将String转化成Integer的方法

1
2
3
4
5
6
7
8
9
10
11
//读入优先级文件
Map<Character,Integer> priority=new HashMap<Character,Integer>();
BufferedReader breader=new BufferedReader(new FileReader("priority.txt"));
String pline=breader.readLine();
while(pline!=null) {
	char[] plineChar=pline.toCharArray();
	priority.put(plineChar[0], Integer.parseInt(String.valueOf(plineChar[2])));
	pline=breader.readLine();
}
System.out.println("优先级："+priority);
breader.close();
  • 中缀表达式转后缀表达式

因为数字是多位的，所以用了一个栈来numStack来记录数，并且使用一个静态方法拼接成一个整数。opStack< Character>是用来存储操作符的，postfix是用来存储转换好的后缀表达式的。整个过程如下：

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
//numStack用于存储存储操作数
Stack<Integer>numStack=new Stack<>();
//opStack用于存储操作符
Stack<Character>opStack=new Stack<>();
//postfix存储后缀表达式的，
//其中有Integer和Character类型，所以用Object作为泛型参数
Queue<Object>postfix=new LinkedList<>();
Scanner scanner=new Scanner(System.in);
String myExp=scanner.nextLine();
while(myExp!=null && !"end".equalsIgnoreCase(myExp)) {
	char[] charExp=myExp.toCharArray();
	//System.out.println(charExp);
	for(char charitem:charExp) {
		switch (charitem) {
			case '1': case '2': case '3': case '4': case '5':
			case '6': case '7': case '8': case '9': case '0':
				numStack.push(Integer.parseInt(String.valueOf(charitem)));
				break;
			case '+': case '-': case '*':
			case '/': case '(':case ')':
                  	//在遇到操作符号之前弹出数字拼接
				pushNumber2Result(numStack, postfix);
				if(opStack.isEmpty()) {
					opStack.push(charitem);
				}else {
					//对右括号特殊处理
					if(charitem==')'&&!opStack.isEmpty()) {
						while(opStack.peek()!='(') {
							postfix.add(opStack.pop());
						}
						//弹出左括号
						opStack.pop();
					}else if(charitem=='(') {
						opStack.push(charitem);
					}else {
						//对非括号的符号输入
						//如果碰到左括号操作符号入栈
						if(opStack.peek()=='(') {
							opStack.push(charitem);
						}else if(priority.get(charitem)>priority.get(opStack.peek())) {
							//如果下一个操作符的优先级大于栈顶的优先级，
                                  //压栈,此时栈顶一定有操作符
							opStack.push(charitem);
						}else {
							//否则，出栈直至当前操作符入栈
							//注意当栈不空的情况下比较
							while(!opStack.isEmpty() && priority.get(charitem)											<=priority.get(opStack.peek())) {
								postfix.add(opStack.pop());
							}
							opStack.push(charitem);
						}
					}
				}
				
		}
	}
	pushNumber2Result(numStack, postfix);
	//注意剩余的操作符可能有多个
	while(!opStack.isEmpty()) {
		postfix.add(opStack.pop());
	}
	System.out.println(postfix);

其中，pushNumber2Result函数的定义如下：

1
2
3
4
5
6
7
8
9
10
11
public static void pushNumber2Result(Stack<Integer>numStack, Queue<Object>result) {
		int num=0;
		int base=1;
		while(!numStack.isEmpty()) {
			num=num+numStack.pop()*base;
			base=base*10;
		}
		//注意如果num!=0才添加进去
		if(num!=0)
			result.add(num);
	}

几个值得注意的地方：

  1. 栈的循环操作注意判空
  2. 操作数的添加如果是0的话不应该添加
  • 利用后缀表达式 计算表达式的值
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
numStack.clear();
while(!postfix.isEmpty()) {
	Object head=postfix.poll();
	if(head instanceof Integer) {
		numStack.push((Integer)head);
	}else if(head instanceof Character){
		Character op=(Character) head;
		int num2=numStack.pop();
		int num1=numStack.pop();
		switch(op) {
		case '+':
			numStack.push(num1+num2);
			break;
		case '-':
			numStack.push(num1-num2);
			break;
		case '*':
			numStack.push(num1*num2);
			break;
		case '/':
			numStack.push(num1/num2);
			break;
		}
	}
}
if(numStack.size()==1) {
	System.out.println("result:"+numStack.pop());
}else {
	System.out.println("计算出错！");
}
  • 测试结果
1
2
3
4
5
6
7
优先级：{*=2, +=1, -=1, /=2}
1+2*3+(1*2)
[1, 2, 3, *, +, 1, 2, *, +]
result:9
1+2*4-5/(1+1)
[1, 2, 4, *, +, 5, 1, 1, +, /, -]
result:7

大功告成！

坚持原创技术分享，您的支持将鼓励我继续创作！