# 【进阶篇 - Day 39】 2020-12-09 设计系列（07. 高频面试题 ）
# 题目描述
# 入选理由
- 面试时考察对数据结构的实际应用与理解，避免了“刷题家”们背题大法
- 同时也考察了大家的代码功底，在实现算法的同时，也要把代码写的简洁优美，具有可维护性与健壮性
# 题目描述
剑指 Offer 09. 用两个栈实现队列 (opens new window) > 641. 设计循环双端队列 (opens new window) > 146. LRU 缓存机制 (opens new window) > 1206. 设计跳表 (opens new window) (这题可以等后面学了跳表专题再回来做)
# 我的回答
https://github.com/leetcode-pp/91alg-2/issues/65#issuecomment-741585662
# 用两个栈实现队列
# 时空复杂度
时间复杂度：O(1) 整体上每个操作都是 O(2) 参数级别
空间复杂度: O(n)
var CQueue = function () {
this.startStack = []
this.endStack = []
};
CQueue.prototype.appendTail = function (value) {
this.startStack.push(value)
};
CQueue.prototype.deleteHead = function () {
if (!this.endStack.length && this.startStack.length) {
while (this.startStack.length) {
this.endStack.push(this.startStack.pop())
}
}
return this.endStack.length ? this.endStack.pop() : -1
};
# 设计循环双端队列
时间复杂度：O(1)
空间复杂度: O(n)
还想写个数组，还是不浪费自己时间了
设计题真是累啊
class DoubleLinkedListNode {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
/**
* Initialize your data structure here. Set the size of the deque to be k.
* @param {number} k
*/
var MyCircularDeque = function (k) {
this.max = k
this.count = 0
this.head = new DoubleLinkedListNode(null)
this.tail = new DoubleLinkedListNode(null)
this.head.next = this.tail
this.tail.prev = this.head
};
/**
* Adds an item at the front of Deque. Return true if the operation is successful.
* @param {number} value
* @return {boolean}
*/
MyCircularDeque.prototype.insertFront = function (value) {
if (this.count >= this.max) return false
const head = this.head.next
const node = new DoubleLinkedListNode(value)
node.next = head
head.prev = node
node.prev = this.head
this.head.next = node
this.count++
return true
};
/**
* Adds an item at the rear of Deque. Return true if the operation is successful.
* @param {number} value
* @return {boolean}
*/
MyCircularDeque.prototype.insertLast = function (value) {
if (this.count >= this.max) return false
const tail = this.tail.prev
const node = new DoubleLinkedListNode(value)
node.prev = tail
tail.next = node
node.next = this.tail
this.tail.prev = node
this.count++
return true
};
/**
* Deletes an item from the front of Deque. Return true if the operation is successful.
* @return {boolean}
*/
MyCircularDeque.prototype.deleteFront = function () {
if (!this.count) return false
const next = this.head.next.next
this.head.next = next
next.prev = this.head
this.count--
return true
};
/**
* Deletes an item from the rear of Deque. Return true if the operation is successful.
* @return {boolean}
*/
MyCircularDeque.prototype.deleteLast = function () {
if (!this.count) return false
const prev = this.tail.prev.prev
this.tail.prev = prev
prev.next = this.tail
this.count--
return true
};
/**
* Get the front item from the deque.
* @return {number}
*/
MyCircularDeque.prototype.getFront = function () {
if (!this.count) return -1
return this.head.next.value
};
/**
* Get the last item from the deque.
* @return {number}
*/
MyCircularDeque.prototype.getRear = function () {
if (!this.count) return -1
return this.tail.prev.value
};
/**
* Checks whether the circular deque is empty or not.
* @return {boolean}
*/
MyCircularDeque.prototype.isEmpty = function () {
return this.count === 0
};
/**
* Checks whether the circular deque is full or not.
* @return {boolean}
*/
MyCircularDeque.prototype.isFull = function () {
return this.count === this.max
};
# LRU 缓存机制
时间复杂度：O(1)
空间复杂度: O(n)
class DoubleLinkedListNode {
constructor(key, value) {
this.key = key
this.value = value;
this.prev = null;
this.next = null;
}
}
var LRUCache = function (capacity) {
this.max = capacity
this.head = new DoubleLinkedListNode(null, null)
this.tail = new DoubleLinkedListNode(null, null)
this.head.next = this.tail
this.tail.prev = this.head
this.map = new Map()
};
LRUCache.prototype._remove = function (node) {
node.prev.next = node.next
node.next.prev = node.prev
node.prev = null
node.next = null
return node
};
LRUCache.prototype._addToHead = function (node) {
const head = this.head.next
node.next = head
head.prev = node
node.prev = this.head
this.head.next = node
};
LRUCache.prototype.get = function (key) {
if (this.map.has(key)) {
const node = this.map.get(key)
this._addToHead(this._remove(node))
return node.value
} else {
return -1
}
};
LRUCache.prototype.put = function (key, value) {
if (this.map.has(key)) {
const node = this.map.get(key)
node.value = value
this._addToHead(this._remove(node))
return
}
if (this.map.size >= this.max) {
this.map.delete(this.tail.prev.key)
this._remove(this.tail.prev)
}
const newNode = new DoubleLinkedListNode(key, value)
this.map.set(key, newNode)
this._addToHead(newNode)
};
# 1206. 设计跳表
时间复杂度：O(1) 整体上每个操作都是 O(2) 参数级别
空间复杂度: O(n)
// TODO: 跳表