Stack and Queue
对应官方的java.util.stack
stack的实现:使用线性表或者链表
而stack最长涉及到的操作是:push and pop
stack涉及到的算法：
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
|
/**
* 元素入栈 只能从栈顶出栈
* @param element
*/
public void push(E element);
/**
*元素出栈 只能从栈顶出栈
* @return
*/
public E pop();
/**
* 获取栈顶元素
* @return
*/
public E peek();
/***********下面这些算法可以复用线性表的算法**************/
/**
* 查看stack内元素数量
* @return
*/
public int size();
/**
* 判断stack内是否为空
* @return
*/
public boolean isEmpty();
/**
* 清空栈内元素
* @return
*/
public void clear();
|
实现功能:可以从front入队和rear出对 对应官方的LinkedList
实现方式:使用链表或者double stack
Time Complexity:在front进行出对和在rear进行入队的Time Complexity都是O(1);如果使用SequenceList在front进行出对的Time Complexity是O(n),在rear进行入队的Time Complexity是O(1).
但是在CircleQueue中我们将使用动态数组实现循环队列并且将各个函数都优化到O(1)的time complexity
Queue涉及到的算法
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
|
/**
* 元素数量
* @return
*/
public int size()
/**
* 是否为空
* @return
*/
public boolean isEmpty()
/**
* 入队
*/
public void enQueue(E element)
{
//从对尾rear入队
list.add(list.size(),element);
}
/**
* 出对 只能从front出对
*/
public E deQueue()
/**
* 获取对头元素
* @return
*/
public E front()
/**
* 清空queue
*/
public void clear()
|
使用双向链表
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
|
private LinkList<E> list = new LinkList<>();
/**
* 元素数量
* @return
*/
public int size()
{
return list.size();
}
/**
* 是否为空
* @return
*/
public boolean isEmpty()
{
return list.isEmpty();
}
/**
* 入队
*/
public void enQueue(E element)
{
//从对尾入队
list.add(list.size(),element);
}
/**
* 出对
*/
public E deQueue()
{
//从对头出对
return list.remove(0);
}
/**
* 获取对头元素
* @return
*/
public E front()
{
return list.get(0);
}
/**
* 清空queue
*/
public void clear()
{
list.clear();
}
|
使用double stack实现
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
|
private Stack<E> inStack = new Stack<>();
private Stack<E> outStack = new Stack<>();
/**
* 元素数量
*
* @return
*/
public int size()
{
return inStack.size()+outStack.size();
}
/**
* 是否为空
*
* @return
*/
public boolean isEmpty() {
return inStack.isEmpty()&&outStack.isEmpty();
}
/**
* 入队
*/
public void enQueue(E element) {
//push到inStack中
inStack.push(element);
}
/**
* 出对
*/
public E deQueue() {
//如果outStack为空
if(outStack.isEmpty()) {
//将inStack所有元素pop到outStack 再弹出栈顶元素
while (!inStack.isEmpty()) {
E e = inStack.pop();
outStack.push(e);
}
}
//如果outstack不为空 就直接弹出栈顶元素
return outStack.pop();
}
/**
* 获取对头元素
* @return
*/
public E front() {
if (outStack.isEmpty()) {
//将inStack所有元素pop到outStack 再弹出栈顶元素
while (!inStack.isEmpty()) {
E e = inStack.pop();
outStack.push(e);
}
}
//如果outstack不为空 就直接弹出栈顶元素
return outStack.pop();
}
/**
* 清空queue
*/
public void clear()
{
inStack.clear();
outStack.clear();
}
|
实现功能:可以从front入队和rear出对的循环队列
实现方式:使用动态数组实现（需要一个索引front指明对头的位置还需要一个数组字段和查看目前数组内元素数量的size字段）
循环的含义：接下来不会直接扩容 会将0和1位置填满后再进行扩容
CircleQueue涉及到的算法:
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
|
/**
* 元素数量
* @return
*/
public int size()
/**
* 是否为空
* @return
*/
public boolean isEmpty()
/**
* 入队
*/
public void enQueue(E element)
/**
* 出对 只能从front出对
*/
public E deQueue()
/**
* 获取对头元素
* @return
*/
public E front()
/**
* 清空queue
*/
public void clear()
/**
* 扩容
*/
private void ensureCapacity(int capacity)
|
考虑普通情况下的入队算法
1
2
|
elements[front + size] = element;
//2 + 3
|
如果顺序已经存满,考虑循环存储
1
2
|
elements[(front + size) % elements.length] = element;
2 + 5 % 7
|
1
2
3
|
因此将将真实索引(i)转化为循环队列上的索引(index)的公式为:
index = (front + i) % elements.length
真实的索引:数组上的（顺序）索引 按照正常情况来说 元素应该在第i位置上 front的真实索引就是0
|
1
2
3
4
5
6
7
8
9
10
11
12
|
/**
* 算法描述：
1.判断容量是否足够
2.使用入队算法(只能从尾部入队)
3.size++;
*/
public void enQueue(E element)
{
ensureCapacity(size+1);
elements[(front + size) % elements.length] = element;
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/**
* 算法描述:
1.保存要出对的元素
2.将front索引所指位置内容null
2.size--;
3.front索引向前移动
*/
public E deQueue()
{
E e = elements[front];
elements[front]=null;
size--;
front = (front + 1) % elements.length;
return e;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
|
/**
* 算法分析:因为清空算法要保证清空的效率，所以只用清空有存储的数组位置，null的 位置不用清空
1.直接使用清空算法
*/
public void clear()
{
for (int i = 0; i < size; i++) {
elements[(front + i) % elements.length] = null;
}
this.size = 0 ;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**
* 算法分析
1.判断容量是否满足
2.创建新的数组
3.挪动
4.将老数组指向新数组并将起始位置指针指向索引0处
*/
private void ensureCapacity(int capacity)
{
int oldCapacity = elements.length;
if (capacity<=oldCapacity) return;
System.out.println(oldCapacity);
int newCapacity =oldCapacity + (oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
//将老数组挪动到新到数组
for (int i = 0; i < size; i++) {
newElements[i] = elements[(front + i) % elements.length];
}
elements = newElements;
//挪动结束后 要把front索引清0
front = 0;
}
|
Circle Queue可以优化的地方主要是
1
2
3
4
|
private int getIndex(int index)
{
return (front + index) % elements.length;
}
|
1
2
3
|
//要求m<2n n>0
m%n
(m>=n) ? m-n:n
|
实现功能:能够在双端(front&rear)进行删除和添加操作，对应LinkedList
实现方法:使用链表实现time complexity为O（1）
Queue涉及到的算法：
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
|
/**
* 元素数量
* @return
*/
public int size()
/**
* 是否为空
* @return
*/
public boolean isEmpty()
/**
*从front入队
*/
public void enQueueFront(E element)
/**
*从rear入队
*/
public void enQueueRear(E element)
/**
* 出对 从front出对
*/
public E deQueueFront()
/**
* 出对 从rear出对
*/
public E deQueueRear()
/**
* 获取对头元素
* @return
*/
public E getFront()
/**
* 获取队尾元素
* @return
*/
public E getRear()
/**
* 清空queue
*/
public void clear()
|
实现功能:可以从front入队和出对和rear入队和出对的循环队列
实现方式:使用动态数组实现（需要一个索引front指明对头的位置还需要一个数组字段）
循环的含义：接下来不会直接扩容 会将0和1位置填满后再进行扩容
双端循环队列和循环队列的不同点在于:双端循环队列在front可以插入元素，这就导致了插入算法的设计要添加
CircleQueue涉及到的算法:
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
|
/**
* 元素数量
* @return
*/
public int size()
/**
* 是否为空
* @return
*/
public boolean isEmpty()
/**
*从front入队
*/
public void enQueueFront(E element)
/**
*从rear入队
*/
public void enQueueRear(E element)
/**
* 出对 从front出对
*/
public E deQueueFront()
/**
* 出对 从rear出对
*/
public E deQueueRear()
/**
* 获取对头元素
* @return
*/
public E getFront()
/**
* 获取队尾元素
* @return
*/
public E getRear()
/**
* 清空queue
*/
public void clear()
/**
* 扩容
*/
private void ensureCapacity(int capacity)
|
(同循环队列)
考虑普通rear入对
1
2
3
4
|
elements[(front-1)%elements.length] = element;
front--;
size++;
|
假设front == 0;
1
2
3
|
elements[(front-1)+elements.length] = element;
front--;
size++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/**
算法分析:
1.索引合法性检查
2.在真实索引-1(如果用SequenceList来看就是-1位置)插入(这里将索引转化公式封装)
3.将front索引指向第一个元素
4.size++
*/
public void enQueueFront(E element)
{
//索引合法性检查
ensureCapacity(size+1);
//使用索引转化公式得到-1处的索引位置
elements[getIndex(-1)] = element;
//将front索引指向第一个元素
front = getIndex(-1);
size++;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/**
算法分析:
1.如果index<0直接用front + index +elements.length即可
2.否则使用普通的索引转化公式
@param index表示以0作为开头时插入位置
@return 返回的是以front作为开头时的插入位置
*/
private int getIndex(int index)
{
index+=front;
//如果front在0位置
if (index<0)
{
return index + elements.length;
}
return index%elements.length;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/**
* 算法分析:
1.保留要删除的元素
2.将其要删除位置置为空
3.将front遇到
4.size--
5.返回删除的元素
*/
public E deQueueFront()
{
E e = elements[getIndex(0)];
elements[getIndex(0)] = null;
front = getIndex(1);
size--;
return e;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
/**
* 算法分析:
1.保留要删除的元素
2.将其要删除位置置为空
3.size--
4.返回删除的元素
*/
public E deQueueRear()
{
E e = elements[getIndex(size-1)];
elements[getIndex(size-1)] = null;
size--;
return e;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/**
* 扩容算法和circle queue的扩容算法一样
*/
private void ensureCapacity(int capacity)
{
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
int newCapacity = oldCapacity +(oldCapacity>>1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[getIndex(i)];
}
elements = newElements;
front =0;
}
|