Fork me on GitHub

数据结构-栈和队列

Stack

  • 栈也是一种线性结构
  • 相比数组,栈对应的操作是数组的子集
  • 栈是一种后进先出的数据结构(LIFO)
  • 只能从一端添加元素,也只能从一端取出元素
  • 这一端称为栈顶

栈的应用是非常广泛的,如无处不在的撤销操作,程序运行时调用的系统栈,剪贴板里面的内容等等

创建自己的栈

首先确定栈的方法,创建栈的接口

1
2
3
4
5
6
7
8
public interface Stack<E> {

int getSize();
boolean isEmpty();
void push(E e); //入栈
E pop(); //出栈
E peek(); //看一下栈顶元素
}

借用上面自定义中的数组来实现栈
创建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
public class ArrayStack<E> implements Stack<E> {

private Array<E> array;

public ArrayStack(int capacity){
array = new Array<>(capacity);
}

public ArrayStack(){
array = new Array<>();
}

@Override
public int getSize(){
return array.getSize();
}

@Override
public boolean isEmpty(){
return array.isEmpty();
}

public int getCapacity(){
return array.getCapacity();
}

@Override
public void push(E e){
array.addLast(e);
}

@Override
public E pop(){
return array.removeLast();
}

@Override
public E peek(){
return array.getLast();
}

@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append('[');
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] top");
return res.toString();
}
}

根据栈的特性,在Array类中添加两个方法

1
2
3
4
5
6
7
8
public E getLast(){
return get(size - 1);
}


public E getFirst(){
return get(0);
}

创建main函数进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {

public static void main(String[] args) {

ArrayStack<Integer> stack = new ArrayStack<>();

for(int i = 0 ; i < 5 ; i ++){
stack.push(i*i);
System.out.println(stack);
}

stack.pop();
System.out.println(stack);
}
}

结果

1
2
3
4
5
6
Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 4] top
Stack: [0, 1, 4, 9] top
Stack: [0, 1, 4, 9, 16] top
Stack: [0, 1, 4, 9] top

时间复杂度分析

pushpop可能会触发resize操作

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void push(E e); O(1) 均摊
  • E pop(); O(1) 均摊
  • E peek(); O(1)

Queue

  • 栈队列也是一种线性结构
  • 相比数组, 队列对应的操作也是数组的子集
  • 队列是一种先进先出的数据结构(FIFO)
  • 只能从一端(队尾)添加元素,也只能从一端(队首)取出元素

创建自己的队列

确定队列的方法, 创建队列的接口

1
2
3
4
5
6
7
8
public interface Queue<E> {

int getSize();
boolean isEmpty();
void enqueue(E e); //入队
E dequeue(); //出队
E getFront(); //查看队首
}

依然使用自己创建的动态数组来实现队列
创建ArrayQueue类, 实现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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class ArrayQueue<E> implements Queue<E> {

private Array<E> array;

public ArrayQueue(int capacity){
array = new Array<>(capacity);
}

public ArrayQueue(){
array = new Array<>();
}

@Override
public int getSize(){
return array.getSize();
}

@Override
public boolean isEmpty(){
return array.isEmpty();
}

public int getCapacity(){
return array.getCapacity();
}

@Override
public void enqueue(E e){
array.addLast(e);
}

@Override
public E dequeue(){
return array.removeFirst();
}

@Override
public E getFront(){
return array.getFirst();
}

@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
for(int i = 0 ; i < array.getSize() ; i ++){
res.append(array.get(i));
if(i != array.getSize() - 1)
res.append(", ");
}
res.append("] tail");
return res.toString();
}

public static void main(String[] args) {

//每入队三个, 出队一个
ArrayQueue<Integer> queue = new ArrayQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
Queue: front [0] tail
Queue: front [0, 1] tail
Queue: front [0, 1, 2] tail
Queue: front [1, 2] tail
Queue: front [1, 2, 3] tail
Queue: front [1, 2, 3, 4] tail
Queue: front [1, 2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5, 6] tail
Queue: front [2, 3, 4, 5, 6, 7] tail
Queue: front [2, 3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8, 9] tail

时间复杂度

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void enqueue(E e); O(1) 均摊
  • E dequeue(); O(n)
  • E getFront(); O(1)

循环队列

数组队列在出队时由于需要将后面的元素都向前挪一位,时间复杂度是O(n),如果使用循环队列,时间复杂度就会降低

创建LoopQueue类,进行测试

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
public class LoopQueue<E> implements Queue<E> {

private E[] data;
private int front, tail;
private int size;

//由于判空的条件是front == tail,
//当front不在下标为o的位置,队列满时,tail会从头开始
//因为判空条件是front == tail,
//所以判满条件是(tail + 1) % data.length == front
//这样就应该在创建队列时多开辟一个空间
// front
// ↓
//⏹⏹⏹⏹⏹⏹⏹⏹⏹
// ↑
// tail
public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}

public LoopQueue(){
this(10);
}

public int getCapacity(){
return data.length - 1;
}

@Override
public boolean isEmpty(){
return front == tail;
}

@Override
public int getSize(){
return size;
}

// 入队时首先判断一下队列是否已满
// 已满的话需要进行扩容
@Override
public void enqueue(E e){

if((tail + 1) % data.length == front)
resize(getCapacity() * 2);

data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}

// 出队时需要将队首向后挪一位
// 判断一下是否需要缩绒
@Override
public E dequeue(){

if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size --;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0)
resize(getCapacity() / 2);
return ret;
}

// 看一眼队首数据
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
}

// 改变容量时依然需要多开辟一个空间
private void resize(int newCapacity){

E[] newData = (E[])new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[(i + front) % data.length];

data = newData;
front = 0;
tail = size;
}

// 重写toString方法时
// 需要注意for 循环的起始位置和终止条件
@Override
public String toString(){

StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
res.append("front [");
for(int i = front ; i != tail ; i = (i + 1) % data.length){
res.append(data[i]);
if((i + 1) % data.length != tail)
res.append(", ");
}
res.append("] tail");
return res.toString();
}

public static void main(String[] args){

LoopQueue<Integer> queue = new LoopQueue<>(5);
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);

if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}

循环队列的时间复杂度

  • int getSize(); O(1)
  • boolean isEmpty(); O(1)
  • void enqueue(E e); O(1) 均摊
  • E dequeue(); O(1) 均摊
  • E getFront(); O(1)

数组队列和循环队列的比较

创建一个main函数进行测试

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
import java.util.Random;

public class Main {

// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
private static double testQueue(Queue<Integer> q, int opCount){

long startTime = System.nanoTime();

Random random = new Random();
for(int i = 0 ; i < opCount ; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();

long endTime = System.nanoTime();

return (endTime - startTime) / 1000000000.0;
}

public static void main(String[] args) {

int opCount = 100000;

ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");

LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}

运行结果

1
2
ArrayQueue, time: 58.8541207 s
LoopQueue, time: 0.0163572 s

主要差异:
ArrayQueue出队的时间复杂度是O(n)级别的,再加上外层的循环就是O(n^2)级别的了,所以对于ArrayQueue来说,testQueue方法的时间复杂度是O(n^2)级别的; 而循环队列出队的时间复杂度是O(1)级别的, 再加上外层的循环就是O(n)级别的了,所以对于LoopQueue来说,testQueue方法的时间复杂度是O(n)级别的

完整代码

-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!
0%