正如標(biāo)題所述败晴，你需要使用兩個(gè)棧來實(shí)現(xiàn)隊(duì)列的一些操作覆致。
隊(duì)列應(yīng)支持push(element)利耍，pop() 和 top()，其中pop是彈出隊(duì)列中的第一個(gè)(最前面的)元素出皇。
pop和top方法都應(yīng)該返回第一個(gè)元素的值羞芍。
思路：這里有一個(gè)老哥的討論感覺很有趣也很有用
我開始是考慮到了將一個(gè)用來導(dǎo)入，一個(gè)用來緩存郊艘，但是效率太低荷科。不過，看到他的討論的最后一個(gè)方案確實(shí)很不錯(cuò)纱注，利用隊(duì)列先進(jìn)先出的性質(zhì)畏浆，具體的就不轉(zhuǎn)載了，鏈接里很詳細(xì)狞贱。
Python3
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, element):
# write your code here
self.stack1.append(element)
def top(self):
# write your code here
# return the top element
if self.stack2:
return self.stack2[-1]
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def pop(self):
# write your code here
# pop and return the top element
if self.stack2:
return self.stack2.pop()
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
在寫這段代碼的過程中犯了一個(gè)小錯(cuò)誤導(dǎo)致memory limitation exceeding刻获。
stack1.pop stack1.pop()
Java
public class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
// do initialization if necessary
stack1 = new Stack<Integer>();
stack2 = new Stack<Integer>();
}
public void push(int element) {
// write your code here
stack1.push(element);
}
public int pop() {
// write your code here
if (!stack2.empty())
{
return stack2.pop();
}
while(!stack1.empty())
{
int x = stack1.pop();
stack2.push(x);
}
return stack2.pop();
}
public int top() {
// write your code here
if (!stack2.empty())
{
return stack2.peek();
}
while(!stack1.empty())
{
int x = stack1.pop();
stack2.push(x);
}
return stack2.peek();
}
}
在編寫中遇到一些問題：
- int 與 integer的相等問題
經(jīng)過查閱，int 是一個(gè)數(shù)據(jù)類型瞎嬉，初值0蝎毡； integer是一個(gè)int的包裝類，初值null氧枣。但是在對(duì)比時(shí)沐兵，integer會(huì)拆箱和int對(duì)比，所以int == integer便监，只要值相等扎谎，就會(huì)相等。
除此之外烧董，兩個(gè)新建的integer是不相等的（比較的是地址）毁靶。非新建的integer在-128-127之間，只要值相等就==（引用）逊移，但是如果不在這之間预吆，就算值等他們也不==，因?yàn)樗麄儠?huì)單獨(dú)建立對(duì)象胳泉，互不引用啡浊。
More - 調(diào)用所有的函數(shù)還是建立新的對(duì)象觅够，都會(huì)有()。
