| comments | difficulty | edit_url |
|---|---|---|
true |
简单 |
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1]
示例 2：
输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000最多会对 appendTail、deleteHead 进行 10000 次调用
我们可以使用两个栈来实现队列，其中一个栈 stk1 用来存储输入的元素，另一个栈 stk2 用来输出元素。
当调用 appendTail() 方法时，我们将元素压入 stk1 中。
当调用 deleteHead() 方法时，如果此时栈 stk2 为空，我们将栈 stk1 中的元素逐个弹出并压入栈 stk2 中，然后弹出栈 stk2 的栈顶元素即可。如果此时栈 stk2 不为空，我们直接弹出栈 stk2 的栈顶元素即可。如果两个栈都为空，说明队列中没有元素，返回 -1。
时间复杂度上，对于 appendTail() 方法，时间复杂度为 deleteHead() 方法，时间复杂度为
class CQueue:
def __init__(self):
self.stk1 = []
self.stk2 = []
def appendTail(self, value: int) -> None:
self.stk1.append(value)
def deleteHead(self) -> int:
if not self.stk2:
while self.stk1:
self.stk2.append(self.stk1.pop())
return -1 if not self.stk2 else self.stk2.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()class CQueue {
private Deque<Integer> stk1 = new ArrayDeque<>();
private Deque<Integer> stk2 = new ArrayDeque<>();
public CQueue() {
}
public void appendTail(int value) {
stk1.push(value);
}
public int deleteHead() {
if (stk2.isEmpty()) {
while (!stk1.isEmpty()) {
stk2.push(stk1.pop());
}
}
return stk2.isEmpty() ? -1 : stk2.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/class CQueue {
public:
CQueue() {
}
void appendTail(int value) {
stk1.push(value);
}
int deleteHead() {
if (stk2.empty()) {
while (!stk1.empty()) {
stk2.push(stk1.top());
stk1.pop();
}
}
if (stk2.empty()) {
return -1;
}
int ans = stk2.top();
stk2.pop();
return ans;
}
private:
stack<int> stk1, stk2;
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/type CQueue struct {
stk1, stk2 []int
}
func Constructor() CQueue {
return CQueue{[]int{}, []int{}}
}
func (this *CQueue) AppendTail(value int) {
this.stk1 = append(this.stk1, value)
}
func (this *CQueue) DeleteHead() int {
if len(this.stk2) == 0 {
for len(this.stk1) > 0 {
this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
this.stk1 = this.stk1[:len(this.stk1)-1]
}
}
if len(this.stk2) == 0 {
return -1
}
ans := this.stk2[len(this.stk2)-1]
this.stk2 = this.stk2[:len(this.stk2)-1]
return ans
}
/**
* Your CQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.AppendTail(value);
* param_2 := obj.DeleteHead();
*/class CQueue {
private stk1: number[];
private stk2: number[];
constructor() {
this.stk1 = [];
this.stk2 = [];
}
appendTail(value: number): void {
this.stk1.push(value);
}
deleteHead(): number {
if (this.stk2.length == 0) {
while (this.stk1.length) {
this.stk2.push(this.stk1.pop());
}
}
return this.stk2.length == 0 ? -1 : this.stk2.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/struct CQueue {
s1: Vec<i32>,
s2: Vec<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl CQueue {
fn new() -> Self {
CQueue {
s1: Vec::new(),
s2: Vec::new(),
}
}
fn append_tail(&mut self, value: i32) {
self.s1.push(value);
}
fn delete_head(&mut self) -> i32 {
match self.s2.pop() {
Some(value) => value,
None => {
while !self.s1.is_empty() {
self.s2.push(self.s1.pop().unwrap());
}
self.s2.pop().unwrap_or(-1)
}
}
}
}var CQueue = function () {
this.stk1 = [];
this.stk2 = [];
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function (value) {
this.stk1.push(value);
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function () {
if (!this.stk2.length) {
while (this.stk1.length) {
this.stk2.push(this.stk1.pop());
}
}
return this.stk2.length ? this.stk2.pop() : -1;
};
/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/public class CQueue {
private Stack<int> stk1 = new Stack<int>();
private Stack<int> stk2 = new Stack<int>();
public CQueue() {
}
public void AppendTail(int value) {
stk1.Push(value);
}
public int DeleteHead() {
if (stk2.Count == 0) {
while (stk1.Count != 0) {
stk2.Push(stk1.Pop());
}
}
return stk2.Count == 0 ? -1 : stk2.Pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.AppendTail(value);
* int param_2 = obj.DeleteHead();
*/class CQueue {
private var stk1: [Int] = []
private var stk2: [Int] = []
init() {
}
func appendTail(_ value: Int) {
stk1.append(value)
}
func deleteHead() -> Int {
if stk2.isEmpty {
while !stk1.isEmpty {
stk2.append(stk1.removeLast())
}
}
return stk2.isEmpty ? -1 : stk2.removeLast()
}
}
/**
* Your CQueue object will be instantiated and called as such:
* let obj = CQueue();
* obj.appendTail(value);
* let param_2 = obj.DeleteHead();
*/