棧和隊(duì)列：
一般是作為程序員的工具，用于輔助構(gòu)思算法，生命周期較短，運(yùn)行時(shí)才被創(chuàng)建；
訪問受限，在特定時(shí)刻，只有一個(gè)數(shù)據(jù)可被讀取或刪除；
是一種抽象的結(jié)構(gòu)，內(nèi)部的實(shí)現(xiàn)機(jī)制，對用戶不可見，比如用數(shù)組、鏈表來實(shí)現(xiàn)棧。
模擬棧結(jié)構(gòu)
同時(shí)，只允許一個(gè)數(shù)據(jù)被訪問，后進(jìn)先出
對于入棧和出棧的時(shí)間復(fù)雜度都為O(1),即不依賴棧內(nèi)數(shù)據(jù)項(xiàng)的個(gè)數(shù)，操作比較快
例，使用數(shù)組作為棧的存儲結(jié)構(gòu)
|
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; //指針，指向棧頂元素的下標(biāo) 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()); } } } |
上面的例子，有一個(gè)maxSize的規(guī)定，因?yàn)閿?shù)組是要規(guī)定大小的，若想無限制，可以使用其他結(jié)構(gòu)來做存儲，當(dāng)然也可以new一個(gè)新的長度的數(shù)組。
例，使用LinkedList存儲來實(shí)現(xiàn)棧
|
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結(jié)構(gòu)
|
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("反轉(zhuǎn)后：" + sb.toString()); } } |
打印：
|
1
|
反轉(zhuǎn)后：社會式株 |
模擬隊(duì)列(一般隊(duì)列、雙端隊(duì)列、優(yōu)先級隊(duì)列)
隊(duì)列：
先進(jìn)先出，處理類似排隊(duì)的問題，先排的，先處理，后排的等前面的處理完了，再處理
對于插入和移除操作的時(shí)間復(fù)雜度都為O(1)，從后面插入，從前面移除
雙端隊(duì)列：
即在隊(duì)列兩端都可以insert和remove：insertLeft、insertRight，removeLeft、removeRight
含有棧和隊(duì)列的功能，如去掉insertLeft、removeLeft，那就跟棧一樣了；如去掉insertLeft、removeRight，那就跟隊(duì)列一樣了
一般使用頻率較低，時(shí)間復(fù)雜度 O(1)
優(yōu)先級隊(duì)列：
內(nèi)部維護(hù)一個(gè)按優(yōu)先級排序的序列。插入時(shí)需要比較查找插入的位置，時(shí)間復(fù)雜度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
|
/* * 隊(duì)列 先進(jìn)先出，一個(gè)指針指示插入的位置，一個(gè)指針指示取出數(shù)據(jù)項(xiàng)的位置 */public class QueueQ<T> { private int max; private T[] ary; private int front; //隊(duì)頭指針 指示取出數(shù)據(jù)項(xiàng)的位置 private int rear; //隊(duì)尾指針 指示插入的位置 private int nItems; //實(shí)際數(shù)據(jù)項(xiàng)個(gè)數(shù) public QueueQ(int size) { this.max = size; ary = (T[]) new Object[max]; front = 0; rear = -1; nItems = 0; } //插入隊(duì)尾 public void insert(T t) { if (rear == max - 1) {//已到實(shí)際隊(duì)尾，從頭開始 rear = -1; } ary[++rear] = t; nItems++; } //移除隊(duì)頭 public T remove() { T temp = ary[front++]; if (front == max) {//列隊(duì)到尾了，從頭開始 front = 0; } nItems--; return temp; } //查看隊(duì)頭 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
|
/* * 雙端隊(duì)列<span style="white-space:pre"> </span>兩端插入、刪除 */public class QueueQT<T> { private LinkedList<T> list; public QueueQT() { list = new LinkedList<T>(); } // 插入隊(duì)頭 public void insertLeft(T t) { list.addFirst(t); } // 插入隊(duì)尾 public void insertRight(T t) { list.addLast(t); } // 移除隊(duì)頭 public T removeLeft() { return list.removeFirst(); } // 移除隊(duì)尾 public T removeRight() { return list.removeLast(); } // 查看隊(duì)頭 public T peekLeft() { return list.getFirst(); } // 查看隊(duì)尾 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
|
/* * 優(yōu)先級隊(duì)列 隊(duì)列中按優(yōu)先級排序，是一個(gè)有序的隊(duì)列 */public class QueueQP { private int max; private int[] ary; private int nItems; //實(shí)際數(shù)據(jù)項(xiàng)個(gè)數(shù) public QueueQP(int size) { this.max = size; ary = new int[max]; nItems = 0; } //插入隊(duì)尾 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]; //前一個(gè)賦給后一個(gè) 小的在后 相當(dāng)于用了插入排序，給定序列本來就是有序的，所以效率O(N) } else { break; } } ary[j + 1] = t; nItems++; } System.out.println(Arrays.toString(ary)); } //移除隊(duì)頭 public int remove() { return ary[--nItems]; //移除優(yōu)先級小的 } //查看隊(duì)尾 優(yōu)先級最低的 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); } } |
