数据结构——ArrayStack和LinkedStack的实现

栈是一种后进先出(LIFO)的数据结构。ArrayStack使用数组来实现,LinkedStack使用链表来实现,各有特点,也都非常简单。可以说这两个版本就是SimpleArrayListSimpleLinkedList的简化版。

ArrayStack

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
import java.util.NoSuchElementException;
public class ArrayStack<T> {
private static int DEFAULT_CAPACITY = 64;
private T[] elements;
/**
* 栈顶索引
*/
private int top = -1;
public ArrayStack(){
this(DEFAULT_CAPACITY);
}
public ArrayStack(int capacity){
ensureCapacity(capacity);
}
public int size(){
return top+1;
}
public boolean isEmpty(){
return top == -1;
}
/**
* 入栈
* @param ele
*/
public void push(T ele){
/* 如果栈容量已经满了,则扩展栈大小 */
if(size() == elements.length)
ensureCapacity(2 * size() + 1);
/* 将元素添加到栈顶,并修改栈顶索引 */
elements[++top] = ele;
}
/**
* 出栈
* @return
* @throws NoSuchElementException
*/
public T pop() throws NoSuchElementException{
/* 如果为空栈,则抛出异常 */
if(isEmpty())
throw new NoSuchElementException("Stack is empty.");
/* 返回栈顶元素,并修改栈顶位置 */
return elements[top--];
}
/**
* 重置栈容量大小,可用于扩展栈容量大小
* @param newCapacity
*/
@SuppressWarnings("unchecked")
private void ensureCapacity(int newCapacity){
if(newCapacity < size())
return;
T[] old = elements;
elements = (T[]) new Object[newCapacity];
for(int i=0; i < size(); i++){
elements[i] = old[i];
}
}
@Override
public String toString() {
return "top = " + top + " size = " + size();
}
}

LinkedStack

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
import java.util.NoSuchElementException;
public class LinkedStack<T> {
private Node<T> head;
private int size = 0;
public LinkedStack(){
head = new Node<T>(null, null);
}
public int size(){
return size;
}
public boolean isEmpty(){
return size() == 0;
}
/**
* 入栈操作
* @param ele
*/
public void push(T ele){
Node<T> newNode = new Node<T>(ele, head.next);
head.next = newNode;
size++;
}
/**
* 出栈操作,弹出栈顶元素
* @return 返回栈顶元素值
* @throws NoSuchElementException
*/
public T pop() throws NoSuchElementException{
if(isEmpty())
throw new NoSuchElementException("Stack is empty.");
T popElement = head.next.data;
head.next = head.next.next;
size--;
return popElement;
}
@Override
public String toString() {
return "size = " + size();
}
private static class Node<T>{
public T data;
public Node<T> next;
public Node(T data, Node<T> next){
this.data = data;
this.next = next;
}
}
}