用棧實現(xiàn)隊列 & 用隊列實現(xiàn)棧
棧和隊列
棧和隊列都是一種數(shù)據(jù)結(jié)構(gòu)，它們的作用都是存儲。
每種數(shù)據(jù)結(jié)構(gòu)都有著其對應(yīng)的特性。隊列的特性是先進(jìn)先出，而棧的特性是先進(jìn)后出：
只有滿足了它們的以上特性，一個數(shù)據(jù)結(jié)構(gòu)才能被稱為棧或者隊列。
接下來我們看一下這兩道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)設(shè)計題：
用棧實現(xiàn)隊列
要用棧實現(xiàn)隊列，就得實現(xiàn)隊列的以下API：
void push(int x) // 將元素添加到隊列的尾處
int pop() //刪除隊列的頭部元素并且返回
int peek() //返回隊列的頭個元素
boolean empty() //判斷隊列是否為空
我們要讓設(shè)計的隊列滿足以上API的使用。
隊列有隊列頭部和隊列尾部。所以我們可以用兩個棧，通過棧的特性讓它們相互配合從而實現(xiàn)一個隊列：
Stack<Integer> stackPush; //一個棧用來負(fù)責(zé)push元素
Stack<Integer> stackPop; //一個棧用來負(fù)責(zé)將元素pop掉
//初始化
public MyQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
push():
push()要做的，就是將一個元素添加到隊列的尾處。
所以這里我們可以直接調(diào)用棧的push()，然后把元素打入stachPush這個棧就好了：
public void push(int x) {
stackPush.push(x);
}
此時，元素1就在stachPush這個棧的底部：
pop():
pop()就是刪除隊列的頭部元素并且返回。
有了剛才push()的經(jīng)驗，pop()依然可以按照push()剛才經(jīng)驗，就是當(dāng)stackPop為空的時候，按順序把stackPush里面的元素一個一個pop()掉，并且返回給stackPop：
然后再將stackPop()里面的元素pop()返回：
public int pop() {
if (stackPop.isEmpty() && stackPush.isEmpty()) {
throw new RuntimeException("Queue is empty.");
} else {
if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
}
return stackPop.pop();
}
peek()：
peek就是返回隊列的頭個元素：
pop()和peek()的區(qū)別是什么呢？就是pop()返回隊列頭個元素并且要刪除，但是peek()返回卻不刪除呀。
所以，和pop()的思路一樣，只需要在最后返回的時候把stackPop.pop()換成stackPop.peek()就完事了。
public int peek() {
if (stackPush.isEmpty() && stackPop.isEmpty()) {
throw new RuntimeException("Queue is empyt.");
} else {
if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
}
return stackPop.peek();
}
empty()：
判斷隊列是否為空，為空就返回true，不為空就返回false。
所以我們也可以直接判斷兩個棧是否同時為空。只要同時為空就返回true，不同時為空就返回false：
public boolean empty() {
return stackPop.isEmpty() && stackPush.isEmpty();
}
可以看出，用棧實現(xiàn)隊列思路還是比較簡單的。主要利用的是兩個棧的相互配合。其核心思路就是一個數(shù)據(jù)從一個棧的隊尾移動到另一個棧，就處于隊頭的位置。
那么來說一下時間復(fù)雜度，當(dāng)隊列為空的時候pop()和peek()都要通過while循環(huán)把元素從stackPush移動到stackPop，所以復(fù)雜度是O(n)。
用隊列實現(xiàn)棧
先看看棧的API：
void push(int x) //將元素壓入棧頂
int pop() //移除并返回棧頂元素
int top() //返回棧頂元素
boolean empty() //如果棧是空的，返回 true ；否則，返回 false 。
和隊列的API一樣。只不過這一次我們是要模擬由隊列實現(xiàn)棧。
如果說用棧實現(xiàn)隊列是一種相互配合的方式的話，那么由隊列實現(xiàn)棧就不需要了。我們可以使用ArrayDeque()來實現(xiàn)隊列。
Queue<Integer> queue;
// 使用ArrayDeque作為隊列
public MyStack() {
queue = new ArrayDeque<>();
}
push(int x)：
根據(jù)棧的特性，第一個入棧的元素會處于棧底部。所以在使用隊列模擬棧的時候，可以先把元素入隊列，然后再一個一個拿出來，最后再入一次隊列，這樣子原本處于隊列頭的元素就到了隊列尾部，相當(dāng)于棧頭：
// 入棧時，將新元素x進(jìn)入隊列后，將新元素x之前的所有元素重新入隊，此時元素x處于隊頭
public void push(int x) {
queue.offer(x);
int size = queue.size();
for (int i = 0; i < size - 1; i++) {
queue.offer(queue.poll());
}
}
pop():
由于出棧的操作是和出隊列的操作是相同的，當(dāng)我們把元素從隊列頭變到隊列尾部后，就直接poll()出來即可：
public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException("EMPTY STACK");
}
return queue.poll();
}
top() ：
獲取棧頭部元素，就相當(dāng)于隊列的peek():
public int top() {
if (queue.isEmpty()) {
throw new RuntimeException("EMPTY STACK");
}
return queue.peek();
}
empty():
返回隊列是否為空，都是通用的：
public boolean empty() {
return queue.isEmpty();
}
相比于用棧實現(xiàn)隊列，用隊列實現(xiàn)棧就非常簡單。核心思想就是將隊列的元素先拿出來再放進(jìn)去從而滿足先進(jìn)后出的特性。
那么它們的時間復(fù)雜度是多少呢？其它操作都是O(1)。只有pop()操作需要通過循環(huán)把元素從隊列拿出來再放進(jìn)去，所以時間復(fù)雜度是O(n)。
以上就是用棧實現(xiàn)隊列 & 用隊列實現(xiàn)棧的思路。主要是用來考察棧和隊列的特性。
