小白备战大厂算法笔试(三)——栈、队列、双向队列

文章目录

    • 栈常用操作
    • 栈的实现
      • 基于链表的实现
      • 基于数组的实现
    • 两种实现对比
    • 栈典型应用
  • 队列
    • 队列常用操作
    • 队列实现
      • 基于链表的实现
      • 基于数组的实现
    • 队列典型应用
  • 双向队列
    • 双向队列常用操作
    • 双向队列实现
      • 基于双向链表的实现
      • 基于数组的实现
    • 双向队列应用

栈是一种遵循先入后出的逻辑的线性数据结构。如下图所示,我们把堆叠元素的顶部称为“栈顶”,底部称为“栈底”。将把元素添加到栈顶的操作叫做“入栈”,删除栈顶元素的操作叫做“出栈”。

image-20230907090823345

栈常用操作

栈的常用操作如下表所示,具体的方法名需要根据所使用的编程语言来确定。在此,我们以常见的 push()pop()peek() 命名为例。

表   栈的操作效率

方法描述时间复杂度
push()元素入栈(添加至栈顶)O(1)
pop()栈顶元素出栈O(1)
peek()访问栈顶元素O(1)

Python:

# 初始化栈
# Python 没有内置的栈类,可以把 List 当作栈来使用 
stack: list[int] = []# 元素入栈
stack.append(1)
stack.append(3)
stack.append(2)
stack.append(5)
stack.append(4)# 访问栈顶元素
peek: int = stack[-1]# 元素出栈
pop: int = stack.pop()# 获取栈的长度
size: int = len(stack)# 判断是否为空
is_empty: bool = len(stack) == 0

Go:

/* 初始化栈 */
// 在 Go 中,推荐将 Slice 当作栈来使用
var stack []int/* 元素入栈 */
stack = append(stack, 1)
stack = append(stack, 3)
stack = append(stack, 2)
stack = append(stack, 5)
stack = append(stack, 4)/* 访问栈顶元素 */
peek := stack[len(stack)-1]/* 元素出栈 */
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]/* 获取栈的长度 */
size := len(stack)/* 判断是否为空 */
isEmpty := len(stack) == 0

栈的实现

栈遵循先入后出的原则,因此我们只能在栈顶添加或删除元素。然而,数组和链表都可以在任意位置添加和删除元素,因此栈可以被视为一种受限制的数组或链表

基于链表的实现

使用链表来实现栈时,我们可以将链表的头节点视为栈顶,尾节点视为栈底。

如下图所示,对于入栈操作,我们只需将元素插入链表头部,这种节点插入方法被称为“头插法”。而对于出栈操作,只需将头节点从链表中删除即可。

image-20230907091741410

image-20230907091756460

image-20230907091807967

Python:

class LinkedListStack:"""基于链表实现的栈"""def __init__(self):"""构造方法"""self.__peek: ListNode | None = Noneself.__size: int = 0def size(self) -> int:"""获取栈的长度"""return self.__sizedef is_empty(self) -> bool:"""判断栈是否为空"""return not self.__peekdef push(self, val: int):"""入栈"""node = ListNode(val)node.next = self.__peekself.__peek = nodeself.__size += 1def pop(self) -> int:"""出栈"""num: int = self.peek()self.__peek = self.__peek.nextself.__size -= 1return numdef peek(self) -> int:"""访问栈顶元素"""# 判空处理if not self.__peek:return Nonereturn self.__peek.valdef to_list(self) -> list[int]:"""转化为列表用于打印"""arr = []node = self.__peekwhile node:arr.append(node.val)node = node.nextarr.reverse()return arr

Go:

/* 基于链表实现的栈 */
type linkedListStack struct {// 使用内置包 list 来实现栈data *list.List
}/* 初始化栈 */
func newLinkedListStack() *linkedListStack {return &linkedListStack{data: list.New(),}
}/* 入栈 */
func (s *linkedListStack) push(value int) {s.data.PushBack(value)
}/* 出栈 */
func (s *linkedListStack) pop() any {if s.isEmpty() {return nil}e := s.data.Back()s.data.Remove(e)return e.Value
}/* 访问栈顶元素 */
func (s *linkedListStack) peek() any {if s.isEmpty() {return nil}e := s.data.Back()return e.Value
}/* 获取栈的长度 */
func (s *linkedListStack) size() int {return s.data.Len()
}/* 判断栈是否为空 */
func (s *linkedListStack) isEmpty() bool {return s.data.Len() == 0
}/* 获取 List 用于打印 */
func (s *linkedListStack) toList() *list.List {return s.data
}

基于数组的实现

使用数组实现栈时,我们可以将数组的尾部作为栈顶。如下图所示,入栈与出栈操作分别对应在数组尾部添加元素与删除元素,时间复杂度都为 O(1)。

image-20230907093006467

image-20230907093019100

由于入栈的元素可能会源源不断地增加,因此我们可以使用动态数组,这样就无须自行处理数组扩容问题。

Python:

class ArrayStack:"""基于数组实现的栈"""def __init__(self):"""构造方法"""self.__stack: list[int] = []def size(self) -> int:"""获取栈的长度"""return len(self.__stack)def is_empty(self) -> bool:"""判断栈是否为空"""return self.__stack == []def push(self, item: int):"""入栈"""self.__stack.append(item)def pop(self) -> int:"""出栈"""if self.is_empty():raise IndexError("栈为空")return self.__stack.pop()def peek(self) -> int:"""访问栈顶元素"""if self.is_empty():raise IndexError("栈为空")return self.__stack[-1]def to_list(self) -> list[int]:"""返回列表用于打印"""return self.__stack

Go:

/* 基于数组实现的栈 */
type arrayStack struct {data []int // 数据
}/* 初始化栈 */
func newArrayStack() *arrayStack {return &arrayStack{// 设置栈的长度为 0,容量为 16data: make([]int, 0, 16),}
}/* 栈的长度 */
func (s *arrayStack) size() int {return len(s.data)
}/* 栈是否为空 */
func (s *arrayStack) isEmpty() bool {return s.size() == 0
}/* 入栈 */
func (s *arrayStack) push(v int) {// 切片会自动扩容s.data = append(s.data, v)
}/* 出栈 */
func (s *arrayStack) pop() any {val := s.peek()s.data = s.data[:len(s.data)-1]return val
}/* 获取栈顶元素 */
func (s *arrayStack) peek() any {if s.isEmpty() {return nil}val := s.data[len(s.data)-1]return val
}/* 获取 Slice 用于打印 */
func (s *arrayStack) toSlice() []int {return s.data
}

两种实现对比

支持操作

两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问,但这已超出了栈的定义范畴,因此一般不会用到。

时间效率

在基于数组的实现中,入栈和出栈操作都是在预先分配好的连续内存中进行,具有很好的缓存本地性,因此效率较高。然而,如果入栈时超出数组容量,会触发扩容机制,导致该次入栈操作的时间复杂度变为 O(n) 。

在链表实现中,链表的扩容非常灵活,不存在上述数组扩容时效率降低的问题。但是,入栈操作需要初始化节点对象并修改指针,因此效率相对较低。不过,如果入栈元素本身就是节点对象,那么可以省去初始化步骤,从而提高效率。

综上所述,当入栈与出栈操作的元素是基本数据类型时,例如 intdouble ,我们可以得出以下结论。

  • 基于数组实现的栈在触发扩容时效率会降低,但由于扩容是低频操作,因此平均效率更高。
  • 基于链表实现的栈可以提供更加稳定的效率表现。

空间效率

在初始化列表时,系统会为列表分配“初始容量”,该容量可能超过实际需求。并且,扩容机制通常是按照特定倍率(例如 2 倍)进行扩容,扩容后的容量也可能超出实际需求。因此,基于数组实现的栈可能造成一定的空间浪费

然而,由于链表节点需要额外存储指针,因此链表节点占用的空间相对较大

综上,我们不能简单地确定哪种实现更加节省内存,需要针对具体情况进行分析。

栈典型应用

  • 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页,浏览器就会将上一个网页执行入栈,这样我们就可以通过后退操作回到上一页面。后退操作实际上是在执行出栈。如果要同时支持后退和前进,那么需要两个栈来配合实现。
  • 程序内存管理。每次调用函数时,系统都会在栈顶添加一个栈帧,用于记录函数的上下文信息。在递归函数中,向下递推阶段会不断执行入栈操作,而向上回溯阶段则会执行出栈操作。

队列

队列是一种遵循先入先出规则的线性数据结构。顾名思义,队列模拟了排队现象,即新来的人不断加入队列的尾部,而位于队列头部的人逐个离开。

如下图所示,我们将队列的头部称为“队首”,尾部称为“队尾”,将把元素加入队尾的操作称为“入队”,删除队首元素的操作称为“出队”。

image-20230907130759869

队列常用操作

表   队列操作效率

方法名描述时间复杂度
push()元素入队,即将元素添加至队尾O(1)
pop()队首元素出队O(1)
peek()访问队首元素O(1)

Python:

# 初始化队列
# 在 Python 中,我们一般将双向队列类 deque 看作队列使用
# 虽然 queue.Queue() 是纯正的队列类,但不太好用,因此不建议
que: deque[int] = collections.deque()# 元素入队
que.append(1)
que.append(3)
que.append(2)
que.append(5)
que.append(4)# 访问队首元素
front: int = que[0];# 元素出队
pop: int = que.popleft()# 获取队列的长度
size: int = len(que)# 判断队列是否为空
is_empty: bool = len(que) == 0

Go:

/* 初始化队列 */
// 在 Go 中,将 list 作为队列来使用
queue := list.New()/* 元素入队 */
queue.PushBack(1)
queue.PushBack(3)
queue.PushBack(2)
queue.PushBack(5)
queue.PushBack(4)/* 访问队首元素 */
peek := queue.Front()/* 元素出队 */
pop := queue.Front()
queue.Remove(pop)/* 获取队列的长度 */
size := queue.Len()/* 判断队列是否为空 */
isEmpty := queue.Len() == 0

队列实现

基于链表的实现

如下图所示,我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”,规定队尾仅可添加节点,队首仅可删除节点。

image-20230907131417462

image-20230907131442892

image-20230907131506809

Python:

class LinkedListQueue:"""基于链表实现的队列"""def __init__(self):"""构造方法"""self.__front: ListNode | None = None  # 头节点 frontself.__rear: ListNode | None = None  # 尾节点 rearself.__size: int = 0def size(self) -> int:"""获取队列的长度"""return self.__sizedef is_empty(self) -> bool:"""判断队列是否为空"""return not self.__frontdef push(self, num: int):"""入队"""# 尾节点后添加 numnode = ListNode(num)# 如果队列为空,则令头、尾节点都指向该节点if self.__front is None:self.__front = nodeself.__rear = node# 如果队列不为空,则将该节点添加到尾节点后else:self.__rear.next = nodeself.__rear = nodeself.__size += 1def pop(self) -> int:"""出队"""num = self.peek()# 删除头节点self.__front = self.__front.nextself.__size -= 1return numdef peek(self) -> int:"""访问队首元素"""if self.size() == 0:print("队列为空")return Falsereturn self.__front.valdef to_list(self) -> list[int]:"""转化为列表用于打印"""queue = []temp = self.__frontwhile temp:queue.append(temp.val)temp = temp.nextreturn queue

Go:

/* 基于链表实现的队列 */
type linkedListQueue struct {// 使用内置包 list 来实现队列data *list.List
}/* 初始化队列 */
func newLinkedListQueue() *linkedListQueue {return &linkedListQueue{data: list.New(),}
}/* 入队 */
func (s *linkedListQueue) push(value any) {s.data.PushBack(value)
}/* 出队 */
func (s *linkedListQueue) pop() any {if s.isEmpty() {return nil}e := s.data.Front()s.data.Remove(e)return e.Value
}/* 访问队首元素 */
func (s *linkedListQueue) peek() any {if s.isEmpty() {return nil}e := s.data.Front()return e.Value
}/* 获取队列的长度 */
func (s *linkedListQueue) size() int {return s.data.Len()
}/* 判断队列是否为空 */
func (s *linkedListQueue) isEmpty() bool {return s.data.Len() == 0
}/* 获取 List 用于打印 */
func (s *linkedListQueue) toList() *list.List {return s.data
}

基于数组的实现

由于数组删除首元素的时间复杂度为O(n),这会导致出队操作效率较低。然而,我们可以采用以下巧妙方法来避免这个问题。

我们可以使用一个变量 front 指向队首元素的索引,并维护一个变量 size 用于记录队列长度。定义 rear = front + size ,这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计,数组中包含元素的有效区间为 [front, rear - 1],各种操作的实现方法如下图所示。

  • 入队操作:将输入元素赋值给 rear 索引处,并将 size 增加 1 。
  • 出队操作:只需将 front 增加 1 ,并将 size 减少 1 。

可以看到,入队和出队操作都只需进行一次操作,时间复杂度均为 O(1) 。

image-20230907132113215

image-20230907132153591

image-20230907132218012

你可能会发现一个问题:在不断进行入队和出队的过程中,frontrear 都在向右移动,当它们到达数组尾部时就无法继续移动了。为解决此问题,我们可以将数组视为首尾相接的“环形数组”。

对于环形数组,我们需要让 frontrear 在越过数组尾部时,直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现,代码如下所示。

Python:

class ArrayQueue:"""基于环形数组实现的队列"""def __init__(self, size: int):"""构造方法"""self.__nums: list[int] = [0] * size  # 用于存储队列元素的数组self.__front: int = 0  # 队首指针,指向队首元素self.__size: int = 0  # 队列长度def capacity(self) -> int:"""获取队列的容量"""return len(self.__nums)def size(self) -> int:"""获取队列的长度"""return self.__sizedef is_empty(self) -> bool:"""判断队列是否为空"""return self.__size == 0def push(self, num: int):"""入队"""if self.__size == self.capacity():raise IndexError("队列已满")# 计算尾指针,指向队尾索引 + 1# 通过取余操作,实现 rear 越过数组尾部后回到头部rear: int = (self.__front + self.__size) % self.capacity()# 将 num 添加至队尾self.__nums[rear] = numself.__size += 1def pop(self) -> int:"""出队"""num: int = self.peek()# 队首指针向后移动一位,若越过尾部则返回到数组头部self.__front = (self.__front + 1) % self.capacity()self.__size -= 1return numdef peek(self) -> int:"""访问队首元素"""if self.is_empty():raise IndexError("队列为空")return self.__nums[self.__front]def to_list(self) -> list[int]:"""返回列表用于打印"""res = [0] * self.size()j: int = self.__frontfor i in range(self.size()):res[i] = self.__nums[(j % self.capacity())]j += 1return res

Go:

/* 基于环形数组实现的队列 */
type arrayQueue struct {nums        []int // 用于存储队列元素的数组front       int   // 队首指针,指向队首元素queSize     int   // 队列长度queCapacity int   // 队列容量(即最大容纳元素数量)
}/* 初始化队列 */
func newArrayQueue(queCapacity int) *arrayQueue {return &arrayQueue{nums:        make([]int, queCapacity),queCapacity: queCapacity,front:       0,queSize:     0,}
}/* 获取队列的长度 */
func (q *arrayQueue) size() int {return q.queSize
}/* 判断队列是否为空 */
func (q *arrayQueue) isEmpty() bool {return q.queSize == 0
}/* 入队 */
func (q *arrayQueue) push(num int) {// 当 rear == queCapacity 表示队列已满if q.queSize == q.queCapacity {return}// 计算尾指针,指向队尾索引 + 1// 通过取余操作,实现 rear 越过数组尾部后回到头部rear := (q.front + q.queSize) % q.queCapacity// 将 num 添加至队尾q.nums[rear] = numq.queSize++
}/* 出队 */
func (q *arrayQueue) pop() any {num := q.peek()// 队首指针向后移动一位,若越过尾部则返回到数组头部q.front = (q.front + 1) % q.queCapacityq.queSize--return num
}/* 访问队首元素 */
func (q *arrayQueue) peek() any {if q.isEmpty() {return nil}return q.nums[q.front]
}/* 获取 Slice 用于打印 */
func (q *arrayQueue) toSlice() []int {rear := (q.front + q.queSize)if rear >= q.queCapacity {rear %= q.queCapacityreturn append(q.nums[q.front:], q.nums[:rear]...)}return q.nums[q.front:rear]
}

以上实现的队列仍然具有局限性,即其长度不可变。然而,这个问题不难解决,我们可以将数组替换为动态数组,从而引入扩容机制。

两种实现的对比结论与栈一致。

队列典型应用

  • 淘宝订单。购物者下单后,订单将加入队列中,系统随后会根据顺序依次处理队列中的订单。在双十一期间,短时间内会产生海量订单,高并发成为工程师们需要重点攻克的问题。
  • 各类待办事项。任何需要实现“先来后到”功能的场景,例如打印机的任务队列、餐厅的出餐队列等。队列在这些场景中可以有效地维护处理顺序。

双向队列

在队列中,我们仅能在头部删除或在尾部添加元素。双向队列提供了更高的灵活性,允许在头部和尾部执行元素的添加或删除操作。

image-20230907164254747

双向队列常用操作

双向队列的常用操作如下表所示,具体的方法名称需要根据所使用的编程语言来确定。

表   双向队列操作效率

方法名描述时间复杂度
pushFirst()将元素添加至队首O(1)
pushLast()将元素添加至队尾O(1)
popFirst()删除队首元素O(1)
popLast()删除队尾元素O(1)
peekFirst()访问队首元素O(1)
peekLast()访问队尾元素O(1)

我们可以直接使用编程语言中已实现的双向队列类。

Python:

# 初始化双向队列
deque: deque[int] = collections.deque()# 元素入队
deque.append(2)      # 添加至队尾
deque.append(5)
deque.append(4)
deque.appendleft(3)  # 添加至队首
deque.appendleft(1)# 访问元素
front: int = deque[0]  # 队首元素
rear: int = deque[-1]  # 队尾元素# 元素出队
pop_front: int = deque.popleft()  # 队首元素出队
pop_rear: int = deque.pop()       # 队尾元素出队# 获取双向队列的长度
size: int = len(deque)# 判断双向队列是否为空
is_empty: bool = len(deque) == 0

Go:

/* 初始化双向队列 */
// 在 Go 中,将 list 作为双向队列使用
deque := list.New()/* 元素入队 */
deque.PushBack(2)      // 添加至队尾
deque.PushBack(5)
deque.PushBack(4)
deque.PushFront(3)     // 添加至队首
deque.PushFront(1)/* 访问元素 */
front := deque.Front() // 队首元素
rear := deque.Back()   // 队尾元素/* 元素出队 */
deque.Remove(front)    // 队首元素出队
deque.Remove(rear)     // 队尾元素出队/* 获取双向队列的长度 */
size := deque.Len()/* 判断双向队列是否为空 */
isEmpty := deque.Len() == 0

双向队列实现

双向队列的实现与队列类似,可以选择链表或数组作为底层数据结构。

基于双向链表的实现

采用“双向链表”作为双向队列的底层数据结构。如下图所示,我们将双向链表的头节点和尾节点视为双向队列的队首和队尾,同时实现在两端添加和删除节点的功能。

image-20230907164856430

image-20230907164907712

image-20230907164931654

image-20230907164944182

image-20230907164952931

Python:

class ListNode:"""双向链表节点"""def __init__(self, val: int):"""构造方法"""self.val: int = valself.next: ListNode | None = None  # 后继节点引用self.prev: ListNode | None = None  # 前驱节点引用class LinkedListDeque:"""基于双向链表实现的双向队列"""def __init__(self):"""构造方法"""self.front: ListNode | None = None  # 头节点 frontself.rear: ListNode | None = None  # 尾节点 rearself.__size: int = 0  # 双向队列的长度def size(self) -> int:"""获取双向队列的长度"""return self.__sizedef is_empty(self) -> bool:"""判断双向队列是否为空"""return self.size() == 0def push(self, num: int, is_front: bool):"""入队操作"""node = ListNode(num)# 若链表为空,则令 front, rear 都指向 nodeif self.is_empty():self.front = self.rear = node# 队首入队操作elif is_front:# 将 node 添加至链表头部self.front.prev = nodenode.next = self.frontself.front = node  # 更新头节点# 队尾入队操作else:# 将 node 添加至链表尾部self.rear.next = nodenode.prev = self.rearself.rear = node  # 更新尾节点self.__size += 1  # 更新队列长度def push_first(self, num: int):"""队首入队"""self.push(num, True)def push_last(self, num: int):"""队尾入队"""self.push(num, False)def pop(self, is_front: bool) -> int:"""出队操作"""# 若队列为空,直接返回 Noneif self.is_empty():return None# 队首出队操作if is_front:val: int = self.front.val  # 暂存头节点值# 删除头节点fnext: ListNode | None = self.front.nextif fnext != None:fnext.prev = Noneself.front.next = Noneself.front = fnext  # 更新头节点# 队尾出队操作else:val: int = self.rear.val  # 暂存尾节点值# 删除尾节点rprev: ListNode | None = self.rear.previf rprev != None:rprev.next = Noneself.rear.prev = Noneself.rear = rprev  # 更新尾节点self.__size -= 1  # 更新队列长度return valdef pop_first(self) -> int:"""队首出队"""return self.pop(True)def pop_last(self) -> int:"""队尾出队"""return self.pop(False)def peek_first(self) -> int:"""访问队首元素"""return None if self.is_empty() else self.front.valdef peek_last(self) -> int:"""访问队尾元素"""return None if self.is_empty() else self.rear.valdef to_array(self) -> list[int]:"""返回数组用于打印"""node = self.frontres = [0] * self.size()for i in range(self.size()):res[i] = node.valnode = node.nextreturn res

Go:

/* 基于双向链表实现的双向队列 */
type linkedListDeque struct {// 使用内置包 listdata *list.List
}/* 初始化双端队列 */
func newLinkedListDeque() *linkedListDeque {return &linkedListDeque{data: list.New(),}
}/* 队首元素入队 */
func (s *linkedListDeque) pushFirst(value any) {s.data.PushFront(value)
}/* 队尾元素入队 */
func (s *linkedListDeque) pushLast(value any) {s.data.PushBack(value)
}/* 队首元素出队 */
func (s *linkedListDeque) popFirst() any {if s.isEmpty() {return nil}e := s.data.Front()s.data.Remove(e)return e.Value
}/* 队尾元素出队 */
func (s *linkedListDeque) popLast() any {if s.isEmpty() {return nil}e := s.data.Back()s.data.Remove(e)return e.Value
}/* 访问队首元素 */
func (s *linkedListDeque) peekFirst() any {if s.isEmpty() {return nil}e := s.data.Front()return e.Value
}/* 访问队尾元素 */
func (s *linkedListDeque) peekLast() any {if s.isEmpty() {return nil}e := s.data.Back()return e.Value
}/* 获取队列的长度 */
func (s *linkedListDeque) size() int {return s.data.Len()
}/* 判断队列是否为空 */
func (s *linkedListDeque) isEmpty() bool {return s.data.Len() == 0
}/* 获取 List 用于打印 */
func (s *linkedListDeque) toList() *list.List {return s.data
}

基于数组的实现

如下图所示,与基于数组实现队列类似,我们也可以使用环形数组来实现双向队列。

在队列的实现基础上,仅需增加“队首入队”和“队尾出队”的方法。

image-20230907170400394

image-20230907170416326

image-20230907170437411

image-20230907170458976

image-20230907170515436

Python:

class ArrayDeque:"""基于环形数组实现的双向队列"""def __init__(self, capacity: int):"""构造方法"""self.__nums: list[int] = [0] * capacityself.__front: int = 0self.__size: int = 0def capacity(self) -> int:"""获取双向队列的容量"""return len(self.__nums)def size(self) -> int:"""获取双向队列的长度"""return self.__sizedef is_empty(self) -> bool:"""判断双向队列是否为空"""return self.__size == 0def index(self, i: int) -> int:"""计算环形数组索引"""# 通过取余操作实现数组首尾相连# 当 i 越过数组尾部后,回到头部# 当 i 越过数组头部后,回到尾部return (i + self.capacity()) % self.capacity()def push_first(self, num: int):"""队首入队"""if self.__size == self.capacity():print("双向队列已满")return# 队首指针向左移动一位# 通过取余操作,实现 front 越过数组头部后回到尾部self.__front = self.index(self.__front - 1)# 将 num 添加至队首self.__nums[self.__front] = numself.__size += 1def push_last(self, num: int):"""队尾入队"""if self.__size == self.capacity():print("双向队列已满")return# 计算尾指针,指向队尾索引 + 1rear = self.index(self.__front + self.__size)# 将 num 添加至队尾self.__nums[rear] = numself.__size += 1def pop_first(self) -> int:"""队首出队"""num = self.peek_first()# 队首指针向后移动一位self.__front = self.index(self.__front + 1)self.__size -= 1return numdef pop_last(self) -> int:"""队尾出队"""num = self.peek_last()self.__size -= 1return numdef peek_first(self) -> int:"""访问队首元素"""if self.is_empty():raise IndexError("双向队列为空")return self.__nums[self.__front]def peek_last(self) -> int:"""访问队尾元素"""if self.is_empty():raise IndexError("双向队列为空")# 计算尾元素索引last = self.index(self.__front + self.__size - 1)return self.__nums[last]def to_array(self) -> list[int]:"""返回数组用于打印"""# 仅转换有效长度范围内的列表元素res = []for i in range(self.__size):res.append(self.__nums[self.index(self.__front + i)])return res

Go:

/* 基于环形数组实现的双向队列 */
type arrayDeque struct {nums        []int // 用于存储双向队列元素的数组front       int   // 队首指针,指向队首元素queSize     int   // 双向队列长度queCapacity int   // 队列容量(即最大容纳元素数量)
}/* 初始化队列 */
func newArrayDeque(queCapacity int) *arrayDeque {return &arrayDeque{nums:        make([]int, queCapacity),queCapacity: queCapacity,front:       0,queSize:     0,}
}/* 获取双向队列的长度 */
func (q *arrayDeque) size() int {return q.queSize
}/* 判断双向队列是否为空 */
func (q *arrayDeque) isEmpty() bool {return q.queSize == 0
}/* 计算环形数组索引 */
func (q *arrayDeque) index(i int) int {// 通过取余操作实现数组首尾相连// 当 i 越过数组尾部后,回到头部// 当 i 越过数组头部后,回到尾部return (i + q.queCapacity) % q.queCapacity
}/* 队首入队 */
func (q *arrayDeque) pushFirst(num int) {if q.queSize == q.queCapacity {fmt.Println("双向队列已满")return}// 队首指针向左移动一位// 通过取余操作,实现 front 越过数组头部后回到尾部q.front = q.index(q.front - 1)// 将 num 添加至队首q.nums[q.front] = numq.queSize++
}/* 队尾入队 */
func (q *arrayDeque) pushLast(num int) {if q.queSize == q.queCapacity {fmt.Println("双向队列已满")return}// 计算尾指针,指向队尾索引 + 1rear := q.index(q.front + q.queSize)// 将 num 添加至队首q.nums[rear] = numq.queSize++
}/* 队首出队 */
func (q *arrayDeque) popFirst() any {num := q.peekFirst()// 队首指针向后移动一位q.front = q.index(q.front + 1)q.queSize--return num
}/* 队尾出队 */
func (q *arrayDeque) popLast() any {num := q.peekLast()q.queSize--return num
}/* 访问队首元素 */
func (q *arrayDeque) peekFirst() any {if q.isEmpty() {return nil}return q.nums[q.front]
}/* 访问队尾元素 */
func (q *arrayDeque) peekLast() any {if q.isEmpty() {return nil}// 计算尾元素索引last := q.index(q.front + q.queSize - 1)return q.nums[last]
}/* 获取 Slice 用于打印 */
func (q *arrayDeque) toSlice() []int {// 仅转换有效长度范围内的列表元素res := make([]int, q.queSize)for i, j := 0, q.front; i < q.queSize; i++ {res[i] = q.nums[q.index(j)]j++}return res
}

双向队列应用

双向队列兼具栈与队列的逻辑,因此它可以实现这两者的所有应用场景,同时提供更高的自由度

我们知道,软件的“撤销”功能通常使用栈来实现:系统将每次更改操作 push 到栈中,然后通过 pop 实现撤销。然而,考虑到系统资源的限制,软件通常会限制撤销的步数(例如仅允许保存50步)。当栈的长度超过50时,软件需要在栈底(即队首)执行删除操作。但栈无法实现该功能,此时就需要使用双向队列来替代栈。请注意,“撤销”的核心逻辑仍然遵循栈的先入后出原则,只是双向队列能够更加灵活地实现一些额外逻辑。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/124405.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CVE-2017-12149

春秋云镜 CVE-2017-12149 JBoss反序列化漏洞 靶标介绍 2017年8月30日&#xff0c;厂商Redhat发布了一个JBOSSAS 5.x 的反序列化远程代码执行漏洞通告。该漏洞位于JBoss的HttpInvoker组件中的 ReadOnlyAccessFilter 过滤器中&#xff0c;其doFilter方法在没有进行任何安全检查…

算法通关村第十三关——溢出问题处理模板

前言 溢出问题是面试当中输出涉及到数字的一个需要特别注意的地方&#xff0c;典型的题目有三个&#xff1a;数字反转&#xff0c;将字符串转成数字和回文数。 1.整数反转 力扣7题&#xff0c;给你一个 32 位的有符号整数 x &#xff0c;返回将 x 中的数字部分反转后的结果。…

rk3399 linux 5.10 usb 2.0设备上电概率性注册失败

多次开关机&#xff0c;发现usb hub和4G都通信失败了&#xff0c;这就有点奇怪了&#xff0c;按理说usb驱动是没啥问题的 先查看usb log rootlinaro-alip:/# dmesg | grep usb [ 1.723797] usbcore: registered new interface driver usbfs [ 1.723828] usbcore: regis…

在很多公司里面会使用打tag的方式保留版本

&#xff1a;git tag|grep "xxx-dev“等分支来查看 2&#xff1a;git cherry-pick XXXXX 然后就是查看有冲突这些 git status 会出现相关的异常 然后解决相关的冲突 git add . git cherry-pick --continue git push XXX HEAD:refs/for/XXX 第一&#xff1a;git ta…

【LeetCode-中等题】17. 电话号码的字母组合

文章目录 题目方法一&#xff1a;递归回溯 题目 方法一&#xff1a;递归回溯 参考讲解&#xff1a;还得用回溯算法&#xff01;| LeetCode&#xff1a;17.电话号码的字母组合 首先可以画出树图&#xff1a; 先将数字对应的字符集合 加入到一个map集合 这里需要一个index来控…

伪静态web.config常见规则写法与参数介绍说明

伪静态web.config常见规则写法与参数介绍说明. 示例1&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <configuration><system.webServer><rewrite><rules><rule name"规则 1" stopProcessing"tru…

【AI理论学习】语言模型:从Word Embedding到ELMo

语言模型&#xff1a;从Word Embedding到ELMo ELMo原理Bi-LM总结参考资料 本文主要介绍一种建立在LSTM基础上的ELMo预训练模型。2013年的Word2Vec及2014年的GloVe的工作中&#xff0c;每个词对应一个vector&#xff0c;对于多义词无能为力。ELMo的工作对于此&#xff0c;提出了…

Go 接口和多态

在讲解具体的接口之前&#xff0c;先看如下问题。 使用面向对象的方式&#xff0c;设计一个加减的计算器 代码如下&#xff1a; package mainimport "fmt"//父类&#xff0c;这是结构体 type Operate struct {num1 intnum2 int }//加法子类&#xff0c;这是结构体…

MySQL——数据库以及数据表的创建

创建数据库 回到刚才创建数据库的问题&#xff0c;我们在创建数据库的时候可以通过添加一个参数&#xff0c;这个参数的意义在于当我们创建的数据库已经存在的时候则不会创建&#xff0c;也不会报错&#xff0c;如果不使用这个参数&#xff0c;则我们在重复创建一个已经存在的…

数据结构--- 树

(一)知识补充 定义 树是一种数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。​ 它具有以下的特点: 每个节点有零个或多个子节点; 没有父节点的节点称为根节点;每一个非根…

2023高教社杯 国赛数学建模E题思路 - 黄河水沙监测数据分析

1 赛题 E 题 黄河水沙监测数据分析 黄河是中华民族的母亲河。研究黄河水沙通量的变化规律对沿黄流域的环境治理、气候变 化和人民生活的影响&#xff0c; 以及对优化黄河流域水资源分配、协调人地关系、调水调沙、防洪减灾 等方面都具有重要的理论指导意义。 附件 1 给出了位…

vue2笔记

Vue笔记 视频: https://www.bilibili.com/video/BV1Zy4y1K7SH?p1 vue是渐进式JavaScript框架 用到什么功能&#xff0c;只需要引入什么功能模块 ; vue的特点:易用,灵活,高效; 组件化 , 一个vue文件包括了(html css js)声明式编程(不直接操作DOM) ;虚拟DOM diff算法(虚拟dom…

C# 基础面试题(万字)

1.选择题 1. 简述下面选项能够捕获运算溢出的异常类型的有 &#xff1f; A)Exception B)SystemException C)ArithmeticException D)OverflowException 试题回答&#xff1a;AD 2. 程序员可使用&#xff08;&#xff09;语句以程序方式引发异常 &#xff1f; A)run B)try C)th…

LAMP搭建WordPress

L linux A apache hhtpd M mysql/maridb P PHP1、 安装php yum -y install php php-fpm php-server php-mysql1.1、 启动php-fpm并自启 systemctl enable php-fpm --now[rootecs-1cee ~]# systemctl status php-fpm ● php-fpm.service - The PHP FastCGI Process ManagerLoa…

VR农学虚拟仿真情景实训教学演示

首先&#xff0c;VR农学虚拟仿真情景实训教学提供了更为真实的实践环境。传统的农学实训往往受制于时间、空间和资源的限制&#xff0c;学生只能通过观察或简单的模拟来学习农业知识和技能。而借助虚拟现实技术&#xff0c;学生可以进入虚拟农场&#xff0c;与各种农作物、工具…

【运维日常】infiniband网络架构,容器间跨机器不同网段通信

本站以分享各种运维经验和运维所需要的技能为主 《python零基础入门》&#xff1a;python零基础入门学习 《python运维脚本》&#xff1a; python运维脚本实践 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8…

PY32F003F18按键输入

一、PY32F003F18的GPIO介绍 1、PY32F003F18的18个I/O&#xff0c;均可作为外部中断&#xff1b; 2、每个GPIO都可以由软件配置为输出&#xff1a; 1)、推挽输出(push-pull) 2)、开漏极输出(open drain) 注意:驱动电流为8mA; 3、每个GPIO都可以由软件配置为输入&#xff1a; 1)、…

c语言初阶指针

目录 何为指针 地址大小 野指针 成因 如何规避 有效性 指针计算 -整数 ​编辑 指针比较运算 指针-指针 ​编辑 数组与指针关系 二级指针 指针数组 应用 何为指针 指针就是指针变量&#xff0c;用来存放内存空间的一个编号&#xff0c;将指针比作我们宾馆的客人&a…

前端 JS 经典:上传文件

重点&#xff1a;multipart/form-data 后端识别上传类型必填 1. form 表单上传 <!-- enctype"multipart/form-data" 这个必填 --> <form action"http://127.0.0.1:8080/users/avatar" method"post" enctype"multipart/form-data…

软件工程课件

软件工程 考点概述软件工程概述能力成度模型能力成熟度模型集成软件过程模型逆向工程![ ](https://img-blog.csdnimg.cn/425cea8190fb4c5ab2bf7be5e2ad990e.png) 考点概述 重点章节 软件工程概述 之前老版教程的&#xff0c;之前考过 能力成度模型 记忆 能力等级 和 特点 能力…