趣解数据结构与算法(二)——栈和队列

0x00.栈

概念

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表

结构规则即为:先进后出

常用方法

  1. push:压入数据
  2. peek:访问栈顶元素
  3. pop:弹出数据
  4. empty:栈是否为空

这里的常用方法不局限于某编程语言,不管什么语言、框架,数据结构中的栈结构的常用操作就是这些

上手操作

我们全套课程将会使用java来操作

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 MyStack {
private Stack<Integer> stack;

public MyStack() {
super();
}
public MyStack(Stack<Integer> stack) {
this.stack=stack;
}
public static void main(String[] args) {
MyStack myStack=new MyStack(new Stack<>());
myStack.stack.push(1); //栈底
myStack.stack.push(4);
myStack.stack.push(6);
myStack.stack.push(7); //栈顶
System.out.println(myStack.stack.toString());
//窥探
System.out.println(myStack.stack.peek());
//弹出
System.out.println(myStack.stack.pop());
System.out.println(myStack.stack);
}
}

控制台:
[1, 4, 6, 7]
7
7
[1, 4, 6]

实现结构

我们来实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。

要求:

  1. pop、push、getMin操作的时间复杂度都是O(1)
  2. 设计的栈类型可以使用现成的栈结构

解题思路:
设计上我们使用两个栈,一个栈用来保存当前栈中的元素,其功能和一个正常的栈没有区别,这个栈记为stackData;另一个栈用来保存每一步的最小值,即当push更小值,该栈也push更小值;当push非更小值,该栈重新push一个前一个最小值,这个栈记为stackMin。两个栈的元素个数要始终保持同步。

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 class MyStack {
private Stack<Integer> stackData;
private Stack<Integer> stackMin;

public MyStack(Stack<Integer> stackDate,Stack<Integer> stackMin) {
this.stackMin=stackMin;
this.stackData=stackDate;
}
public void push(int newNum) {
if(this.stackMin.empty()) {
this.stackMin.push(newNum);
}else if(newNum<this.getMin()) {
this.stackMin.push(newNum);
}else {
int newMin=this.stackMin.peek().intValue();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop() {
if(this.stackData.empty()) {
throw new RuntimeException("数据栈为空");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getMin() {
if(this.stackMin.empty()) {
throw new RuntimeException("最小栈为空");
}
return this.stackMin.peek();
}

public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
MyStack myStack=new MyStack(new Stack<>(), new Stack<>());
System.out.println("请输入您要存入的数字:");
for(int i=0;i<6;i++) {
int newNum=scanner.nextInt();
myStack.push(newNum);
}
System.out.println("内部stackData"+myStack.stackData);
System.out.println("内部stackMin"+myStack.stackMin);
System.out.println("最小的元素: "+myStack.getMin());
}
}

控制台:
请输入您要存入的数字:
4
5
7
2
5
0
内部stackData[4, 5, 7, 2, 5, 0]
内部stackMin[4, 4, 4, 2, 2, 0]
最小的元素: 0


0x01.队列

概念

队列的概念:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。

实现方式有两种:顺序存储(列表)、链式存储(链表)

结构规则即为:先进先出

假上溢问题:
基于顺序存储的队列需要考虑一下假上溢问题,什么是假上溢呢?
资源路径有问题

常用方法

  1. add:添加数据
  2. peek:访问队列顶元素
  3. pop:弹出数据
  4. empty:栈是否为空
  5. move:搬移队列

实现顺序队列

我们来根据顺序存储来实现一个队列:

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
public class MyQueue {
private int[] queue; //队列
private int head; //头部元素下标
private int tail; //尾部元素下标的下一个位置

public MyQueue(int[] queue) {
this.queue=queue;
this.head=0;
this.tail=0;
}
public boolean add(int num) {
if(tail==queue.length&&head==0) { //队列真的满了
throw new RuntimeException("队列已满");
}
if(tail==queue.length&&head!=0) { //假溢出,需要搬移
queue=move();
}
queue[tail]=num;
tail++;
return true;
}
public int pop() {
int num=queue[head];
queue[head]=0;
head++;
return num;
}
public boolean empty() {
return tail==head&&head==0&&queue[0]==0?true:false;
}
private int[] move() {
int[] ints=new int[queue.length];
int count=head;
for(int i=0;head<queue.length;i++,head++) {
ints[i]=queue[head];
}
tail=queue.length-count;
head=0;
return ints;
}

/* (非 Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "MyQueue{"
+ "queue="+Arrays.toString(queue)
+ ",head="+head
+ ",tail="+tail
+ "}";
}
public static void main(String[] args) {
MyQueue mq=new MyQueue(new int[5]);
System.out.println(mq);

mq.add(3);
mq.add(4);
mq.add(2);
mq.add(5);
System.out.println(mq);

mq.pop();
mq.pop();
System.out.println(mq);

mq.add(1);
mq.add(2);
mq.add(6);
System.out.println(mq);
}
}

控制台:
MyQueue{queue=[0, 0, 0, 0, 0],head=0,tail=0}
MyQueue{queue=[3, 4, 2, 5, 0],head=0,tail=4}
MyQueue{queue=[0, 0, 2, 5, 0],head=2,tail=4}
MyQueue{queue=[2, 5, 1, 2, 6],head=0,tail=5}

这段代码中,我们使用了move方法来实现数据的搬移从而避免假上溢的问题,实际上,我们还可以使用循环队列的方式智能避免假上溢问题

实现循环队列

循环队列的精髓在于将数组假想成一个环,通过取余的方法充分填充,不得不说前辈们的智慧真是无穷无尽。

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
public class MyQueue {
private int[] queue; //队列
private int head; //头部元素下标
private int tail; //尾部元素下标的下一个位置

private final int maxSize;

public MyQueue(int maxSize) {
this.maxSize=maxSize;
this.queue=new int[maxSize];
this.head=0;
this.tail=0;
}
public void add(int num) {
if(isFull()) { //队列满了
throw new RuntimeException("队列已满");
}
queue[tail]=num;
tail++;
tail%=maxSize;
}
public int pop() {
if(empty()) {
throw new RuntimeException("队列已空");
}
int temp=queue[head];
queue[head]=0;
head++;
return temp;
}
public int peek() {
if(empty()) {
throw new RuntimeException("队列已空");
}
return queue[head];
}
public boolean empty() {
return tail==head;
}
public boolean isFull() {
return (tail+1)%maxSize==head;
}
/* (非 Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "MyQueue{"
+ "queue="+Arrays.toString(queue)
+ ",head="+head
+ ",tail="+tail
+ "}";
}
public static void main(String[] args) {
MyQueue mq=new MyQueue(6);
System.out.println(mq);

mq.add(3);
mq.add(4);
mq.add(2);
mq.add(5);
System.out.println(mq);

mq.pop();
mq.pop();
System.out.println(mq);

mq.add(1);
mq.add(2);
mq.add(6);
System.out.println(mq);
}
}

控制台:
MyQueue{queue=[0, 0, 0, 0, 0, 0],head=0,tail=0}
MyQueue{queue=[3, 4, 2, 5, 0, 0],head=0,tail=4}
MyQueue{queue=[0, 0, 2, 5, 0, 0],head=2,tail=4}
MyQueue{queue=[6, 0, 2, 5, 1, 2],head=2,tail=1}

猫狗队列

运用队列的功能,在指定用户的类的基础上,实现以下功能:

  1. 用户可以调用add方法将cat类或dog类的实例放入队列中
  2. 用户可以调用pollAll方法,将队列中所有的实例按照进队列的先后顺序弹出
  3. 用户可以调用pollDog方法,将队列中dog类的实例按照“先进先出”顺序弹出
  4. 用户可以调用pollCat方法,将队列中cog类的实例按照“先进先出”顺序弹出
  5. 用户可以调用isEmpty的方法,检查队列中是否还有dog或cat的实例
  6. 用户可以调用isDogEmpty方法,检查队列中是否有dog类的实例
  7. 用户可以调用isCatEmpty方法,检查队列中是否有cat类的实例

这个猫狗队列的问题看似简单,实则暗藏杀机,因为如果使用一个pet队列,或者cat、dog、pet三个队列,都不能不出错地实现上面的全部要求,更不能擅自更改用户内部的cat/dog类。

解决思路:新定义一个类,将原有的用户的类作为成员变量之一,再添加一个count类作为时间戳(暂可理解为一种标记)进行排序,根据时间戳来poll;
如下图所示,弹出cat时就弹出cat,弹出dog时就弹出dog,全部弹出时就比较时间戳count进行弹出。

资源路径有问题

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Pet {
private String type;
private String name;
public Pet(String type,String name) {
this.type=type;
this.name=name;
}
public Pet() { super(); }
public String getName() {
return name;
}
public String getType() { return this.type;}
}
1
2
3
4
5
public class Cat extends Pet {
public Cat(String name) {
super("cat",name);
}
}
1
2
3
4
5
public class Dog extends Pet {
public Dog(String name) {
super("dog",name);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class PetEnter {  //对pet类进行装饰
private Pet pet;
private long count; //时间戳

public PetEnter(Pet pet,long count) {
this.pet=pet;
this.count=count;
}
public Pet getPet() {
return pet;
}
public long getCount() {
return count;
}
public String PetEnter() {
return this.PetEnter();
}
}
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
public class CatDogQueue {
private Queue<PetEnter> dogQ;
private Queue<PetEnter> catQ;
private long count;

public CatDogQueue() {
this.dogQ=new LinkedList<PetEnter>();
this.catQ=new LinkedList<PetEnter>();
this.count=0;
}
public void add(Pet pet) {
if(pet.getType().equals("dog")) {
this.dogQ.add(new PetEnter(pet, count++));
}else if(pet.getType().equals("cat")) {
this.catQ.add(new PetEnter(pet, count++));
}else {
throw new RuntimeException("err,not cat or dog");
}
}
public Pet pollAll() { //抛出所有
if(!dogQ.isEmpty()&&!catQ.isEmpty()) {
if(dogQ.peek().getCount()<catQ.peek().getCount()) {
return dogQ.poll().getPet();
}else {
return catQ.poll().getPet();
}
}else if(!dogQ.isEmpty()) {
return dogQ.poll().getPet();
}else if(!catQ.isEmpty()) {
return catQ.poll().getPet();
}else {
throw new RuntimeException("队列空");
}
}
public Dog pollDog() {
if(!isDogQueueEmpty()) {
return (Dog)this.dogQ.poll().getPet();
}else {
throw new RuntimeException("狗队列空");
}
}
public Cat pollCat() {
if(!isCatQueueEmpty()) {
return (Cat)this.catQ.poll().getPet();
}else {
throw new RuntimeException("猫队列空");
}
}
public boolean isEmpty() {
return dogQ.isEmpty()&&catQ.isEmpty();
}
public boolean isDogQueueEmpty() {
return dogQ.isEmpty();
}
public boolean isCatQueueEmpty() {
return catQ.isEmpty();
}


public static void main(String[] args) {
CatDogQueue cdq=new CatDogQueue();
cdq.add(new Dog("花花"));
cdq.add(new Dog("嘟嘟"));
cdq.add(new Cat("仔仔"));
while(!cdq.isEmpty()) {
System.out.println(cdq.pollAll().getName());
}

cdq.add(new Dog("花花"));
cdq.add(new Dog("嘟嘟"));
cdq.add(new Cat("仔仔"));
while(!cdq.isDogQueueEmpty()) {
System.out.println(cdq.pollDog().getName());
}

cdq.add(new Dog("花花"));
cdq.add(new Dog("嘟嘟"));
cdq.add(new Cat("仔仔"));
while(!cdq.isCatQueueEmpty()) {
System.out.println(cdq.pollCat().getName());
}
}
}

控制台:
花花
嘟嘟
仔仔
花花
嘟嘟
仔仔
仔仔

为什么会输出两个“仔仔”,因为全部弹出Dog队列的时候,Cat队列的内容不会被弹出,所以“仔仔”会有两个

两个栈实现队列问题

栈的特点是先进后出,而队列的特点是先进先出,我们的新问题需求就是:利用两个栈来实现一个队列。

欢迎请我喝奶茶(*゜ェ゜*)
---这篇文章到头了---感谢您的阅读-------------