Stack
数据结构——栈的快速入门
栈的介绍
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一 端，称为栈底(Bottom)。
根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈项，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
- 图解方式说明出栈（pop)和入栈(push)
应用场景
1) 子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2) 处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3) 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4) 二叉树的遍历。
5) 图形的深度优先(depth—first)搜索法。
栈的代码实现
数组模拟栈
分析：
使用数组模拟栈
定义一个变量为top来表示栈顶，初始化为-1
入栈的操作，当有数据加入到栈时，top++，stack[top]=data;
出栈的操作，int value=stack[top]; top—; return value;
实现
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
|
class ArrayStack{
private int maxSize;
private int[] stack;
private int 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 ( ) ) {
throw new RuntimeException ( "栈空，没有数据" );
}
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
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
| public class ArrayStackDemo {
public static void main ( String[] args ) {
ArrayStack stack = new ArrayStack ( 4 );
String key = "";
boolean loop = true;
Scanner sc = new Scanner ( System.in );
while (loop) {
System.out.println ("show,表示显示菜单" );
System.out.println ("exit,表示退出菜单" );
System.out.println ("push,表示添加数据到菜单（入栈）" );
System.out.println ("pop,表示从栈中取出数据（出栈）" );
System.out.println ( "请输入你的选择" );
key = sc.next ( );
switch (key){
case "show":
stack.list ();
break;
case "exit":
sc.close ();
loop = false;
break;
case "push":
System.out.println ( "请输入一个数" );
int value = sc.nextInt ( );
stack.push ( value );
break;
case "pop":
try {
int res = stack.pop ( );
System.out.printf ( "出栈的数据是%d\n", res );
} catch (Exception e) {
System.out.println ( e.getMessage ());
}
break;
}
}
System.out.println ("程序退出" );
}
}
|
链表模拟栈
使用双链表
定义一个top表示栈顶，初始值为-1；
入栈的操作，当有数据加入到栈时，弄一个辅助节点，temp=top,temp.next指向新节点;heroNode.pre = temp;top=heroNode
出栈的操作。当出栈时，top的节点出去，辅助节点temp=top;temp.pre.next=null; top=temp.pre; temp.pre=null;
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
class DoubleLinkList {
private int maxSize;
private HeroNode3 top =new HeroNode3(-1,null);
private int n;
private HeroNode3 head = new HeroNode3 ( 0, "" );
public DoubleLinkList ( int maxSize ) {
this.maxSize = maxSize;
}
public boolean isFull(){
return top.no == maxSize - 1;
}
public boolean isEmpty(){
return top.no == -1;
}
public void list ( ) {
if ( isEmpty ()) {
System.out.println ( "栈空没有数据" );
return;
}
HeroNode3 temp = top;
while (true) {
if ( temp.no==-1 ) {
break;
}
System.out.println ( temp );
temp = temp.pre;
}
}
public void push ( String value ) {
if ( isFull ( ) ) {
System.out.println ( "栈满" );
return;
}
HeroNode3 heroNode = new HeroNode3 ( n++, value );
HeroNode3 temp = top;
temp.next = heroNode;
heroNode.pre = temp;
top=heroNode;
}
public HeroNode3 pop ( ) {
if ( isEmpty ( ) ) {
throw new RuntimeException ( "栈空，没有数据" );
}
n--;
HeroNode3 temp=top;
temp.pre.next=null;
top = temp.pre;
temp.pre = null;
return temp;
}
}
class HeroNode3 {
public int no;
public String value;
public HeroNode3 next;
public HeroNode3 pre;
public HeroNode3 ( int no, String value ) {
this.no = no;
this.value = value;
}
@Override
public String toString ( ) {
return "HeroNode3 [no=" + no + ",value=" + value + "]";
}
}
|
测试
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
| public class DoubleListStackDemo {
public static void main ( String[] args ) {
DoubleLinkList stack = new DoubleLinkList ( 5 );
String key = "";
boolean loop = true;
Scanner sc = new Scanner ( System.in );
while (loop) {
System.out.println ("show,表示显示菜单" );
System.out.println ("exit,表示退出菜单" );
System.out.println ("push,表示添加数据到菜单（入栈）" );
System.out.println ("pop,表示从栈中取出数据（出栈）" );
System.out.println ( "请输入你的选择" );
key = sc.next ( );
switch (key){
case "show":
stack.list ();
break;
case "exit":
sc.close ();
loop = false;
break;
case "push":
System.out.println ( "请输入一个值" );
String value = sc.next ( );
stack.push ( value );
break;
case "pop":
try {
HeroNode3 res = stack.pop ( );
System.out.printf ( "出栈的数据是%s\n", res.value );
} catch (Exception e) {
System.out.println ( e.getMessage ());
}
break;
}
}
System.out.println ("程序退出" );
}
}
|
