|
作者 | labuladong 來源 | labuladong 隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu),，形象一點(diǎn)就是這樣：
這兩種數(shù)據(jù)結(jié)構(gòu)底層其實(shí)都是數(shù)組或者鏈表實(shí)現(xiàn)的,，只是 API 限定了它們的特性，那么今天就來看看如何使用「棧」的特性來實(shí)現(xiàn)一個「隊列」,，如何用「隊列」實(shí)現(xiàn)一個「?！埂?br> 一,、用棧實(shí)現(xiàn)隊列首先,，隊列的 API 如下： class MyQueue {
/** 添加元素到隊尾 */
public void push(int x);
/** 刪除隊頭的元素并返回 */
public int pop();
/** 返回隊頭元素 */
public int peek();
/** 判斷隊列是否為空 */
public boolean empty();
}
我們使用兩個棧s1, s2就能實(shí)現(xiàn)一個隊列的功能（這樣放置棧可能更容易理解）： 
class MyQueue {
private Stack<Integer> s1, s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
// ...
}
當(dāng)調(diào)用push讓元素入隊時,，只要把元素壓入s1即可,，比如說push進(jìn) 3 個元素分別是 1,2,3，那么底層結(jié)構(gòu)就是這樣： 
/** 添加元素到隊尾 */
public void push(int x) {
s1.push(x);
}
那么如果這時候使用peek查看隊頭的元素怎么辦呢,？按道理隊頭元素應(yīng)該是 1,，但是在s1中 1 被壓在棧底，現(xiàn)在就要輪到s2起到一個中轉(zhuǎn)的作用了： 當(dāng)s2為空時,，可以把s1的所有元素取出再添加進(jìn)s2,，這時候s2中元素就是先進(jìn)先出順序了。 
/** 返回隊頭元素 */
public int peek() {
if (s2.isEmpty())
// 把 s1 元素壓入 s2
while (!s1.isEmpty())
s2.push(s1.pop());
return s2.peek();
}
同理,，對于pop操作,，只要操作s2就可以了。 /** 刪除隊頭的元素并返回 */
public int pop() {
// 先調(diào)用 peek 保證 s2 非空
peek();
return s2.pop();
}
最后,，如何判斷隊列是否為空呢,？如果兩個棧都為空的話，就說明隊列為空： /** 判斷隊列是否為空 */
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
至此,，就用棧結(jié)構(gòu)實(shí)現(xiàn)了一個隊列,，核心思想是利用兩個棧互相配合,。 值得一提的是,，這幾個操作的時間復(fù)雜度是多少呢？其他操作都是 O(1),，有點(diǎn)意思的是peek操作,，調(diào)用它時可能觸發(fā)while循環(huán)，這樣的話時間復(fù)雜度是 O(N),，但是大部分情況下while循環(huán)不會被觸發(fā),，時間復(fù)雜度是 O(1)。由于pop操作調(diào)用了peek,，它的時間復(fù)雜度和peek相同,。 像這種情況，可以說它們的最壞時間復(fù)雜度是 O(N),，因?yàn)榘?code>while循環(huán),，可能需要從s1往s2搬移元素,。 但是它們的均攤時間復(fù)雜度是 O(1)，這個要這么理解：對于一個元素,，最多只可能被搬運(yùn)一次,，也就是說peek操作平均到每個元素的時間復(fù)雜度是 O(1)。 二,、用隊列實(shí)現(xiàn)棧如果說雙棧實(shí)現(xiàn)隊列比較巧妙,，那么用隊列實(shí)現(xiàn)棧就比較簡單粗暴了，只需要一個隊列作為底層數(shù)據(jù)結(jié)構(gòu),。首先看下棧的 API： class MyStack {
/** 添加元素到棧頂 */
public void push(int x);
/** 刪除棧頂?shù)脑夭⒎祷?nbsp;*/
public int pop();
/** 返回棧頂元素 */
public int top();
/** 判斷棧是否為空 */
public boolean empty();
}
先說pushAPI,，直接將元素加入隊列，同時記錄隊尾元素,，因?yàn)殛犖苍叵喈?dāng)于棧頂元素,，如果要top查看棧頂元素的話可以直接返回： class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
/** 添加元素到棧頂 */
public void push(int x) {
// x 是隊列的隊尾，是棧的棧頂
q.offer(x);
top_elem = x;
}
/** 返回棧頂元素 */
public int top() {
return top_elem;
}
}
我們的底層數(shù)據(jù)結(jié)構(gòu)是先進(jìn)先出的隊列,，每次pop只能從隊頭取元素,；但是棧是后進(jìn)先出，也就是說popAPI 要從隊尾取元素,。 
解決方法簡單粗暴,，把隊列前面的都取出來再加入隊尾，讓之前的隊尾元素排到隊頭,，這樣就可以取出了： 
/** 刪除棧頂?shù)脑夭⒎祷?nbsp;*/
public int pop() {
int size = q.size();
while (size > 1) {
q.offer(q.poll());
size--;
}
// 之前的隊尾元素已經(jīng)到了隊頭
return q.poll();
}
這樣實(shí)現(xiàn)還有一點(diǎn)小問題就是,，原來的隊尾元素被提到隊頭并刪除了，但是top_elem變量沒有更新,，我們還需要一點(diǎn)小修改： /** 刪除棧頂?shù)脑夭⒎祷?nbsp;*/
public int pop() {
int size = q.size();
// 留下隊尾 2 個元素
while (size > 2) {
q.offer(q.poll());
size--;
}
// 記錄新的隊尾元素
top_elem = q.peek();
q.offer(q.poll());
// 刪除之前的隊尾元素
return q.poll();
}
最后,，APIempty就很容易實(shí)現(xiàn)了，只要看底層的隊列是否為空即可： /** 判斷棧是否為空 */
public boolean empty() {
return q.isEmpty();
}
很明顯,，用隊列實(shí)現(xiàn)棧的話,，pop 操作時間復(fù)雜度是 O(N)，其他操作都是 O(1),。 個人認(rèn)為，用隊列實(shí)現(xiàn)棧沒啥亮點(diǎn),，但是用雙棧實(shí)現(xiàn)隊列是值得學(xué)習(xí)的,。 出棧順序本來就和入棧順序相反，但是從棧s1搬運(yùn)元素到s2之后,，s2中元素出棧的順序就變成了隊列的先進(jìn)先出順序,，這個特性有點(diǎn)類似「負(fù)負(fù)得正」，確實(shí)不容易想到,。
|
