資訊專欄INFORMATION COLUMN
摘要：雙隊(duì)列法復(fù)雜度時(shí)間空間思路和類似，我們也可以用兩個(gè)隊(duì)列來(lái)模擬棧的操作。當(dāng)時(shí)，我們將數(shù)字進(jìn)非空的隊(duì)列就行了。操作和一樣，區(qū)別在于我們拿到最后一個(gè)數(shù)后，還要再把它進(jìn)另一個(gè)隊(duì)列中。
雙隊(duì)列法 復(fù)雜度
時(shí)間 O(N) 空間 O(N)
思路和Implement Queue using Stack類似，我們也可以用兩個(gè)隊(duì)列來(lái)模擬棧的操作。當(dāng)push時(shí)，我們將數(shù)字offer進(jìn)非空的隊(duì)列就行了。當(dāng)pop時(shí)，因?yàn)橐玫氖顷?duì)列最后一個(gè)數(shù)，我們先將它前面的數(shù)offer進(jìn)另一個(gè)隊(duì)列，然后多帶帶拿出最后一個(gè)數(shù)，并且不再offer進(jìn)另一個(gè)隊(duì)列，這樣，另一個(gè)隊(duì)列就少了最后一個(gè)數(shù)，而我們也拿到了最后一個(gè)數(shù)，而本來(lái)的隊(duì)列就變成空了，等待下次的pop操作來(lái)填滿。top操作和pop一樣，區(qū)別在于我們拿到最后一個(gè)數(shù)后，還要再把它offer進(jìn)另一個(gè)隊(duì)列中。
代碼class MyStack {
Queue queue1;
Queue queue2;
int size;
public MyStack(){
this.queue1 = new LinkedList();
this.queue2 = new LinkedList();
this.size = 0;
}
// Push element x onto stack.
public void push(int x) {
if(queue1.isEmpty()){
queue2.offer(x);
} else {
queue1.offer(x);
}
size++;
}
// Removes the element on top of the stack.
public int pop() {
if(size == 0){
return -1;
}
int res = 0;
// 將前面的數(shù)都o(jì)ffer進(jìn)另一個(gè)隊(duì)列，然后拿出最后一個(gè)數(shù)
if(queue1.isEmpty()){
for(int i = 0; i < size - 1; i++){
queue1.offer(queue2.poll());
}
res = queue2.poll();
} else {
for(int i = 0; i < size - 1; i++){
queue2.offer(queue1.poll());
}
res = queue1.poll();
}
size--;
return res;
}
// Get the top element.
public int top() {
if(size == 0){
return -1;
}
// 先執(zhí)行pop
int top = pop();
// 然后將pop出來(lái)的數(shù)再塞回隊(duì)列就行了
if(queue1.isEmpty()){
queue2.offer(top);
} else {
queue1.offer(top);
}
// 注意size也要加1
size++;
return top;
}
// Return whether the stack is empty.
public boolean empty() {
return size == 0;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64618.html
摘要：下面是入棧時(shí)代碼獲得隊(duì)列長(zhǎng)度反轉(zhuǎn)次數(shù)為隊(duì)列長(zhǎng)度減一反轉(zhuǎn)語(yǔ)言沒有棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組或雙端隊(duì)列實(shí)現(xiàn)。這類編程語(yǔ)言就壓根不需要用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用隊(duì)列實(shí)現(xiàn)棧的下列操作： push(x) -- 元素 x 入棧 pop() -- 移除棧頂元素 top() -- 獲取棧頂元素 empty() -- 返回棧是否為空 Impl...
摘要：題目要求使用隊(duì)列來(lái)模擬實(shí)現(xiàn)一個(gè)棧。棧是指先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，而隊(duì)列則是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。隊(duì)列的包括在隊(duì)列尾插入數(shù)據(jù)，輸出隊(duì)列頭的數(shù)據(jù)，查看隊(duì)列的長(zhǎng)度，隊(duì)列是否為空。 題目要求 Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of que...
摘要：題目使用棧實(shí)現(xiàn)隊(duì)列的下列操作將一個(gè)元素放入隊(duì)列的尾部。用棧實(shí)現(xiàn)隊(duì)列，可以用兩個(gè)棧完成題解。入隊(duì)列時(shí)用存入節(jié)點(diǎn)，出隊(duì)列時(shí)內(nèi)節(jié)點(diǎn)順序出棧壓入中。這類編程語(yǔ)言就壓根不需要用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用棧實(shí)現(xiàn)隊(duì)列的下列操作： push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。 pop() -- 從隊(duì)列首部移除元素。 peek() -- 返回隊(duì)...
摘要：注意的方法是和，實(shí)際上我們應(yīng)該實(shí)現(xiàn)的是和或者和，的實(shí)現(xiàn)和是一樣的，但將改為時(shí)，我們要先把到的元素保存，然后再?gòu)棾鲚敵鰲＃缓蠓祷剡@個(gè)保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...
摘要：題目要求通過隊(duì)列實(shí)現(xiàn)一個(gè)棧的功能。棧的為壓入棧頂，出棧，棧頂元素，棧是否為空。重復(fù)上述的操作。但是當(dāng)需要彈出元素時(shí)，則從桶彈出。這樣，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保證位輸入順序。極大的減少了不必要的入棧出棧。 題目要求 Implement the following operations of a queue using stacks. push(x) ...
閱讀 797·2023-04-26 03:04
閱讀 2872·2021-11-15 18:10
閱讀 1198·2021-09-03 10:28
閱讀 1137·2019-08-30 15:53
閱讀 894·2019-08-30 12:45
閱讀 1962·2019-08-30 11:03
閱讀 2870·2019-08-29 14:01
閱讀 2934·2019-08-28 18:24
