表、栈和队列

ADT

抽象数据类型(abstract data type,ADT)是带有一组操作的对象的集合。
对于集合ADT,可以有添加、删除、包含等操作

表ADT

简单数组实现

对表的所有操作都可以通过使用数组来实现。虽然数组是有固定容量创建的,但在需要的时候可以使用双倍的容量创建一个不同的数组。
许多情形下表是通过在末端进行插入操作的,然后只对数组访问。这种情形下数组是一种恰当的实现。然而如果发生一些插入和删除操作,特别是前端进行,那么数组不是一种好的选择。

简单链表

为了避免插入和删除的线性开销,需要保证表可以不连续存储,否则表的每个部分都可能需要整体移动。
链表是由一系列的节点组成,这些节点不必在内存中相连,每个节点含有表元素和到包含该元素后继元素的节点的链,可以称之为next链,最后一个单元的next链引用null。
简单链表删除最后一项比较复杂,因为必须找出指向最后节点的项,把它的next链改成null,然后在更新持有最后节点的链,最好的做法是让每一个节点有一个指向它在表中的前面节点的链称之为双链表

java Collection API中的表

Collection接口

Collection接口扩展了Iterable接口,实现Iterable接口的类拥有增强for循环,都可以使用forEach进行循环遍历

1
2
3
4
5
6
7
8
9
public interface Collection<E> extends Iterable<E> {  
int size();
boolean isEmpty();
void clear();
boolean contains(Object o);
Iterator<E> iterator();
boolean add(E e);
boolean remove(Object o);
}

Iterator接口

1
2
3
4
5
6
7
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
}

Iterator的remove方法主要优点在于:Collection的remove方法必须先找出需要删除的项。
在迭代集合时Collection的remove会抛出ConcurrentModificationException

增强for循环

java中的增强for循环实际上编译器会重写成如下所示:

1
2
3
4
5
6
7
8
9
10
11
List<String> list = new ArrayList<>();
list.add("abc");
for (String s : list) {
System.out.println(s);
}
//等同于上面增强for循环写法
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
System.out.println(s);
}

List接口、ArrayList类和LinkedList类

1、ArrayList类提供了list ADT的一种可增长数组的实现,其优点在于对get和set的调用花费常数时间,其缺点是插入和删除代价昂贵(除了在末端进行)。
2、LinkedList类提供了list ADT的双链表实现,其优点是插入和删除均开销很小,在表的前端和末端添加和删除都是常数时间的操作,其缺点是不容易索引,get的调用是昂贵的(除了get第一个和最后一个)。
3、对搜索而言,ArrayList和LinkedList都是低效的,对Collection的contains和remove方法的调用均花费线性时间。
4、ArrayList中有个容量的概念,它标识基础数组的大小,在需要的时候会自动扩容保证至少具有表的大小,如果早期知道该大小,可以设置容量足够大的量以避免数组容量以后的扩展,trimToSize可以在所有的ArrayList添加操作完成之后使用以避免浪费空间。
5、以下方法对于LinkedList操作整个程序线性时间不是二次时间,对于ArrayList是二次时间,因为对于ArrayList即使迭代器位于需要被删除的节点上,其remove方法仍然是昂贵的,因为数组的项必须要移动

1
2
3
4
5
6
7
8
public static void remove(List<Integer> list) {
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
if (iterator.next() % 2 == 0) {
iterator.remove();
}
}
}

ListIterator接口

ListIterator扩展了Iterator接口。
1、iterator可以应用于所有的集合,Set、List和Map以及这些集合的子类型。而ListIterator只能用于List及其子类型。
2、ListIterator有hasPrevious()和previous()方法,可以实现逆向遍历,但是iterator不可以。
3、ListIterator可以定位当前索引的位置,nextIndex()和previousIndex()可以实现。Iterator没有此功能。
4、ListIterator有add方法,可以向List中添加对象,而Iterator不能。
5、ListIterator可以实现对象的修改,set()方法可以实现。Iterator仅能遍历,不能实现修改。都可以实现删除操作。
用例:它可以用来从List的所有的偶数中减去1,对于LinkedList来说,不适用ListIterator的set方法是很难做到的。

简单的ArrayList类的实现

只供参考理解,编译器会报错

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
public class MyArrayList<AnyType> implements Iterable<AnyType>  
{
private static final int DEFAULT_CAPACITY = 10;

private int theSize;
private AnyType[] theItems;

public int size()
{
return theSize;
}

public boolean isEmpty()
{
return size() == 0;
}

//调整容量符合大小
public void trimToSize()
{
ensureCapacity(size());
}
//确保数组大小足够大
public void ensureCapacity(int newCapacity)
{
if(newCapacity < theSize)
return;

//复制数据到新数组中
AnyType[] old = theItems;
theItems = (AnyType[]) new Object[newCapacity];
for(int i = 0; i <size(); i++)
{
theItems[i] = old[i];
}
}
public AnyType get(int index)
{
if(index < 0 || index >= size())
{
throw new ArrayIndexOutOfBoundsException();
}
return theItems[index];
}

public AnyType set(int index, AnyType newVal)
{
if(index < 0 || index >= size())
{
throw new ArrayIndexOutOfBoundsException();
}
AnyType old = theItems[index];
theItems[index] = newVal;
return old;
}

public void add(int index, AnyType x)
{
//数组不够大,则扩大数组
if(theItems.length == size())
{
ensureCapacity(size()*2 + 1);
}
//从index开始,元素往后移动一位
for(int i = theSize; i > index; i--)
{
theItems[i] = theItems[i - 1];
}
//index位置赋值x
theItems[index] = x;
theSize++;
}

public AanyType remove(int index)
{
AnyType removedItem = theItems[index];
for(int i = index; i < size(); i++)
{
//从index位置开始,所有元素都往前移动一位
theItems[i] = theItems[i + 1];
}
theSize--;
return removedItem;
}

public java.util.Iterator<AnyType> iterator()
{
return new ArrayListIterator<AnyType>();
}

private static class ArrayListIterator<AnyType> implements java.util.Iterator<AnyType>
{
private int current = 0;

public boolean hasNext()
{
return current < MyArrayList.this.size();
}

public AnyType next()
{
return MyArrayList.this.theItems[current++];
}

public void remove()
{
//防止迭代器的remove与MyArrayList的remove冲突
MyArrayList.this.remove(--current);
}
}
};

简单的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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
public class MyLinkedList <AnyType> implements Iterable<AnyType>{
private int theSize; //双向链表中的元素个数
private int modCount; //这个标记为了配合Iterator实现修改的保护,这一点后面专做论述,凡是做了增删修改,这个标记均变化
private Node<AnyType> beginMarker; // 双向链表的开始标记
private Node<AnyType> endMarker; //双向链表的尾部标记

public MyLinkedList()
{
// 构造函数 先初始化双向聊表 调动 clear()函数
clear();
}
public void clear()
{// 确保双向链表处于空的状态 ----> 我们使用一个辅助的头结点
// 头标记和尾标记 指向同一个 辅助头结点,和一个辅助的尾节点
beginMarker = new Node<AnyType>(null, null, null);
endMarker = new Node<AnyType>(null, beginMarker, null);
beginMarker.next = endMarker;

theSize = 0;
modCount ++; //zhege
}

// 获取元素的个数
public int size()
{
return theSize;
}

// 判断是否为空
public boolean isEmpty()
{
return theSize == 0;
}


/*
* 增删查改的操作
*/
// 默认把元素插入到尾部,其中调用插入到指定位置的函数
public boolean add(AnyType x)
{
add(size()+1, x);
return true;
}
// 把元素插入到指定位置,其中调用插入到指定元素之前 函数
public void add(int idx, AnyType x)
{
addBefore(getNode(idx), x);
}
// 重置某个节点的data值,并返回以前的 data值
public AnyType set(int idx, AnyType newVal)
{
if(idx <1 || idx >size())
throw new RuntimeException(new Exception("下表越界"));
Node<AnyType> p = getNode(idx);
AnyType oldVal = p.data;
p.data = newVal;
return oldVal;
}
// 删除第idx个节点,调用remove(Node)函数,返回删除节点的data值
public AnyType remove(int idx)
{
if(idx <1 || idx >size())
throw new RuntimeException(new Exception("下表越界"));
return remove(getNode(idx));
}



/*
* 下面这些函数都是一些private的都是位别的一些函数服务的
*/
// 在p前面插入 x 元素
private void addBefore(Node<AnyType>p, AnyType x)
{
Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize ++; //添加进来一个新元素之后,别忘了元素个数++
modCount ++; //无论增删 该标志 均++
}
// 获取 idx处的 节点引用
private Node<AnyType> getNode(int idx)
{
if(idx < 1 || idx > size()+1)// 考虑在尾部插入的情况,如果取这个尾节点,其data = null
throw new RuntimeException(new Exception("索引越界"));
Node<AnyType> p = null;
if( idx <= size()/2) // 在前半边中找
{
p = beginMarker.next;
for( int i = 1; i < idx; i++)
p = p.next;
}else{ //在后半边中找
p = endMarker;
for(int i = size(); i >= idx; i--)
p = p.prev;
}

return p;
}
// 返回 删除某个节点,并返回这个节点的data值
private AnyType remove(Node<AnyType> p)
{
p.prev.next = p.next;
p.next.prev = p.prev;
theSize --;
modCount --;
return p.data;
}


/*
* 实现迭代器
*/
public Iterator<AnyType> iterator()
{
return new LinkedListIterator();
}
//实现迭代器
private class LinkedListIterator implements Iterator<AnyType>
{
private Node<AnyType> current = beginMarker.next; //记住当前的位置,这和书序表中类似
private int expectedModCount = modCount;
private boolean okToRemove = false;

@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return current!=endMarker;
}

@Override
public AnyType next() {
// 注意了 下面的 保护迭代期间 不允许 越过迭代器修改集合元素的 机制 是精髓
if(modCount != expectedModCount)
throw new RuntimeException(new Exception("您刚刚越过迭代器修改了集合元素"));
if(!hasNext())
throw new RuntimeException(new Exception("已经没有元素了"));

AnyType nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}

@Override
public void remove() {
// TODO Auto-generated method stub
if(modCount != expectedModCount)
throw new RuntimeException(new Exception("您刚刚越过迭代器修改了集合元素"));
if(!okToRemove)
throw new RuntimeException(new Exception("先next再删除"));

MyLinkedList.this.remove(current.prev);
okToRemove = false; // 与next()中的 okToRemove = false; 遥相呼应,以确保必须在next()之后才能remove
expectedModCount ++;
}

}

/*
* 私有嵌套类的形式,定义内部节点,节点里面没有访问双向链表中的内容,所以使用私有嵌套类可也
* 如果访问了外面类的属性或者方法就只能使用内部类,去除static关键字,内部类的使用主要是为了可以简写,见单链表中的介绍
*/
private static class Node<AnyType>{
// 构造函数
public Node(AnyType d, Node<AnyType>p, Node<AnyType>n) {
data = d; prev = p; next = n;
}

public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
}

}

栈(stack)是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶端(top),对栈的操作有push(进栈)和pop(出栈),前者相对于插入,后者相对于删除最后插入的元素。
栈有时又叫做LIFO(后进先出)表。

栈的实现

由于栈是一个表,任何实现表的方法都能实现栈,ArrayList和LinkedList都支持栈操作

栈的应用

简单例子:
平衡符号:编译器检查程序的语法错误
叙述如下:做一个空栈,读入字符知道文件结尾,如果字符是个开放符号则将其推入栈中,如果是个封闭符号则当栈空时报错,否则将栈元素弹出,如果弹出的符号不是对应的开放符号则报错,在文件结尾如果栈非空则报错。

队列

队列也是表,使用队列时,插入在一段,删除则在另一端。
队列的基本操作是enqueue(入队),它在表的末端插入元素,和dequeue(出队),它删除并返回在表的开头的元素

队列的实现

如果栈的情形一样,对于队列而言任何的表的实现都是合法的

队列的应用

窗口买票的应用等所有需要先进先出的案例

开发者首页 wechat
欢迎您扫一扫上面的微信公众号