栈和队列:
一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建;
访问受限,在特定时刻,只有一个数据可被读取或删除;
是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组、链表来实现栈。
模拟栈结构
同时,只允许一个数据被访问,后进先出
对于入栈和出栈的时间复杂度都为O(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
77
78
79
80
|
public class StackS<T> { private int max; private T[] ary; private int top; //指针,指向栈顶元素的下标 public StackS( int size) { this .max = size; ary = (T[]) new Object[max]; top = - 1 ; } // 入栈 public void push(T data) { if (!isFull()) ary[++top] = data; } // 出栈 public T pop() { if (isEmpty()) { return null ; } return ary[top--]; } // 查看栈顶 public T peek() { return ary[top]; } //栈是否为空 public boolean isEmpty() { return top == - 1 ; } //栈是否满 public boolean isFull() { return top == max - 1 ; } //size public int size() { return top + 1 ; } public static void main(String[] args) { StackS<Integer> stack = new StackS<Integer>( 3 ); for ( int i = 0 ; i < 5 ; i++) { stack.push(i); System.out.println( "size:" + stack.size()); } for ( int i = 0 ; i < 5 ; i++) { Integer peek = stack.peek(); System.out.println( "peek:" + peek); System.out.println( "size:" + stack.size()); } for ( int i = 0 ; i < 5 ; i++) { Integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); } System.out.println( "----" ); for ( int i = 5 ; i > 0 ; i--) { stack.push(i); System.out.println( "size:" + stack.size()); } for ( int i = 5 ; i > 0 ; i--) { Integer peek = stack.peek(); System.out.println( "peek:" + peek); System.out.println( "size:" + stack.size()); } for ( int i = 5 ; i > 0 ; i--) { Integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); } } } |
上面的例子,有一个maxSize的规定,因为数组是要规定大小的,若想无限制,可以使用其他结构来做存储,当然也可以new一个新的长度的数组。
例,使用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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
public class StackSS<T> { private LinkedList<T> datas; public StackSS() { datas = new LinkedList<T>(); } // 入栈 public void push(T data) { datas.addLast(data); } // 出栈 public T pop() { return datas.removeLast(); } // 查看栈顶 public T peek() { return datas.getLast(); } //栈是否为空 public boolean isEmpty() { return datas.isEmpty(); } //size public int size() { return datas.size(); } public static void main(String[] args) { StackS<Integer> stack = new StackS<Integer>( 3 ); for ( int i = 0 ; i < 5 ; i++) { stack.push(i); System.out.println( "size:" + stack.size()); } for ( int i = 0 ; i < 5 ; i++) { Integer peek = stack.peek(); System.out.println( "peek:" + peek); System.out.println( "size:" + stack.size()); } for ( int i = 0 ; i < 5 ; i++) { Integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); } System.out.println( "----" ); for ( int i = 5 ; i > 0 ; i--) { stack.push(i); System.out.println( "size:" + stack.size()); } for ( int i = 5 ; i > 0 ; i--) { Integer peek = stack.peek(); System.out.println( "peek:" + peek); System.out.println( "size:" + stack.size()); } for ( int i = 5 ; i > 0 ; i--) { Integer pop = stack.pop(); System.out.println( "pop:" + pop); System.out.println( "size:" + stack.size()); } } } |
例,单词逆序,使用Statck结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class WordReverse { public static void main(String[] args) { reverse( "株式会社" ); } static void reverse(String word) { if (word == null ) return ; StackSS<Character> stack = new StackSS<Character>(); char [] charArray = word.toCharArray(); int len = charArray.length; for ( int i = 0 ; i <len; i++ ) { stack.push(charArray[i]); } StringBuilder sb = new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pop()); } System.out.println( "反转后:" + sb.toString()); } } |
打印:
1
|
反转后:社会式株 |
模拟队列(一般队列、双端队列、优先级队列)
队列:
先进先出,处理类似排队的问题,先排的,先处理,后排的等前面的处理完了,再处理
对于插入和移除操作的时间复杂度都为O(1),从后面插入,从前面移除
双端队列:
即在队列两端都可以insert和remove:insertLeft、insertRight,removeLeft、removeRight
含有栈和队列的功能,如去掉insertLeft、removeLeft,那就跟栈一样了;如去掉insertLeft、removeRight,那就跟队列一样了
一般使用频率较低,时间复杂度 O(1)
优先级队列:
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置,时间复杂度O(N), 删除O(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
77
78
79
80
81
82
83
84
85
86
87
|
/* * 队列 先进先出,一个指针指示插入的位置,一个指针指示取出数据项的位置 */ public class QueueQ<T> { private int max; private T[] ary; private int front; //队头指针 指示取出数据项的位置 private int rear; //队尾指针 指示插入的位置 private int nItems; //实际数据项个数 public QueueQ( int size) { this .max = size; ary = (T[]) new Object[max]; front = 0 ; rear = - 1 ; nItems = 0 ; } //插入队尾 public void insert(T t) { if (rear == max - 1 ) { //已到实际队尾,从头开始 rear = - 1 ; } ary[++rear] = t; nItems++; } //移除队头 public T remove() { T temp = ary[front++]; if (front == max) { //列队到尾了,从头开始 front = 0 ; } nItems--; return temp; } //查看队头 public T peek() { return ary[front]; } public boolean isEmpty() { return nItems == 0 ; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQ<Integer> queue = new QueueQ<Integer>( 3 ); for ( int i = 0 ; i < 5 ; i++) { queue.insert(i); System.out.println( "size:" + queue.size()); } for ( int i = 0 ; i < 5 ; i++) { Integer peek = queue.peek(); System.out.println( "peek:" + peek); System.out.println( "size:" + queue.size()); } for ( int i = 0 ; i < 5 ; i++) { Integer remove = queue.remove(); System.out.println( "remove:" + remove); System.out.println( "size:" + queue.size()); } System.out.println( "----" ); for ( int i = 5 ; i > 0 ; i--) { queue.insert(i); System.out.println( "size:" + queue.size()); } for ( int i = 5 ; i > 0 ; i--) { Integer peek = queue.peek(); System.out.println( "peek:" + peek); System.out.println( "size:" + queue.size()); } for ( int i = 5 ; i > 0 ; i--) { Integer remove = queue.remove(); System.out.println( "remove:" + remove); System.out.println( "size:" + queue.size()); } } } |
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
|
/* * 双端队列<span style="white-space:pre"> </span>两端插入、删除 */ public class QueueQT<T> { private LinkedList<T> list; public QueueQT() { list = new LinkedList<T>(); } // 插入队头 public void insertLeft(T t) { list.addFirst(t); } // 插入队尾 public void insertRight(T t) { list.addLast(t); } // 移除队头 public T removeLeft() { return list.removeFirst(); } // 移除队尾 public T removeRight() { return list.removeLast(); } // 查看队头 public T peekLeft() { return list.getFirst(); } // 查看队尾 public T peekRight() { return list.getLast(); } public boolean isEmpty() { return list.isEmpty(); } public int size() { return list.size(); } } |
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
|
/* * 优先级队列 队列中按优先级排序,是一个有序的队列 */ public class QueueQP { private int max; private int [] ary; private int nItems; //实际数据项个数 public QueueQP( int size) { this .max = size; ary = new int [max]; nItems = 0 ; } //插入队尾 public void insert( int t) { int j; if (nItems == 0 ) { ary[nItems++] = t; } else { for (j = nItems - 1 ; j >= 0 ; j--) { if (t > ary[j]) { ary[j + 1 ] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序,给定序列本来就是有序的,所以效率O(N) } else { break ; } } ary[j + 1 ] = t; nItems++; } System.out.println(Arrays.toString(ary)); } //移除队头 public int remove() { return ary[--nItems]; //移除优先级小的 } //查看队尾 优先级最低的 public int peekMin() { return ary[nItems - 1 ]; } public boolean isEmpty() { return nItems == 0 ; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQP queue = new QueueQP( 3 ); queue.insert( 1 ); queue.insert( 2 ); queue.insert( 3 ); int remove = queue.remove(); System.out.println( "remove:" + remove); } } |