kotlin:225. 用队列实现栈 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。 实现 MyStack 类: void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。 注意: 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
时间: 2024-03-23 20:37:29 浏览: 18
以下是使用两个队列实现栈的 Kotlin 代码:
```
import java.util.*
class MyStack() {
private val queue1 = LinkedList<Int>()
private val queue2 = LinkedList<Int>()
private var topElement: Int? = null
/** Push element x onto stack. */
fun push(x: Int) {
queue2.offer(x)
topElement = x
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll())
}
val temp = queue1
queue1 = queue2
queue2 = temp
}
/** Removes the element on top of the stack and returns that element. */
fun pop(): Int {
val popped = queue1.poll()
if (queue1.isEmpty()) {
topElement = null
} else {
topElement = queue1.peek()
}
return popped
}
/** Get the top element. */
fun top(): Int {
return topElement!!
}
/** Returns whether the stack is empty. */
fun empty(): Boolean {
return queue1.isEmpty()
}
}
```
解释一下代码:
我们使用两个队列 `queue1` 和 `queue2` 来模拟栈。`queue1` 存储栈中的元素,而 `queue2` 用来在 `push` 操作时暂存元素。
在 `push` 操作中,我们首先把元素 `x` 加入到 `queue2` 中,然后将 `queue1` 中的所有元素依次加入到 `queue2` 中。这样做的目的是为了让 `queue2` 中的元素按照栈的顺序排列,即最后加入的元素在队首,而最先加入的元素在队尾。然后我们将 `queue2` 和 `queue1` 交换,这样 `queue1` 中的元素就按照栈的顺序排列了。
在 `pop` 操作中,我们直接从 `queue1` 中弹出队首元素即可。如果 `queue1` 变为空队列,则将 `topElement` 置为 `null`。
在 `top` 操作中,我们返回 `topElement`,它记录了栈顶元素的值。
在 `empty` 操作中,我们判断 `queue1` 是否为空即可。