[データ構造とアルゴリズム]スタックStackの多様な実装
28175 ワード
![[数据结构与算法]栈Stack的多种实现](https://s1.md5.ltd/image/a96fe6af51457d389b5314b442afd62d.png)
宣言:
オリジナル作品、
転載時に文章の出所を明記してください
SAP師太
技術ブログ(博/客/園www.cnblogs.com):www.cnblogs.com/jiangzhengjun,
文章の元の出所をハイパーリンク形式で表示します.
さもないと法律の責任を追及します!原文リンク:http://www.cnblogs.com/jiangzhengjun/p/4289864.html
1 package stack;
2
3 /**
4 *
5 * @author jzj
6 *
7 * @param <E>
8 */
9 public interface Stack<E> {
10 //
11 public void push(E e);
12
13 //
14 public E pop();
15
16 //
17 public E peek();
18
19 //
20 public int size();
21
22 //
23 public boolean isEmpty();
24 } 1 package stack;
2
3 /**
4 *
5 * @author jzj
6 *
7 * @param <E>
8 */
9 public class LinkedStack<E> implements Stack<E> {
10 private class Node {
11 E data;//
12 Node next;//next
13
14 Node() {//
15 data = null;
16 next = null;
17 }
18
19 /**
20 *
21 * @param data
22 * @param next next
23 */
24 Node(E data, Node next) {
25 this.data = data;
26 this.next = next;
27 }
28
29 //
30 boolean isEnd() {
31 return data == null && next == null;
32 }
33 }
34
35 /*
36 * ， data next null ， ，
37 * ， ： top ，
38 * ，
39 */
40 private Node top = new Node();
41
42 //
43 public void push(E data) {
44 //
45 top = new Node(data, top);
46 }
47
48 //
49 public E pop() {
50 // ， null
51 E data = top.data;
52 if (!top.isEnd()) {// ，
53 top = top.next;
54 }
55 return data;
56 }
57
58 //
59 public E peek() {
60 // ， null
61 return top.data;
62 }
63
64 //
65 public int size() {
66 int size = 0;
67 Node tmpTop = top;
68 while (tmpTop.next != null) {
69 size++;
70 tmpTop = tmpTop.next;
71 }
72 return size;
73 }
74
75 //
76 public boolean isEmpty() {
77 return top.isEnd();
78 }
79 } 1 package stack;
2
3 import java.util.LinkedList;
4
5 /**
6 * LinkedList
7 * @author jzj
8 *
9 * @param <E>
10 */
11 public class LinkedListStack<E> implements Stack<E> {
12 private LinkedList<E> list = new LinkedList<E>();
13
14 //
15 public void push(E e) {
16 list.addFirst(e);
17 }
18
19 //
20 public E pop() {
21 return list.removeFirst();
22 }
23
24 //
25 public E peek() {
26 return list.getFirst();
27 }
28
29 //
30 public int size() {
31 return list.size();
32 }
33
34 //
35 public boolean isEmpty() {
36 return list.isEmpty();
37 }
38 } 1 package stack;
2
3 /**
4 *
5 * @author jzj
6 *
7 * @param <E>
8 */
9 public class ArrayStack<E> implements Stack<E> {
10 private E[] data;
11 private int top = -1;//
12 private int size = 3;
13
14 public ArrayStack() {
15 data = (E[]) new Object[size];
16 }
17
18 //
19 public void push(E e) {
20 if ((top + 1) == size) {
21 throw new IllegalStateException("stack full...");
22 }
23 data[++top] = e;
24 }
25
26 //
27 public E pop() {
28 if (top == -1) {
29 throw new IllegalStateException("stack empty...");
30 }
31 E tmp = data[top];
32 // ， ，
33 data[top] = null;
34 top--;
35 return tmp;
36 }
37
38 //
39 public E peek() {
40 if (top == -1) {
41 throw new IllegalStateException("stack empty...");
42 }
43 return data[top];
44 }
45
46 //
47 public int size() {
48 return top + 1;
49 }
50
51 //
52 public boolean isEmpty() {
53 return top == -1;
54 }
55 } 1 package stack;
2
3 import java.util.ArrayList;
4
5 /**
6 * ArrayList
7 * @author jzj
8 *
9 * @param <E>
10 */
11 public class ArrayListStack<E> implements Stack<E> {
12 private ArrayList<E> list = new ArrayList<E>();
13
14 //
15 public void push(E e) {
16 list.add(e);//ArrayList ，
17 }
18
19 //
20 public E pop() {
21 return list.remove(list.size() - 1);//
22 }
23
24 //
25 public E peek() {
26 return list.get(list.size() - 1);
27 }
28
29 //
30 public int size() {
31 return list.size();
32 }
33
34 //
35 public boolean isEmpty() {
36 return list.isEmpty();
37 }
38 }