資訊專欄INFORMATION COLUMN
摘要：題目要求使用隊(duì)列來模擬實(shí)現(xiàn)一個棧。棧是指先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，而隊(duì)列則是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。隊(duì)列的包括在隊(duì)列尾插入數(shù)據(jù)，輸出隊(duì)列頭的數(shù)據(jù)，查看隊(duì)列的長度，隊(duì)列是否為空。
題目要求
Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. Notes: You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
使用隊(duì)列來模擬實(shí)現(xiàn)一個棧。
棧是指先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，而隊(duì)列則是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。
假設(shè)我們分別往棧和隊(duì)列中順序輸入[1,2,3]，那么棧的輸出是[3,2,1]，而隊(duì)列的輸出的[1,2,3]。
隊(duì)列的API包括在隊(duì)列尾插入數(shù)據(jù)，輸出隊(duì)列頭的數(shù)據(jù)，查看隊(duì)列的長度，隊(duì)列是否為空。
那么我們現(xiàn)在看一下如何通過隊(duì)列來實(shí)現(xiàn)棧的操作。
方法一：兩個隊(duì)列當(dāng)插入數(shù)據(jù)中時，固定往非空的那個隊(duì)列插入數(shù)據(jù)。（如果兩個隊(duì)列的值都為空，那么就任選一個隊(duì)列插入即可）。當(dāng)想要獲得棧頂數(shù)據(jù)或者執(zhí)行棧的pop操作時，那么就將隊(duì)列中的值逐個輸出到另一個隊(duì)列中，并輸出原隊(duì)列中最后一個元素的值。
下面用圖形展示一下：
1.向數(shù)據(jù)結(jié)構(gòu)中插入1，因?yàn)榇藭r兩個隊(duì)列總都為空，因此任選一個隊(duì)列插入
2.向數(shù)據(jù)結(jié)構(gòu)中插入2和3，因?yàn)榇藭r隊(duì)列一非空，因此插入隊(duì)列一
3.模擬pop操作，這是需要將隊(duì)列一的內(nèi)容輸出再輸入到隊(duì)列二中并丟棄隊(duì)列1中最后一個元素，即為3
4.模擬top操作，類似于pop，將非空隊(duì)列的內(nèi)容逐個轉(zhuǎn)移至空隊(duì)列，并記錄最后的一個元素返回，即為2
代碼如下：
public class Stack {
LinkedList queue1 = new LinkedList();
LinkedList queue2 = new LinkedList();
/** Push element x onto stack. */
public void push(int x) {
if(queue1.isEmpty()){
queue2.offer(x);
}else{
queue1.offer(x);
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
int top = 0;
if(queue1.isEmpty()){
while(queue2.size() > 1){
top = queue2.poll();
queue1.offer(top);
}
top = queue2.poll();
}else{
while(queue1.size() > 1){
top = queue1.poll();
queue2.offer(top);
}
top = queue1.poll();
}
return top;
}
/** Get the top element. */
public int top() {
int top = 0;
if(queue1.isEmpty()){
while(!queue2.isEmpty()){
top = queue2.poll();
queue1.offer(top);
}
}else{
while(!queue1.isEmpty()){
top = queue1.poll();
queue2.offer(top);
}
}
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}
思路二：單個隊(duì)列模擬棧
思路一使用兩個隊(duì)列從而確保值從隊(duì)列中丟出的過程不會丟失。但是其實(shí)一個隊(duì)列已經(jīng)足以來模擬棧。我們只需要在每一次往隊(duì)列中輸入數(shù)據(jù)時，確保當(dāng)前隊(duì)列中的輸出順序和棧相同即可。同樣我們使用圖片來模擬一下過程。
1.輸入1，這時隊(duì)列為空，將1正常輸入
2.輸入2，這時為了確保隊(duì)列的輸出順序和棧相同，我需要將1輸出并重新輸入，這時可以把1看成一個新輸入的值，所以將在2之后輸出
3.輸入3，同上一步，在輸入新加入的值后，將余下的值輸出后重新輸入一遍
其實(shí)隊(duì)列的最大特點(diǎn)就是可以維護(hù)原來的輸入順序，因此每次輸出再重新輸入的數(shù)據(jù)之間的順序不會受到影響。
4.pop和push只需要輸出或者讀取隊(duì)首的值即可
class MyStack {
/** Initialize your data structure here. */
Queue queue;
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
int size = queue.size();
queue.offer(x);
while (size-- > 0) {
queue.offer(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68136.html
摘要：下面是入棧時代碼獲得隊(duì)列長度反轉(zhuǎn)次數(shù)為隊(duì)列長度減一反轉(zhuǎn)語言沒有棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組或雙端隊(duì)列實(shí)現(xiàn)。這類編程語言就壓根不需要用隊(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...
摘要：注意的方法是和，實(shí)際上我們應(yīng)該實(shí)現(xiàn)的是和或者和，的實(shí)現(xiàn)和是一樣的，但將改為時，我們要先把到的元素保存，然后再彈出輸出棧，然后返回這個保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...
摘要：題目使用棧實(shí)現(xiàn)隊(duì)列的下列操作將一個元素放入隊(duì)列的尾部。用棧實(shí)現(xiàn)隊(duì)列，可以用兩個棧完成題解。入隊(duì)列時用存入節(jié)點(diǎn)，出隊(duì)列時內(nèi)節(jié)點(diǎn)順序出棧壓入中。這類編程語言就壓根不需要用隊(duì)列實(shí)現(xiàn)棧或用棧實(shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用棧實(shí)現(xiàn)隊(duì)列的下列操作： push(x) -- 將一個元素放入隊(duì)列的尾部。 pop() -- 從隊(duì)列首部移除元素。 peek() -- 返回隊(duì)...
摘要：雙隊(duì)列法復(fù)雜度時間空間思路和類似，我們也可以用兩個隊(duì)列來模擬棧的操作。當(dāng)時，我們將數(shù)字進(jìn)非空的隊(duì)列就行了。操作和一樣，區(qū)別在于我們拿到最后一個數(shù)后，還要再把它進(jìn)另一個隊(duì)列中。 雙隊(duì)列法 復(fù)雜度 時間 O(N) 空間 O(N) 思路 和Implement Queue using Stack類似，我們也可以用兩個隊(duì)列來模擬棧的操作。當(dāng)push時，我們將數(shù)字offer進(jìn)非空的隊(duì)列就行了。當(dāng)p...
摘要：題目要求通過隊(duì)列實(shí)現(xiàn)一個棧的功能。棧的為壓入棧頂，出棧，棧頂元素，棧是否為空。重復(fù)上述的操作。但是當(dāng)需要彈出元素時，則從桶彈出。這樣，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保證位輸入順序。極大的減少了不必要的入棧出棧。 題目要求 Implement the following operations of a queue using stacks. push(x) ...
閱讀 2273·2023-04-25 23:15
閱讀 1937·2021-11-22 09:34
閱讀 1561·2021-11-15 11:39
閱讀 968·2021-11-15 11:37
閱讀 2162·2021-10-14 09:43
閱讀 3502·2021-09-27 13:59
閱讀 1511·2019-08-30 15:43
閱讀 3475·2019-08-30 15:43
