栈和队列

栈:先进后出

最先进入的最后出,就像子弹匣。

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
public class ArrayStack {
private int sizeMax;
private int [] arr;
private int top;


public ArrayStack(int sizeMax) {
this.sizeMax = sizeMax;
arr = new int [this.sizeMax];
top = -1;//因为是数组,第一个元素的下标是0,所有先让其索引为-1
}


public boolean isFull(){
return top==sizeMax-1;
}
public boolean isEmpty(){
return isEqualNegativeOne(top);
}
public boolean isEqualNegativeOne(int item){
return item==-1;
}
//入栈
public void push(int value){
if (isFull()){
System.out.println("Stack is full!");
return;
}
arr[++top] = value;
}
//出栈
public int pop(){
if (isEmpty()) throw new RuntimeException("Stack is empty!");
return arr[top--];
}

//全部出栈
public void allPop(){
while (!isEmpty()){
System.out.println("deliver from godown:"+arr[top--]);
}
}
//遍历
public void list(){
int first = top;
while (!isEqualNegativeOne(first))
System.out.printf("stack[%d]=%d\n",first,arr[first--]);
}



}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(10);
for (int i = 0; i <11 ; i++) {
stack.push(i);
}
System.out.println("入栈:");
stack.list();
System.out.println("出栈:");
for (int i = 0; i < 3; i++) {
stack.pop();
}
stack.list();
System.out.println("全部出栈:");
全部出栈
stack.allPop();
try {
stack.pop();
}catch (Exception e){
e.printStackTrace();
}
}
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
Stack is full!
入栈:
stack[9]=9
stack[8]=8
stack[7]=7
stack[6]=6
stack[5]=5
stack[4]=4
stack[3]=3
stack[2]=2
stack[1]=1
stack[0]=0
出栈:
stack[6]=6
stack[5]=5
stack[4]=4
stack[3]=3
stack[2]=2
stack[1]=1
stack[0]=0
全部出栈:
deliver from godown:6
deliver from godown:5
deliver from godown:4
deliver from godown:3
deliver from godown:2
deliver from godown:1
deliver from godown:0
java.lang.RuntimeException: Stack is empty!
at Stack.ArrayStack.pop(ArrayStack.java:35)
at Stack.ArrayStack.main(ArrayStack.java:66)
队列:先进先出

就是排队,第一个的人先走。

队列也分成两种:

  • 静态队列(数组实现)
  • 动态队列(链表实现)

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
package Queen;


public class ArrayQueen {
private int maxSize;//数组最大容量
private int front;//队头
private int rear;//队尾
private int arr[];//队列数组
public ArrayQueen(int maxSize){
this.maxSize=maxSize;
arr = new int[this.maxSize];
front =-1;
rear =-1;
}

public boolean isFull(){return rear==maxSize; }

public boolean isEmpty(){ return rear==front; }

public void add(int value){//增加
if(isFull()){
System.out.println("队列满了");
return;
}
arr[++rear]=value;
}

public int get(){//取出
if (isEmpty()) throw new RuntimeException("Arrays is empty!");
int value =arr[++front];
arr[front]=0;
return value;
}

public int queryFirst(){return query(1); }//查询头部

public int queryFinal(){ return query(rear-front); }//查询尾部

public int query(int i){//查询
int f = front+i;
if (isEmpty()) return -1;
if (f>rear) return -1;
return arr[f];
}
public int total(){
return rear;
}
public String list(){
int f = front;
String s = "[";
for (int i = ++f; i <= rear; i++) {
s+=arr[i]+" ";
}
return s+"]";
}


}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
ArrayQueen queen = new ArrayQueen(20);
queen.add(13);
queen.add(12);
queen.add(11);
queen.add(15);
System.out.println("当前队列情况:"+queen.list());
System.out.println("出队列:"+queen.get());
System.out.println("出队列:"+queen.get());
System.out.println("当前队列情况:"+queen.list());

System.out.println("查询队列尾部:"+queen.queryFinal());
System.out.println("查询队列头部:"+queen.queryFirst());
System.out.printf("查询队列第2个:%d\n",queen.query(2));
System.out.printf("查询队列第1个:%d\n",queen.query(1));
}

输出:

1
2
3
4
5
6
7
8
当前队列情况:[13 12 11 15 ]
出队列:13
出队列:12
当前队列情况:[11 15 ]
查询队列尾部:15
查询队列头部:11
查询队列第2个:15
查询队列第1个:11
循环队列

往往实现静态队列,我们都是做成循环队列

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
98
99
100
101
102
103
104
105
106
107
108
109
public class CircularQueen {
private int maxSize;//数组最大容量
private int front;//指向队列第一个元素
private int rear;//指向队列最后一个元素的后一个位置
private int arr[];//队列数组
public CircularQueen(int maxSize){
this.maxSize=maxSize;
arr = new int[this.maxSize];

}
public void add(int value){
if (isFull()) {throw new RuntimeException("Arrays is empty!");}
arr[rear]=value;
rear = (rear+1)%maxSize;
}
public int get(){
if (isEmpty()) {
System.out.println("Arrays is empty!");
return -1;
}
int value = arr[front];
front =(front+1)%maxSize;
return value;
}
public void show(){
if (isEmpty()) {throw new RuntimeException("Arrays is empty!");}
for (int i = front; i < front+Size(); i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
public int showFirst(){
if (isEmpty()) {throw new RuntimeException("Arrays is empty!");}
return arr[front];
}
public int showFinal(){
if (isEmpty()) {throw new RuntimeException("Arrays is empty!");}
return arr[(rear-1+maxSize)%maxSize];
}
public boolean isFull(){ return (rear+1)%maxSize==front; }
public boolean isEmpty(){ return rear==front; }
public int Size(){ return (rear+maxSize-front)%maxSize; }


public static void main(String[] args) {
CircularQueen queue = new CircularQueen(4); //说明设置4, 其队列的有效数据最大是3
char key = ' '; // 接收用户输入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
// 输出一个菜单
while (loop) {
System.out.println("s(show): 显示队列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列取出数据");
System.out.println("h(head): 查看队列头的数据");
System.out.println("f(final): 查看队列尾的数据");
key = scanner.next().charAt(0);// 接收一个字符
switch (key) {
case 's':
try {
queue.show();
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'a':
System.out.println("输出一个数");
int value = scanner.nextInt();
queue.add(value);

break;
case 'g': // 取出数据
try {
int res = queue.get();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'h': // 查看队列头的数据
try {
int res = queue.showFirst();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'f': // 查看队列头的数据
try {
int res = queue.showFinal();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
// TODO: handle exception
System.out.println(e.getMessage());
}
break;
case 'e': // 退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}