什么是栈(Stack)、队列(Queue)?

在很多的应用中,我们需要维护多个对象的集合。这种操作一般来说都比较简单,例如向集合中添加、删除、更新某个元素,检查是否为空以及遍历整个集合。
栈(Stack),或者可以被称为下压栈。你可以将栈想象成为一堆邮件列表,按照通常的规则,每次新来一封邮件,往往都将其放至于最上方;同理,每次处理(查看)一封邮件,都是查看最新的邮件。
队列(Queue),遵守公平原则,你可以将队列想象成为现实中买票排队,永远保证等待时间最长的人最先出队。

栈(Stack)

栈(Stack),或者可以被称为下压栈。你可以将栈想象成为一堆邮件列表,按照通常的规则,每次新来一封邮件,往往都将其放至于最上方;同理,每次处理(查看)一封邮件,都是查看最新的邮件。

栈遵守后进先出(LIFO; Last In, First Out)原则。无论是从栈中添加亦或是删除操作,都只允许从栈顶进行操作。

Stack

如上图,栈内元素的顺序是:0->1->2->3->4
一般我们对于栈的基本操作无非以下几种:

  • 入栈(push)
  • 出栈(pop)
  • 获取栈大小(size)
  • 是否为空(isEmpty)

我们上面说过,无论是从栈中添加亦或是删除操作,都只允许在栈顶操作。
我们分别来看下分步图解入栈(添加)和出栈(删除)操作。

入栈(Push)

Stack-Push

  1. 目前栈内元素的顺序是0->1->2->3
  2. 入栈元素4,位置为栈顶
  3. 入栈后栈内元素为0->1->2->3->4

出栈(Pop)

Stack-Pop

  1. 目前栈内元素的顺序是0->1->2->3->4
  2. 出栈栈顶元素,出栈的元素为4
  3. 出栈后栈内元素为0->1->2->3

接下来我们看下代码层面的数组实现,你可以在我的Github找到此代码。

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
package net.sunzhenyu.miscellaneous.dsa.stack;

import java.util.Iterator;

public class Stack<T> implements IStack<T> {

private static int DEFAULT_INITIAL_CAPACITY = 10;
private Object[] elements;
private int size;

public Stack() {
this.elements = new Object[DEFAULT_INITIAL_CAPACITY];
}

public Stack(int initialCapacity) {
if (initialCapacity > 0) {
this.elements = new Object[initialCapacity];
} else {
this.elements = new Object[DEFAULT_INITIAL_CAPACITY];
}
}

private void ensureCapacity() {
if (this.elements.length >= size) {
expand(this.elements.length << 1);
}
}

@SuppressWarnings("all")
private void expand(int newSize) {
Object[] newArr = new Object[newSize];
for (int i = 0; i < size; i++) {
newArr[i] = this.elements[i];
}
this.elements = newArr;
}

@Override
public void push(T element) {
ensureCapacity();
this.elements[size++] = element;
}

@Override
@SuppressWarnings("unchecked")
public T pop() {
Object oldElement = this.elements[--size];
elements[size] = null;
if (size > 0 && size == this.elements.length >> 4) {
expand(this.elements.length >> 1);
}
return (T) oldElement;
}

@Override
public boolean isEmpty() {
return this.size == 0;
}

@Override
public int size() {
return this.size;
}

@Override
public Iterator<T> iterator() {
return new It();
}

class It implements Iterator<T> {

private int key = size;

@Override
public boolean hasNext() {
return key > 0;
}

@Override
@SuppressWarnings("unchecked")
public T next() {
return (T) elements[--key];
}
}
}

PS:还有一种是使用Node来实现栈,代码在这里

队列(Queue)

队列(Queue),遵守公平原则,你可以将队列想象成为现实中买票排队,永远保证等待时间最长的人最先出队。

队列是一种线性的数据结构,遵守先进先出(FIFI; First In First Out)原则;队列只允许在队首 进行出队操作,且只允许在队尾进行入队操作。

Queue

一般来说,队列的操作只有如下几种:

  • 入队(enqueue)
  • 出队(dequeue)
  • 获取队列大小(size)
  • 队列是否为空(isEmpty)

我们接下来来看下入队和出队操作的分步图解:

入队(EnQueue)

Queue-EnQueue

  1. 目前队列内元素为0->1->2->3
  2. 入队元素4到队尾
  3. 入队后的队列内元素为0->1->2->3->4

出队(DeQueue)

Queue-DeQueue

  1. 目前队列内元素为0->1->2->3->4
  2. 从队首出队一个元素,元素为0
  3. 出队后的队列内元素为1->2->3->4

接下来我们来看下代码层面的数组实现,你也可以在我的Github找到此代码。

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
package net.sunzhenyu.miscellaneous.dsa.queue;

import java.util.Iterator;

public class ArrayQueue<T> implements IQueue<T> {

private Object[] elements;
private int size;
private int head;
private final Integer DEFAULT_CAPACITY = 10;

public ArrayQueue(int initialCapacity) {
if (initialCapacity <= 0) {
elements = new Object[DEFAULT_CAPACITY];
} else {
elements = new Object[initialCapacity];
}
}

@Override
public void enqueue(T element) {
ensureCapacity(this.elements.length << 1);
elements[size++] = element;
}

@Override
@SuppressWarnings("unchecked")
public T dequeue() {
if (size == (elements.length >> 4)) {
expandAndShrink(this.elements.length >> 1);
}
T result = (T) elements[head];
elements[head] = null;
if (++head == elements.length) {
head = 0;
}
return result;
}

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

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

private void ensureCapacity(int newCapacity) {
if (newCapacity <= 0) {
throw new IllegalArgumentException("The new capacity cannot smaller and equal than zero");
}
if (size >= elements.length) {
expandAndShrink(newCapacity);
}
}

@SuppressWarnings("all")
private void expandAndShrink(int newCapacity) {
Object[] newCapacityArray = new Object[newCapacity];
for (int i = 0; i < size; i++) {
newCapacityArray[i] = elements[i];
}
this.elements = newCapacityArray;
}

@Override
public Iterator<T> iterator() {
return new ArrayQueueIterator<>();
}

class ArrayQueueIterator<E> implements Iterator<E> {

private int index = head;

@Override
public boolean hasNext() {
return index < size;
}

@Override
@SuppressWarnings("unchecked")
public E next() {
return (E) elements[index++];
}
}
}