网站开发项目计划书ppt,新媒体营销策略,国外做电商网站,个人网站毕业设计论文栈
栈 #xff08;stack#xff09;是一种遵循先入后出逻辑的线性数据结构 把堆叠元素的顶部称为“栈顶”#xff0c;底部称为“栈底”。 将把元素添加到栈顶的操作叫作“入栈”#xff0c;删除栈顶元素的操作叫作“出栈”。
栈的常用操作 /* 初始化栈 */
stackintstack是一种遵循先入后出逻辑的线性数据结构 把堆叠元素的顶部称为“栈顶”底部称为“栈底”。 将把元素添加到栈顶的操作叫作“入栈”删除栈顶元素的操作叫作“出栈”。
栈的常用操作 /* 初始化栈 */
stackint stack;
/* 元素入栈 */
stack.push(1);
stack.push(3);
stack.push(2);
stack.push(5);
stack.push(4);
/* 访问栈顶元素 */
int top stack.top();
/* 元素出栈 */
stack.pop(); // 无返回值
/* 获取栈的长度 */
int size stack.size();
/* 判断是否为空 */
bool empty stack.empty();栈的实现
栈可以视为一种受限制的数组或链表只能在末尾添加和删除元素。
基于链表的实现
将链表的头节点视为栈顶尾节点视为栈底。 对于入栈操作只需将元素插入链表头部这种节点插入方法被称为“头插法”。而对于出栈操作只需将头节点从链表中删除即可。
/*** File: linkedlist_stack.cpp* Created Time: 2022-11-28* Author: qualifier1024 (2539244001qq.com)*/#include ../utils/common.hpp/* 基于链表实现的栈 */
class LinkedListStack {private:ListNode *stackTop; // 将头节点作为栈顶int stkSize; // 栈的长度public:LinkedListStack() {stackTop nullptr;stkSize 0;}~LinkedListStack() {// 遍历链表删除节点释放内存freeMemoryLinkedList(stackTop);}/* 获取栈的长度 */int size() {return stkSize;}/* 判断栈是否为空 */bool isEmpty() {return size() 0;}/* 入栈 */void push(int num) {ListNode *node new ListNode(num);node-next stackTop;stackTop node;stkSize;}/* 出栈 */int pop() {int num top();ListNode *tmp stackTop;stackTop stackTop-next;// 释放内存delete tmp;stkSize--;return num;}/* 访问栈顶元素 */int top() {if (isEmpty())throw out_of_range(栈为空);return stackTop-val;}/* 将 List 转化为 Array 并返回 */vectorint toVector() {ListNode *node stackTop;vectorint res(size());for (int i res.size() - 1; i 0; i--) {res[i] node-val;node node-next;}return res;}
};/* Driver Code */
int main() {/* 初始化栈 */LinkedListStack *stack new LinkedListStack();/* 元素入栈 */stack-push(1);stack-push(3);stack-push(2);stack-push(5);stack-push(4);cout 栈 stack ;printVector(stack-toVector());/* 访问栈顶元素 */int top stack-top();cout 栈顶元素 top top endl;/* 元素出栈 */top stack-pop();cout 出栈元素 pop top 出栈后 stack ;printVector(stack-toVector());/* 获取栈的长度 */int size stack-size();cout 栈的长度 size size endl;/* 判断是否为空 */bool empty stack-isEmpty();cout 栈是否为空 empty endl;// 释放内存delete stack;return 0;
}
基于数组的实现
以将数组的尾部作为栈顶入栈与出栈操作分别对应在数组尾部添加元素与删除元素时间复杂度都为 (1)。 由于入栈的元素可能会源源不断地增加因此可以使用动态数组这样就无须自行处理数组扩容问题。 /*** File: array_stack.cpp* Created Time: 2022-11-28* Author: qualifier1024 (2539244001qq.com)*/#include ../utils/common.hpp/* 基于数组实现的栈 */
class ArrayStack {private:vectorint stack;public:/* 获取栈的长度 */int size() {return stack.size();}/* 判断栈是否为空 */bool isEmpty() {return stack.size() 0;}/* 入栈 */void push(int num) {stack.push_back(num);}/* 出栈 */int pop() {int num top();stack.pop_back();return num;}/* 访问栈顶元素 */int top() {if (isEmpty())throw out_of_range(栈为空);return stack.back();}/* 返回 Vector */vectorint toVector() {return stack;}
};/* Driver Code */
int main() {/* 初始化栈 */ArrayStack *stack new ArrayStack();/* 元素入栈 */stack-push(1);stack-push(3);stack-push(2);stack-push(5);stack-push(4);cout 栈 stack ;printVector(stack-toVector());/* 访问栈顶元素 */int top stack-top();cout 栈顶元素 top top endl;/* 元素出栈 */top stack-pop();cout 出栈元素 pop top 出栈后 stack ;printVector(stack-toVector());/* 获取栈的长度 */int size stack-size();cout 栈的长度 size size endl;/* 判断是否为空 */bool empty stack-isEmpty();cout 栈是否为空 empty endl;// 释放内存delete stack;return 0;
}两种实现对比
支持操作 两种实现都支持栈定义中的各项操作。数组实现额外支持随机访问但这已超出了栈的定义范畴因此一般不会用到。
时间效率 在基于数组的实现中入栈和出栈操作都在预先分配好的连续内存中进行具有很好的缓存本地性因此效率较高。然而如果入栈时超出数组容量会触发扩容机制导致该次入栈操作的时间复杂度变为 () 。 在基于链表的实现中链表的扩容非常灵活不存在上述数组扩容时效率降低的问题。但是入栈操作需要初始化节点对象并修改指针因此效率相对较低。不过如果入栈元素本身就是节点对象那么可以省去初始化步骤从而提高效率。
综上所述当入栈与出栈操作的元素是基本数据类型时例如 int 或 double 我们可以得出以下结论。 1.基于数组实现的栈在触发扩容时效率会降低但由于扩容是低频操作因此平均效率更高。 2.基于链表实现的栈可以提供更加稳定的效率表现。
空间效率 在初始化列表时系统会为列表分配“初始容量”该容量可能超出实际需求并且扩容机制通常是按照特定倍率例如 2 倍进行扩容的扩容后的容量也可能超出实际需求。 因此基于数组实现的栈可能造成一定的空间浪费。然而由于链表节点需要额外存储指针因此链表节点占用的空间相对较大。
栈的典型应用
浏览器中的后退与前进、软件中的撤销与反撤销。如果要同时支持后退和前进那么需要两个栈来配合实现。 程序内存管理。每次调用函数时系统都会在栈顶添加一个栈帧用于记录函数的上下文信息。在递归函数中向下递推阶段会不断执行入栈操作而向上回溯阶段则会不断执行出栈操作。
队列
队列 queue是一种遵循先入先出规则的线性数据结构。 将队列头部称为“队首”尾部称为“队尾”将把元素加入队尾的操作称为“入队”删除队首元素的操作称为“出队”。
队列的常用操作 /*** File: deque.cpp* Created Time: 2022-11-25* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* Driver Code */
int main() {/* 初始化双向队列 */dequeint deque;/* 元素入队 */deque.push_back(2);deque.push_back(5);deque.push_back(4);deque.push_front(3);deque.push_front(1);cout 双向队列 deque ;printDeque(deque);/* 访问元素 */int front deque.front();cout 队首元素 front front endl;int back deque.back();cout 队尾元素 back back endl;/* 元素出队 */deque.pop_front();cout 队首出队元素 popFront front 队首出队后 deque ;printDeque(deque);deque.pop_back();cout 队尾出队元素 popLast back 队尾出队后 deque ;printDeque(deque);/* 获取双向队列的长度 */int size deque.size();cout 双向队列长度 size size endl;/* 判断双向队列是否为空 */bool empty deque.empty();cout 双向队列是否为空 empty endl;return 0;
}队列实现
可以在一端添加元素并在另一端删除元素链表和数组都符合要求。
基于链表的实现
以将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”规定队尾仅可添加节点队首仅可删除节点。
/*** File: linkedlist_queue.cpp* Created Time: 2022-11-25* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* 基于链表实现的队列 */
class LinkedListQueue {private:ListNode *front, *rear; // 头节点 front 尾节点 rearint queSize;public:LinkedListQueue() {front nullptr;rear nullptr;queSize 0;}~LinkedListQueue() {// 遍历链表删除节点释放内存freeMemoryLinkedList(front);}/* 获取队列的长度 */int size() {return queSize;}/* 判断队列是否为空 */bool isEmpty() {return queSize 0;}/* 入队 */void push(int num) {// 在尾节点后添加 numListNode *node new ListNode(num);// 如果队列为空则令头、尾节点都指向该节点if (front nullptr) {front node;rear node;}// 如果队列不为空则将该节点添加到尾节点后else {rear-next node;rear node;}queSize;}/* 出队 */int pop() {int num peek();// 删除头节点ListNode *tmp front;front front-next;// 释放内存delete tmp;queSize--;return num;}/* 访问队首元素 */int peek() {if (size() 0)throw out_of_range(队列为空);return front-val;}/* 将链表转化为 Vector 并返回 */vectorint toVector() {ListNode *node front;vectorint res(size());for (int i 0; i res.size(); i) {res[i] node-val;node node-next;}return res;}
};/* Driver Code */
int main() {/* 初始化队列 */LinkedListQueue *queue new LinkedListQueue();/* 元素入队 */queue-push(1);queue-push(3);queue-push(2);queue-push(5);queue-push(4);cout 队列 queue ;printVector(queue-toVector());/* 访问队首元素 */int peek queue-peek();cout 队首元素 peek peek endl;/* 元素出队 */peek queue-pop();cout 出队元素 pop peek 出队后 queue ;printVector(queue-toVector());/* 获取队列的长度 */int size queue-size();cout 队列长度 size size endl;/* 判断队列是否为空 */bool empty queue-isEmpty();cout 队列是否为空 empty endl;// 释放内存delete queue;return 0;
}
基于数组的实现
在数组中删除首元素的时间复杂度为 () 这会导致出队操作效率较低。
可以采用以下巧妙方法来避免这个问题 使用一个变量 front 指向队首元素的索引并维护一个变量 size 用于记录队列长度。定义 rear front size 这个公式计算出的 rear 指向队尾元素之后的下一个位置。 基于此设计数组中包含元素的有效区间为 [front, rear - 1] 入队操作将输入元素赋值给 rear 索引处并将 size 增加 1 。 出队操作只需将 front 增加 1 并将 size 减少 1 。 这样可以看到入队和出队操作都只需进行一次操作时间复杂度均为 (1)。 但这样在不断进行入队和出队的过程中front 和 rear 都在向右移动当它们到达数组尾部时就无法继续移动了。为了解决此问题可以将数组视为首尾相接的“环形数组“。
/*** File: array_queue.cpp* Created Time: 2022-11-25* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* 基于环形数组实现的队列 */
class ArrayQueue {private:int *nums; // 用于存储队列元素的数组int front; // 队首指针指向队首元素int queSize; // 队列长度int queCapacity; // 队列容量public:ArrayQueue(int capacity) {// 初始化数组nums new int[capacity];queCapacity capacity;front queSize 0;}~ArrayQueue() {delete[] nums;}/* 获取队列的容量 */int capacity() {return queCapacity;}/* 获取队列的长度 */int size() {return queSize;}/* 判断队列是否为空 */bool isEmpty() {return size() 0;}/* 入队 */void push(int num) {if (queSize queCapacity) {cout 队列已满 endl;return;}// 计算队尾指针指向队尾索引 1// 通过取余操作实现 rear 越过数组尾部后回到头部int rear (front queSize) % queCapacity;// 将 num 添加至队尾nums[rear] num;queSize;}/* 出队 */int pop() {int num peek();// 队首指针向后移动一位若越过尾部则返回到数组头部front (front 1) % queCapacity;queSize--;return num;}/* 访问队首元素 */int peek() {if (isEmpty())throw out_of_range(队列为空);return nums[front];}/* 将数组转化为 Vector 并返回 */vectorint toVector() {// 仅转换有效长度范围内的列表元素vectorint arr(queSize);for (int i 0, j front; i queSize; i, j) {arr[i] nums[j % queCapacity];}return arr;}
};/* Driver Code */
int main() {/* 初始化队列 */int capacity 10;ArrayQueue *queue new ArrayQueue(capacity);/* 元素入队 */queue-push(1);queue-push(3);queue-push(2);queue-push(5);queue-push(4);cout 队列 queue ;printVector(queue-toVector());/* 访问队首元素 */int peek queue-peek();cout 队首元素 peek peek endl;/* 元素出队 */peek queue-pop();cout 出队元素 pop peek 出队后 queue ;printVector(queue-toVector());/* 获取队列的长度 */int size queue-size();cout 队列长度 size size endl;/* 判断队列是否为空 */bool empty queue-isEmpty();cout 队列是否为空 empty endl;/* 测试环形数组 */for (int i 0; i 10; i) {queue-push(i);queue-pop();cout 第 i 轮入队 出队后 queue ;printVector(queue-toVector());}// 释放内存delete queue;return 0;
}以上实现的队列仍然具有局限性其长度不可变。然而这个问题不难解决可以将数组替换为动态数组从而引入扩容机制。
队列典型应用
订单。购物者下单后订单将加入队列中系统随后会根据顺序处理队列中的订单。在双十一期间短时间内会产生海量订单高并发成为工程师们需要重点攻克的问题。 各类待办事项。任何需要实现“先来后到”功能的场景例如打印机的任务队列、餐厅的出餐队列等队列在这些场景中可以有效地维护处理顺序。
双向队列
双向队列double‑ended queue允许在头部和尾部执行元素的添加或删除操作
双向队列常用操作 /*** File: deque.cpp* Created Time: 2022-11-25* Author: Krahets (krahets163.com)*/#include ../utils/common.hpp/* Driver Code */
int main() {/* 初始化双向队列 */dequeint deque;/* 元素入队 */deque.push_back(2);deque.push_back(5);deque.push_back(4);deque.push_front(3);deque.push_front(1);cout 双向队列 deque ;printDeque(deque);/* 访问元素 */int front deque.front();cout 队首元素 front front endl;int back deque.back();cout 队尾元素 back back endl;/* 元素出队 */deque.pop_front();cout 队首出队元素 popFront front 队首出队后 deque ;printDeque(deque);deque.pop_back();cout 队尾出队元素 popLast back 队尾出队后 deque ;printDeque(deque);/* 获取双向队列的长度 */int size deque.size();cout 双向队列长度 size size endl;/* 判断双向队列是否为空 */bool empty deque.empty();cout 双向队列是否为空 empty endl;return 0;
}双向队列实现
基于双向链表的实现
们将双向链表的头节点和尾节点视为双向队列的队首和队尾同时实现在两端添加和删除节点的功能。
基于数组的实现
可以使用环形数组来实现双向队列。
双向队列应用
双向队列兼具栈与队列的逻辑因此它可以实现这两者的所有应用场景同时提供更高的自由度。 软件的“撤销”功能通常使用栈来实现系统将每次更改操作 push 到栈中然后通过 pop 实现撤销。然而考虑到系统资源的限制软件通常会限制撤销的步数例如仅允许保存 50 步。当栈的长度超过50 时软件需要在栈底队首执行删除操作。但栈无法实现该功能此时就需要使用双向队列来替代栈。
学习地址https://github.com/krahets/hello-algo 重新复习数据结构所有的内容都来自这里。
