首页 计算机科学 算法训练 2023

# 队列和哈希

# 算法题

# 1. 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/05_hash_queue/level_2/topic_1.go

  1. 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ push 、 pop 、 peek 、 empty ）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top , peek/pop from top , size , 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
type MyQueue struct {
	inStock, outStock []int
}
func Constructor() MyQueue {
	return MyQueue{}
}
func (q *MyQueue) Push(x int) {
	q.inStock = append(q.inStock, x)
}
func (q *MyQueue) Pop() int {
	if len(q.outStock) == 0 {
		q.tranceInStockToOutStock()
	}
	ans := q.outStock[len(q.outStock)-1]
	q.outStock = q.outStock[:len(q.outStock)-1]
	return ans
}
func (q *MyQueue) Peek() int {
	if len(q.outStock) == 0 {
		q.tranceInStockToOutStock()
	}
	return q.outStock[len(q.outStock)-1]
}
func (q *MyQueue) Empty() bool {
	return len(q.inStock) == 0 && len(q.outStock) == 0
}
func (q *MyQueue) tranceInStockToOutStock() {
	for len(q.inStock) > 0 {
		q.outStock = append(q.outStock, q.inStock[len(q.inStock)-1])
		q.inStock = q.inStock[:len(q.inStock)-1]
	}
}
# 2. 用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/05_hash_queue/level_2/topic_2.go
  • 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（ push 、 top 、 pop 和 empty ）。
    实现 MyStack 类：
    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
    注意：
    • 你只能使用队列的基本操作 —— 也就是 push to back 、 peek/pop from front 、 size 和 is empty 这些操作。
    • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。
type MyStack struct {
	outQueue, tempQueue []int
}
func ConstructorV2() MyStack {
	return MyStack{}
}
func (s *MyStack) Push(x int) {
	s.tempQueue = append(s.tempQueue, x)
	for len(s.outQueue) > 0 {
		s.tempQueue = append(s.tempQueue, s.outQueue[0])
		s.outQueue = s.outQueue[1:]
	}
	s.tempQueue, s.outQueue = s.outQueue, s.tempQueue
}
func (s *MyStack) Pop() int {
	ans := s.outQueue[0]
	s.outQueue = s.outQueue[1:]
	return ans
}
func (s *MyStack) Top() int {
	return s.outQueue[0]
}
func (s *MyStack) Empty() bool {
	return len(s.outQueue) == 0
}
# 3. LRU 缓存
https://leetcode.cn/problems/lru-cache/
https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/05_hash_queue/level_3/topic_1.go
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
//map + 双向链表实现 LRU 缓存
type LRUCache struct {
	size       int
	cap        int
	cache      map[int]*LinkNode
	head, tail *LinkNode
}
type LinkNode struct {
	key, val  int
	pre, next *LinkNode
}
func Constructor(capacity int) LRUCache {
	dummyHeadNode, dummyTailNode := &LinkNode{0, 0, nil, nil}, &LinkNode{0, 0, nil, nil}
	dummyHeadNode.next = dummyTailNode
	dummyTailNode.pre = dummyHeadNode
	return LRUCache{
		size:  0,
		cap:   capacity,
		cache: map[int]*LinkNode{},
		head:  dummyHeadNode,
		tail:  dummyTailNode,
	}
}
// 每次 get 都会把操作的节点移动到链表的头部
func (ca *LRUCache) Get(key int) int {
	node, ok := ca.cache[key]
	if !ok {
		return -1
	}
	out := node.val
	// 移动到 head
	node.delete()
	ca.addNodeToHead(node)
	return out
}
func (ca *LRUCache) Put(key int, value int) {
	node, ok := ca.cache[key]
	if !ok {
		// insert
		if ca.size >= ca.cap {
			// 尾删
			tailNode := ca.tail.pre
			tailNode.delete()
			delete(ca.cache, tailNode.key)
			ca.size--
		}
		newNode := &LinkNode{key, value, nil, nil}
		ca.addNodeToHead(newNode)
		ca.cache[key] = newNode
		ca.size++
	} else {
		// update
		node.val = value
		node.delete()
		ca.addNodeToHead(node)
	}
}
func (ca *LRUCache) addNodeToHead(node *LinkNode) {
	node.pre = ca.head
	node.next = ca.head.next
	ca.head.next.pre = node
	ca.head.next = node
}
func (node *LinkNode) delete() {
	node.next.pre = node.pre
	node.pre.next = node.next
}
 
-->