栈与队列

栈和队列可以说是最基本的数据结构了,它们都是在两端进行操作,其中栈在栈顶进行操作,被称为先进后出(LIFO),队列在队头和队尾进行操作,被称为先进先出(FIFO)

直接来看看API吧:

API

public class Stack
Stack() 构造一个空栈
void push(Item item) 入栈
Item pop() 出栈
boolean isEmpty() 判空
int size() 大小

链栈

顾名思义,基于链表实现的栈

其中的一个结点:

1
2
3
4
private class Node {
Item item;
Node next;
}

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LinkedStack<Item> {
private Node first = null;
private class Node {
Item item;
Node next;
}
public boolean isEmpty() {
return first == null;
}
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
public Item pop() {
Item item = first.item;
first = first.next;
return item;
}
}

顺序栈

基于数组(顺序表)实现的栈是顺序栈

简单实现一个定长的栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FixedCapacityStack<Item> {
private Item[] s;
private int N = 0;
public FixedCapacityStack(int capacity) {
s = (Item[]) new Object[capacity];
}

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

public void push(Item item) {
s[N++] = item;
}

public Item pop() {
return s[--N];
}
}

但是定长的栈需要获取capacity,而这又需要客户端提供,然而大部分时间客户端是不知道所需的容量的。

于是就有了动态长度的栈:

ResizingArrayStack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class ResizingArrayStack<Item> {
private Item[] s;
private int N = 0;
public ResizingArrayStack() {
s = (Item[]) new Object[1];
}
public void push(Item item) {
if (N == s.length) resize(2 * s.length);
s[N++] = item;
}
public Item pop() {
return s[--N];
s[N] = null;
if (N > 0 && N == s.length/4) resize(s.length/2);
return item;
}
private void resize(int capacity) {
Item[] copy = (Item[]) new Object[capacity];
for (int i = 0; i < N; i++)
copy[i] = s[i];
s = copy;
}
}

此时poppush操作的最坏时间复杂度也是O(N)O(N)

迭代器

我们可以为栈写一个迭代器:

需要实现Iterator<>接口的hasNextnext方法,栈类也需要实现Iterable<>接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public Item next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Item item = current.item;
current = current.next;
return item;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public Iterator<Item> iterator() {
return new ArrayIterator();
}
private class ArrayIterator implements Iterator<Item> {
private int i = N;
public boolean hasNext() {
return i > 0;
}
public Item next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return s[--N];
}
}

队列

队列是一种基于先进先出(FIFO)策略的集合类型

API

public class Queue
Queue() 构造一个空队列
void enqueue(Item item) 入队
Item dequeue() 出队
boolean isEmpty() 判空
int size() 大小

链队

直接贴代码,没什么好说的

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
public class LinkedQueue<Item> implements Iterable<Item>{
private Node first, last;
private class Node {
Item item;
Node next;
}

public boolean isEmpty() {
return first == null;
}

public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
}

public Item dequeue() {
Item item = first.item;
first = first.next;
if (isEmpty()) last = null;
return item;
}

public Iterator<Item> iterator() {
return new ListIterator();
}

private class ListIterator implements Iterator<Item> {
private Node current = first;

public boolean hasNext() {
return current != null;
}

public Item next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Item item = current.item;
current = current.next;
return item;
}
}
}

顺序队列

顺序队列是基于顺序表的队列,其实一般都是循环队列,就是栈顶、栈底两个指针,front = (front + 1) % MaxSizerear = (rear + 1) % MaxSize

  • 队空条件:rear == front
  • 队满条件:(rear + 1) % MaxSize == front
  • 元素进队:rear = (rear + 1) % MaxSize
  • 元素出队:front = (front + 1) % MaxSize
1
2
3
4
5
6
7
8
9
10
11
12
public void push(Item item)	{ 
if ((rear + 1) % MaxSize == front) return;
rear = (rear + 1) % MaxSize;
s[rear] = item;
}

public Item pop() {
if (front == rear) throw new NoSuchElementException();
front = (front + 1) % MaxSize;
return s[front];
}


栈与队列
https://ivansnow02.github.io/posts/16574/
作者
Ivan Snow
发布于
2023年5月30日
许可协议