栈与队列最基本的特征:
栈:先进后出
队列:先进先出
用栈实现队列:
题解:
栈是先进后出的数据结构,队列是先进先出,题目中已经说明,需要两个栈来实现队列,题目中让实现的方法是push、pop、peek、empty,
我们首先定义两个栈stack_in, stack_out,一个负责进栈,一个负责出栈
push:将数据放入,我们可以直接将数据放入到进栈stack_in中
empty: 若进栈和空栈都为空,则说明模拟的队列为空
pop:pop之前我们先要判断模拟的队列是否为空,若为空,直接返回None,因为是出队列,我们要先判断出栈stack_out是否为空,若为空,则需要将进栈中的数据都要导入到出栈中,记住,是将进栈中所有的数据,然后出栈出
peek:此方法其实是模拟返回队列的头数值,也就是出栈的栈顶元素,记住此方法不会改变数据的结构,只是返回数据
代码:
用队列实现栈
题解:
队列是每次队头出列,队尾入列,使用双端队列
push:数据进入到队尾
pop:pop之前先要判断模拟栈是否为空,若不空,则直接返回队列的末尾数据
top:返回的是栈顶的元素,也是队列尾部的元素
empty:判断对队列是空即可
双队列: