网站建设实训报告模板,市场调研公司存在的意义,深圳网站建设软件开发公司,广州品牌设计网站建设文章目录 栈栈常用操作栈的实现基于链表的实现基于数组的实现 两种实现对比栈典型应用 队列队列常用操作队列实现基于链表的实现基于数组的实现 队列典型应用 双向队列双向队列常用操作双向队列实现基于双向链表的实现基于数组的实现 双向队列应用 栈
栈是一种遵循先入后出的逻… 文章目录 栈栈常用操作栈的实现基于链表的实现基于数组的实现 两种实现对比栈典型应用 队列队列常用操作队列实现基于链表的实现基于数组的实现 队列典型应用 双向队列双向队列常用操作双向队列实现基于双向链表的实现基于数组的实现 双向队列应用 栈
栈是一种遵循先入后出的逻辑的线性数据结构。如下图所示我们把堆叠元素的顶部称为“栈顶”底部称为“栈底”。将把元素添加到栈顶的操作叫做“入栈”删除栈顶元素的操作叫做“出栈”。 栈常用操作
栈的常用操作如下表所示具体的方法名需要根据所使用的编程语言来确定。在此我们以常见的 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) 0Go
/* 初始化栈 */
// 在 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栈的实现
栈遵循先入后出的原则因此我们只能在栈顶添加或删除元素。然而数组和链表都可以在任意位置添加和删除元素因此栈可以被视为一种受限制的数组或链表。
基于链表的实现
使用链表来实现栈时我们可以将链表的头节点视为栈顶尾节点视为栈底。
如下图所示对于入栈操作我们只需将元素插入链表头部这种节点插入方法被称为“头插法”。而对于出栈操作只需将头节点从链表中删除即可。 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 arrGo
/* 基于链表实现的栈 */
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)。 由于入栈的元素可能会源源不断地增加因此我们可以使用动态数组这样就无须自行处理数组扩容问题。
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.__stackGo
/* 基于数组实现的栈 */
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) 。
在链表实现中链表的扩容非常灵活不存在上述数组扩容时效率降低的问题。但是入栈操作需要初始化节点对象并修改指针因此效率相对较低。不过如果入栈元素本身就是节点对象那么可以省去初始化步骤从而提高效率。
综上所述当入栈与出栈操作的元素是基本数据类型时例如 int 或 double 我们可以得出以下结论。
基于数组实现的栈在触发扩容时效率会降低但由于扩容是低频操作因此平均效率更高。基于链表实现的栈可以提供更加稳定的效率表现。
空间效率
在初始化列表时系统会为列表分配“初始容量”该容量可能超过实际需求。并且扩容机制通常是按照特定倍率例如 2 倍进行扩容扩容后的容量也可能超出实际需求。因此基于数组实现的栈可能造成一定的空间浪费。
然而由于链表节点需要额外存储指针因此链表节点占用的空间相对较大。
综上我们不能简单地确定哪种实现更加节省内存需要针对具体情况进行分析。
栈典型应用
浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页浏览器就会将上一个网页执行入栈这样我们就可以通过后退操作回到上一页面。后退操作实际上是在执行出栈。如果要同时支持后退和前进那么需要两个栈来配合实现。程序内存管理。每次调用函数时系统都会在栈顶添加一个栈帧用于记录函数的上下文信息。在递归函数中向下递推阶段会不断执行入栈操作而向上回溯阶段则会执行出栈操作。
队列
队列是一种遵循先入先出规则的线性数据结构。顾名思义队列模拟了排队现象即新来的人不断加入队列的尾部而位于队列头部的人逐个离开。
如下图所示我们将队列的头部称为“队首”尾部称为“队尾”将把元素加入队尾的操作称为“入队”删除队首元素的操作称为“出队”。 队列常用操作 表 队列操作效率
方法名描述时间复杂度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) 0Go
/* 初始化队列 */
// 在 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队列实现
基于链表的实现
如下图所示我们可以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”规定队尾仅可添加节点队首仅可删除节点。 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 queueGo
/* 基于链表实现的队列 */
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) 。 你可能会发现一个问题在不断进行入队和出队的过程中front 和 rear 都在向右移动当它们到达数组尾部时就无法继续移动了。为解决此问题我们可以将数组视为首尾相接的“环形数组”。
对于环形数组我们需要让 front 或 rear 在越过数组尾部时直接回到数组头部继续遍历。这种周期性规律可以通过“取余操作”来实现代码如下所示。
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 resGo
/* 基于环形数组实现的队列 */
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]
}以上实现的队列仍然具有局限性即其长度不可变。然而这个问题不难解决我们可以将数组替换为动态数组从而引入扩容机制。
两种实现的对比结论与栈一致。
队列典型应用
淘宝订单。购物者下单后订单将加入队列中系统随后会根据顺序依次处理队列中的订单。在双十一期间短时间内会产生海量订单高并发成为工程师们需要重点攻克的问题。各类待办事项。任何需要实现“先来后到”功能的场景例如打印机的任务队列、餐厅的出餐队列等。队列在这些场景中可以有效地维护处理顺序。
双向队列
在队列中我们仅能在头部删除或在尾部添加元素。双向队列提供了更高的灵活性允许在头部和尾部执行元素的添加或删除操作。 双向队列常用操作
双向队列的常用操作如下表所示具体的方法名称需要根据所使用的编程语言来确定。 表 双向队列操作效率
方法名描述时间复杂度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) 0Go
/* 初始化双向队列 */
// 在 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双向队列实现
双向队列的实现与队列类似可以选择链表或数组作为底层数据结构。
基于双向链表的实现
采用“双向链表”作为双向队列的底层数据结构。如下图所示我们将双向链表的头节点和尾节点视为双向队列的队首和队尾同时实现在两端添加和删除节点的功能。 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 resGo
/* 基于双向链表实现的双向队列 */
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
}基于数组的实现
如下图所示与基于数组实现队列类似我们也可以使用环形数组来实现双向队列。
在队列的实现基础上仅需增加“队首入队”和“队尾出队”的方法。 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 resGo
/* 基于环形数组实现的双向队列 */
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时软件需要在栈底即队首执行删除操作。但栈无法实现该功能此时就需要使用双向队列来替代栈。请注意“撤销”的核心逻辑仍然遵循栈的先入后出原则只是双向队列能够更加灵活地实现一些额外逻辑。
相关文章：
