// 雙端隊(duì)列
struct DoubleQueue {
private var data = [Int]()
private var n = 0, pre = 0, tra = 0
public var trail: Int? {
return isEmpty ? nil : data[tra - 1]
}
public var prev: Int? {
return isEmpty ? nil : data[pre]
}
public var total: Int {
return tra - pre
}
public var isEmpty: Bool {
return tra - pre == 0
}
init(num: Int) {
n = num
pre = 0
tra = 0
data = [Int](repeating: Int.min, count: num)
}
@discardableResult
public mutating func enqueue(val: Int) -> Bool {
if total == n {
reBuild()
}
// 數(shù)組前方有空余空間, 需要做數(shù)據(jù)搬移
if tra == n && pre > 0 {
for i in pre..<tra {
data[i-pre] = data[i]
}
tra -= pre
pre = 0
}
data[tra] = val
tra += 1
return true
}
@discardableResult
public mutating func enqueueFront(val: Int) -> Bool {
if total == n {
reBuild()
}
pre = pre > 0 ? pre - 1 : 0
data.insert(val, at: pre)
return true
}
@discardableResult
public mutating func dequeue() -> Int? {
if total == 0 {
return nil
}
let val = data[pre]
pre += 1
return val
}
@discardableResult
public mutating func dequeueBack() -> Int? {
if total == 0 {
return nil
}
let val = data[tra - 1]
tra -= 1
return val
}
private mutating func reBuild() {
let count = n * 2
var newData = [Int](repeating: Int.min, count: count)
let range = newData.startIndex..<newData.index(newData.startIndex, offsetBy: n)
newData.replaceSubrange(range, with: data)
data = newData
n = n * 2
}
}
class MaxQueue {
private var data = [Int]()
private var queue: DoubleQueue!
public var isEmpty: Bool {
return data.count == 0
}
init() {
data = [Int]()
queue = DoubleQueue(num: 10)
}
func max_value() -> Int {
if isEmpty {
return -1
}
return queue.prev!
}
func push_back(_ value: Int) {
while (!queue.isEmpty && value > queue.trail!) {
queue.dequeueBack()
}
queue.enqueue(val: value)
data.append(value)
}
func pop_front() -> Int {
if isEmpty {
return -1
}
let val = data.removeFirst()
if val == queue.prev {
queue.dequeue()
}
return val
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* let obj = MaxQueue()
* let ret_1: Int = obj.max_value()
* obj.push_back(value)
* let ret_3: Int = obj.pop_front()
*/
