java栈
栈是一个先进后出的数据结构,想要自己实现一个栈,要求这个栈具有push(),pop()——返回栈顶并出栈,peek()——返回栈顶不出栈,isEmpty()等方法。
1.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
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
77import java.util.Arrays;
/**
* @author George
* @project testDemo
* @package abc
* @date 2021/9/25 19:59
* @since 1.0
*/
class Stack1<T> {
// 实现栈的数组
private Object[] stack;
// 数组大小
private int size;
Stack1(){
stack=new Object[10];
}
// 判断数组是否为空
public boolean isEmpty(){
if (size==0){
return true;
}else{
return false;
}
}
// 返回栈顶元素
public T peek(){
T t=null;
if (size>0){
t= (T) stack[size-1];
}
return t;
}
// 返回栈顶并出栈
public T pop(){
T t=peek();
if(size>0){
stack[size-1]=null;
size--;
}
return t;
}
// 扩容
public void expandCapacity(int size){
int len=stack.length;
if (size>len){
size=size*3/2+1;
stack= Arrays.copyOf(stack,size);
}
}
public void push(T t){
expandCapacity(size+1);
stack[size]=t;
size++;
}
}
public class ArrayStack {
public static void main(String[] args) {
Stack1<String> stringStack1=new Stack1<>();
System.out.println(stringStack1.peek());
System.out.println(stringStack1.isEmpty());
stringStack1.push("java");
stringStack1.push("chenyc2021@qq.com");
stringStack1.push("gogogo");
System.out.println(stringStack1.pop());
System.out.println(stringStack1.isEmpty());
System.out.println(stringStack1.peek());
}
}采用链表来实现
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/**
* @author George
* @project testDemo
* @package abc
* @date 2021/9/26 0:49
* @since 1.0
*/
class Stack2<T> {
// 定义一个链表
class Node<T> {
private T t;
private Node next;
}
private Node<T> head;
// 构造函数
Stack2() {
head = null;
}
// 入栈
public void push(T t) {
if (t == null) {
throw new NullPointerException("参数不能为空");
}
if (head == null) {
head = new Node<T>();
head.t = t;
head.next = null;
} else {
Node<T> temp = head;
head = new Node<T>();
head.t = t;
head.next = temp;
}
}
// 出栈
public T pop() {
T t = head.t;
head = head.next;
return t;
}
// 栈顶元素
public T peek() {
T t = head.t;
return t;
}
//判断栈是否为空
public boolean isEmpty() {
if (head == null) {
return true;
} else {
return false;
}
}
}
public class LinkStack {
public static void main(String[] args) {
Stack2 stack = new Stack2();
System.out.println(stack.isEmpty());
stack.push("Java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}采用LinkedList实现栈
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
53import java.util.LinkedList;
/**
* @author George
* @project testDemo
* @package abc
* @date 2021/9/26 9:39
* @since 1.0
*/
class Stack3<T>{
// 构建一个linkedLIst集合
private LinkedList<T> ll=new LinkedList<>();
// 判断栈是否为空
public boolean isEmpty(){
return ll.isEmpty();
}
// 入栈
public void push(T t){
ll.addFirst(t);
}
//出栈
public T pop(){
return ll.removeFirst();
}
// 栈顶元素
public T peek(){
T t=null;
if (!ll.isEmpty()){
t=ll.getFirst();
}
return t;
}
}
public class LinkedStack {
public static void main(String[] args) {
Stack3<String> stringStack3=new Stack3<>();
System.out.println(stringStack3.isEmpty());
System.out.println(stringStack3.peek());
stringStack3.push("java");
stringStack3.push("is");
stringStack3.push("beautiful");
System.out.println(stringStack3.peek());
System.out.println(stringStack3.pop());
System.out.println(stringStack3.isEmpty());
System.out.println(stringStack3.peek());
}
}
1.2、栈的应用
在java中,栈是一种很重要的数据结构,如以下的很多场景都应用到了栈
- 符号匹配
- 中缀表达式变为后缀表达式
- 计算后缀表达式
- 实现函数的嵌套调用
- HTML和XML中的标签匹配
- 网页浏览器中以访问界面的历史记录
例如:
- 符号匹配
在编写程序的过程中,我们经常会遇到诸如圆括号“()”与花括号“{}”,这些符号都必须是左右匹配的,这就是我们所说的符合匹配类型,当然符合不仅需要个数相等,而且需要先左后右的依次出现,否则就不符合匹配规则,如“)(”,明显是错误的匹配,而“()”才是正确的匹配。有时候符合如括号还会嵌套出现,如“9-(5+(5+1))”,而嵌套的匹配原则是一个右括号与其前面最近的一个括号匹配,事实上编译器帮我检查语法错误是也是执行一样的匹配原理,而这一系列操作都需要借助栈来完成,接下来我们使用栈来实现括号”()”是否匹配的检测。
判断原则如下(str=”((5-3)*8-2)”):
a.设置str是一个表达式字符串,从左到右依次对字符串str中的每个字符char进行语法检测,如果char是,左括号则入栈,如果char是右括号则出栈(有一对匹配就可以去匹配一个左括号,因此可以出栈),若此时出栈的字符char为左括号,则说明这一对括号匹配正常,如果此时栈为空或者出栈字符不为左括号,则表示缺少与char匹配的左括号,即目前不完整。
b.重复执行a操作,直到str检测结束,如果此时栈为空,则全部括号匹配,如果栈中还有左括号,是说明缺少右括号。
实现代码如下:
1 | public class CheckExpression { |