栈和队列常用算法总结

如何用栈来实现队列,如何用队列来实现栈,如何用数组来实现栈和队列。

如何用栈实现队列

思路:用栈实现队列结构,准备两个栈,一个push栈,一个pop栈,加数据入push栈,取数据从pop栈中拿。总体思路是进push的数据倒入pop栈中,两次逆序等于顺序。倒的两个限制:(1) 如果push开始往pop中倒数据,一次要倒完 (2) pop栈为空才允许倒数据。只要满足以上两个限制,倒数据的行为可以发生在任何时刻

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
public static class twoStacksToQueue {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;

private void transfer() {
if (!popStack.empty())
return;
while (!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}

public twoStacksToQueue() {
pushStack = new Stack<>();
popStack = new Stack<>();
}

public boolean offer(int num) {
pushStack.push(num);
transfer();
return true;
}

public int poll() {
if (popStack.empty() && pushStack.empty()) {
throw new RuntimeException("Queue is empty");
}
transfer();
return popStack.pop();
}

public int peek() {
if (popStack.empty() && pushStack.empty()) {
throw new RuntimeException("Queue is empty");
}
transfer();
return popStack.peek();
}
}

如何用队列实现栈

思路:准备两个队列,一个data队列,一个help队列,压数的话压入data队列,弹出数将data队列中的数除了最后一个数之外其他的压入help队列,将最后一个数返回用户,再将data和help引用互换

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
public static class TwoQueuesToStack {
private Queue<Integer> data;
private Queue<Integer> help;

public TwoQueuesToStack() {
data = new LinkedList<>();
help = new LinkedList<>();
}

public int push(int num) {
data.add(num);
return num;
}

public int pop() {
if (data.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
while (data.size() > 1) {
help.add(data.poll());
}
int res = data.poll();
swap();
return res;
}

public int peek() {
if (data.isEmpty()) {
throw new RuntimeException("Stack is empty");
}
while (data.size() > 1) {
help.add(data.poll());
}
int res = data.poll();
// 注意:最后一个数要加回help中
help.add(res);
swap();
return res;
}

private void swap() {
Queue<Integer> tmp = data;
data = help;
help = tmp;
}
}

如何用数组实现栈

思路:准备一个栈顶指针index,数组的大小设置为栈的大小为initSize。当要加一个数,index的含义为如果新来一个数,我把新来的数放在index位置。当用户让我弹出一个数,我弹出的数是index的前一个数(前一个数也就是位置处于index下面一个数,假设数组是竖直排列的,最底下是nums[0])。index == size时前一个数下标为size - 1,栈满,如还要压入则给用户报错。index == 0时前一个数下标为-1。栈空,如还要弹出给用户报错。

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
public static class ArrayStack {
private int[] array;
private int index;
public int size; // 栈的大小,也是数组的大小

public ArrayStack(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
this.size = initSize;
array = new int[initSize];
index = 0;
}

public int push(int num) {
if (index < size) {
array[index ++] = num;
return num;
} else {
throw new ArrayIndexOutOfBoundsException("The stack is full!");
}
}

public int pop() {
if (index > 0) {
return array[-- index];
} else {
throw new ArrayIndexOutOfBoundsException("The stack is empty!");
}
}

public int peek() {
if (index > 0) {
return array[index - 1];
} else {
throw new ArrayIndexOutOfBoundsException("The stack is empty!");
}
}
}

如何用数组实现队列

思路:准备一个start变量一个end变量,一开始都指向0位置,再准备一个curSize变量约束startend的行为,curSize表示队列已有元素的个数。startend无直接关系(解耦),start或者end都是每次和curSize比较是否越界。end代表当要加一个数,我把新来的数放在end位置,start代表当用户让我取出一个数,我把start位置的数取出给用户,类似于加数队尾排队打饭,取数队头打完饭走人。end一旦到底就返回开头,start一直在追end,curSize == array.length时队列为满,如还要加数给用户报错,curSize == 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static class ArrayQueue {
private int[] array;
private int curSize;
private int start, end;
public ArrayQueue(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
array = new int[initSize];
curSize = 0;
start = 0;
end = 0;
}

public boolean add(int num) {
if (curSize == array.length) {
throw new ArrayIndexOutOfBoundsException("The Queue is full");
}
curSize ++;
array[end] = num;
// end的下一个位置
end = end == array.length - 1 ? 0 : end + 1;
return true;
}

public int poll() {
if (curSize == 0) {
throw new ArrayIndexOutOfBoundsException("The Queue is empty");
}
curSize --;
int tmp = start;
// start的下一个位置
start = start == array.length - 1 ? 0 : start + 1;
return array[tmp];
}

public int peek() {
if (curSize == 0) {
throw new ArrayIndexOutOfBoundsException("The Queue is empty");
}
return array[start];
}
}
谢谢小天使请我吃糖果
0%