實現一個佇列,使得push_rear(), pop_front() 和get_min()的時間複雜度為O(1)

實現一個佇列,使得push_rear(), pop_front() 和get_min()的時間複雜度為O(1)

問題描述:

實現一個佇列,使得它的push_rear(), pop_front() 和get_min() 這三個函式的時間複雜的為常數(即O(1))。

分析:

在leetcode上面有類似的題目,但是其所要求的是實現一個棧(stack)而不是佇列。

這裡將使用兩個棧來作為輔助資料結構。第一個棧專門用來接收新來的資料,第二個棧專門接收第一個棧中的資料。每一次都把第一個棧中的所有資料倒轉到第二個中。資料永遠從第二個棧中pop出去。

具體舉例來看:現在四個數字[1, 5, 2, 4] (4是最早到達的資料)依次壓入棧中,每壓入一個數字的時候,在其旁邊(黃色背景)使用另一個數字記錄當前棧中最小的值。所以,從下圖中,當壓入數字5的時候,當前棧中最小的值是2,所以其旁邊的數字為2.

四個數字入棧之後,把它們分別彈出然後再次入棧到第二個棧中。黃色背景的數值依然是記錄當前棧中最小的數字。當需要pop front操作的時候,把第二個棧中top元素彈出。

這時候發現,這三個函式push_rear(), pop_front() 和get_min()的時間複雜度是為O(0)的。演算法執行期間間歇性的將資料從棧1中倒轉到棧2中,這個操作所用的時間複雜度為O(n),但是因為並不是在操作每一個元素的時候都需要倒轉,所以平均下來整個演算法的三個函式的時間複雜度是常數。

這裡寫圖片描述

實現

import java.util.EmptyStackException;
import java.util.Stack;
public class ContantQueue {
private Stack<Value> s1 = new Stack<>();
private Stack<Value> s2 = new Stack<>();
public void pushRear(int value){
System.out.println("input number: " value);
pushRear(s1, value);
}
private void pushRear(Stack<Value> s, int value){
if(s.empty())
s.push(new Value(value, value));
else{
if(value > s.peek().min){
s.push(new Value(value, s.peek().min));
}else{
s.push(new Value(value, value));
}
}
}
public int popFront(){
if(empty()) throw new EmptyStackException();
return s2.pop().value;
}
public int getMin(){
if(empty()) throw new EmptyStackException();
return s2.peek().min;
}
public boolean empty(){
if(s2.empty()){
transferNums();
}
if(s2.empty()) return true;
else return false;
}
private void transferNums(){
if(s1.empty()) return;
while(!s1.empty()){
pushRear(s2, s1.pop().value);
}
}
class Value{
int value;
int min;
public Value(){}
public Value(int value, int min){
this.value = value;
this.min = min;
}
}
public static void main(String[] args) {
ContantQueue queue = new ContantQueue();
queue.pushRear(4);
queue.pushRear(2);
queue.pushRear(5);
queue.pushRear(1);
assert queue.popFront() == 4;
assert queue.popFront() == 2;
assert queue.popFront() == 5;
assert queue.popFront() == 1;
queue.pushRear(6);
queue.pushRear(2);
queue.pushRear(9);
queue.pushRear(7);
assert queue.popFront() == 6;
assert queue.getMin() == 2;
assert queue.popFront() == 2;
assert queue.getMin() == 7;
queue.pushRear(16);
queue.pushRear(8);
assert queue.popFront() == 9;
assert queue.popFront() == 7;
assert queue.popFront() == 16;
assert queue.popFront() == 8;
}
}

該程式碼實現只適用於單執行緒。

結束!