haohao

数据结构与算法(Java 实现)之线性表(三)

Markdown

生活苟且的人,傻了吧唧的去了诗和远方;而鼓吹诗和远方的人,工作比谁都积极。

本篇简单介绍一下栈和队列的实现,它们是数据结构与算法中非常重要的基础。

栈(Stack)

stack

是限定在表尾进行插入和删除的线性表。允许插入的端称为栈顶,另一端称为栈底。

栈的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
public interface Stack<T> {
T pop();
void push(T item);
int size();
boolean isEmpty();
}

栈的实现(链栈)

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
public class LinkedStack<T> implements Stack<T> {
private Node head;
private int count;
public LinkedStack() {
head = null;
count = 0;
}
@Override
public T pop() {
if (head == null) {
throw new IllegalStateException("the stack is null.");
}
Node node = head;
head = head.getNext();
node.setNext(null);
return (T) node.getElement();
}
@Override
public void push(T item) {
Node node = new Node(item);
node.setNext(head);
head = node;
count ++;
}
@Override
public int size() {
return count;
}
@Override
public boolean isEmpty() {
return count == 0;
}
@Override
public String toString() {
if (head == null) {
return null;
} else {
Node p = head;
StringBuilder stringBuilder = new StringBuilder();
while (p != null) {
stringBuilder.append(p.getElement()).append("\n");
p = p.getNext();
}
return stringBuilder.toString();
}
}
public static void main(String[] args) {
LinkedStack<String> linkedStack = new LinkedStack<String>();
linkedStack.push("Android");
linkedStack.push("iOS");
linkedStack.push("Kotlin");
System.out.println(linkedStack.toString());
System.out.println("pop -> " + linkedStack.pop());
System.out.println("pop -> " + linkedStack.pop());
System.out.println(linkedStack.toString());
}
}

输出:

1
2
3
4
5
6
7
Kotlin
iOS
Android
pop -> Kotlin
pop -> iOS
Android

队列(Queue)

queue

队列是只允许在一端进行插入操作,在另一端进行删除操作的线性表。队列是一种先进先出的线性表(FIFO)。允许插入的一段称为队尾,允许删除的一端称为队头。

队列的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
public interface Queue<T> {
void enQueue(T item);
T deQueue();
T peek();
int size();
boolean isEmpty();
}

队列实现(链队列)

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
public class LinkedQueue<T> implements Queue<T> {
private int size;
private Node head;
public LinkedQueue() {
size = 0;
head = null;
}
@Override
public void enQueue(T item) {
Node node = new Node(item);
if (head == null) {
head = node;
} else {
Node p = head;
Node prev = null;
while (p != null) {
prev = p;
p = p.getNext();
}
prev.setNext(node);
}
size++;
}
@Override
public T deQueue() {
if (head == null) {
throw new IllegalStateException("the queue is empty.");
}
Node node = head;
head = head.getNext();
node.setNext(null);
size --;
return (T) node.getElement();
}
@Override
public T peek() {
return (T) head.getElement();
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (isEmpty()) {
return null;
} else {
StringBuilder stringBuilder = new StringBuilder();
Node p = head;
while (p != null) {
stringBuilder.append(p.getElement()).append("\n");
p = p.getNext();
}
return stringBuilder.toString();
}
}
public static void main(String[] args) {
LinkedQueue<String> linkedQueue = new LinkedQueue<String>();
linkedQueue.enQueue("Android");
linkedQueue.enQueue("iOS");
linkedQueue.enQueue("Kotlin");
linkedQueue.enQueue("Java");
System.out.println(linkedQueue.toString());
System.out.println("LinkedQueue dequeue -> " + linkedQueue.deQueue());
System.out.println("LinkedQueue dequeue -> " + linkedQueue.deQueue());
System.out.println(linkedQueue.toString());
}
}

输出:

1
2
3
4
5
6
7
8
9
Android
iOS
Kotlin
Java
LinkedQueue dequeue -> Android
LinkedQueue dequeue -> iOS
Kotlin
Java



联系我

Wechat ID

公众号

生活不止于眼前的苟且, 还有诗和远方的田野