基础数据结构---栈

devtools/2024/12/23 1:48:14/

顺序表实现

一、栈类的声明

栈是一种特殊的线性表，可以由顺序表来实现，也可以由链表来实现，这节课，我们采用顺序表来实现栈。

#include <iostream>#include <stdexcept>using namespace std;template<typename T> // (1)class Stack { // (2)private:T *data; // (3)int size; // (4)int capacity; // (5)void resize(); // (6)public:Stack() : data(new T[10]), size(0), capacity(10) {} // (7)~Stack(); // (8)void push(T element); // (9)T pop(); // (10)T top() const; // (11)int getSize() const; // (12)};

(1) template<typename T> 这是一个模板声明，表明 Stack 类是一个通用的模板类，可以用于存储任何类型的元素 T。

(2) 这是 Stack 类的声明，它表示一个栈的数据结构。

(3) data 是一个私有成员变量，用于存储栈中的元素。它是一个指向类型为 T 的指针。

(4) size 是一个私有成员变量，用于记录栈中元素的数量。

(5) capacity 这是一个私有成员变量，用于记录栈的容量。

(6) resize() 是一个私有成员函数，用于在栈容量不足时进行扩容。

(7) Stack() 是构造函数，用于初始化栈的成员变量。它创建一个新的栈，并分配一个容量为 10 的数组来存储元素。

(8) ~Stack() 是析构函数，用于释放栈所占用的内存。

(9) void push(T element) 这是一个公共成员函数，用于将一个新元素压入栈顶。

(10) T pop() 是一个公共成员函数，用于从栈顶弹出一个元素。

(11) T top() 是一个公共成员函数，用于获取栈顶的元素，但不弹出它。

(12) int getSize() 是一个公共成员函数，用于获取栈中元素的数量。

二、栈的扩容

template<typename T>void Stack<T>::resize() { // (1)int newCapacity = capacity * 2; // (2)T *newData = new T[newCapacity]; // (3)for (int i = 0; i < size; i++) {newData[i] = data[i]; // (4)}delete[] data; // (5)data = newData; // (6)capacity = newCapacity; // (7)}

resize 函数用于在栈的容量不足时进行扩容操作。它创建了一个新的更大的数组，并将旧数组的元素复制到新数组中，然后更新栈的指针和容量。这样可以确保栈能够容纳更多的元素，而不会发生溢出。

(1) template<typename T> 是模板声明的一部分，表示 resize 函数是一个通用的模板函数，可以用于处理任何类型的元素 T。

(2) 这一行计算了新的容量，并将其赋值给 newCapacity 变量。新的容量是当前容量的两倍。

(3) 创建一个新的数组 newData，用于存储新扩容后的元素。新数组的大小为新的容量。

(4) 这是一个循环，用于将当前栈中的元素从旧数组 data 复制到新数组 newData 中。

(5) 释放了旧数组 data 所占用的内存空间。

(6) 将 newData 数组赋值给 data，使其成为栈的新存储数组。

(7) 更新了栈的容量为新的容量。

三、栈的销毁

template<typename T>Stack<T>::~Stack() { // (1)delete[] data; // (2)}

(1) 这是析构函数的声明，用于在对象销毁时执行清理操作。

(2) 释放了动态分配的数组 data 所占用的内存空间。delete[] 用于释放动态分配的数组内存。

四、入栈

template<typename T>void Stack<T>::push(T element) {if (size == capacity) { // (1)resize();}data[size++] = element; // (2)}

(1) 如果栈的当前大小 size 等于容量 capacity，则调用 resize 函数进行扩容操作。代表如果栈已满，需要先进行扩容以增加栈的容量。

(2) 将元素 element 赋值给栈数组 data 的 size 位置，并将 size 的值增加 1，以表示栈中元素的数量增加。

五、出栈

template<typename T>T Stack<T>::pop() {if (size == 0) {throw std::underflow_error("Stack is empty"); // (1)}return data[--size]; // (2)}

(1) 检查栈是否为空。如果栈为空（即 size 为 0），则抛出一个 std::underflow_error 异常，提示 "Stack is empty"。

(2) 如果栈不为空，通过 --size 减小栈的大小，并返回 data 数组中栈顶元素的值。

六、获取栈顶元素

template<typename T>T Stack<T>::top() const {if (size == 0) {throw std::underflow_error("Stack is empty");}return data[size - 1]; // (1)}

(1) 如果栈不为空，返回 data 数组中最后一个元素的值，即栈顶元素。

七、栈的完整源码

#include <iostream>
#include <stdexcept>using namespace std;template<typename T>
class Stack {
private:T* data;int size;int capacity;void resize();
public:Stack() : data(new T[10]), size(0), capacity(10) {}~Stack();void push(T element);T pop();T top() const;int getSize() const;
};template<typename T>
void Stack<T>::resize() {int newCapacity = capacity * 2;T* newData = new T[newCapacity];for (int i = 0; i < size; i++) {newData[i] = data[i];}delete[] data;data = newData;capacity = newCapacity;
}template<typename T>Stack<T>::~Stack() {delete[] data;
}template<typename T>void Stack<T>::push(T element) {if (size == capacity) {resize();}data[size++] = element;
}template<typename T>T Stack<T>::pop() {if (size == 0) {throw std::underflow_error("Stack is empty");}return data[--size];
}template<typename T>
T Stack<T>::top() const {if (size == 0) {throw std::underflow_error("Stack is empty");}return data[size - 1];
}template<typename T>
int Stack<T>::getSize() const {return size;
}int main() {Stack<int> st;st.push(4);st.push(7);st.push(13);cout << st.top() << endl;st.push(17);cout << st.top() << endl;st.pop();st.pop();cout << st.top() << endl;cout << st.getSize() << endl;return 0;}

C++链表实现

一、栈类的声明

栈是一种特殊的线性表，可以由顺序表来实现，也可以由链表来实现，这节课，我们采用链表来实现栈。

#include <iostream>
#include <stdexcept>using namespace std;
template<typename T> // (1)class Stack {
private:struct Node { // (2)T data;Node* next;Node(T d) : data(d), next(NULL) {}};Node* head; // (3)int size; // (4)
public:Stack() : head(NULL), size(0) {} // (5)~Stack(); // (6)void push(T element); // (7)T pop(); // (8)T top() const; // (9)int getSize() const; // (10)};

(1) 这是一个模板声明，表示这个类是一个通用的类模板，可以用于处理各种不同类型的元素。

(2)这是一个结构体定义，用于表示栈中的节点。每个节点包含一个数据成员 data 和一个指向下一个节点的指针 next。

(3) head 是一个私有成员变量，用于保存栈的头节点指针。

(4) size 是一个私有成员变量，用于保存栈的大小。

(5) Stack() 是构造函数，用于初始化栈。它将头节点指针设置为 NULL，并将栈的大小设置为 0。

(6) ~Stack() 是析构函数，用于释放栈中分配的内存。

(7) void push(T element) 是一个公共成员函数，用于将一个元素压入栈顶。它创建一个新的节点，并将元素赋值给节点的数据成员，然后将新节点插入到栈的头部。

(8) T pop() 是一个公共成员函数，用于从栈顶弹出一个元素。它检查栈是否为空，如果不为空，则删除栈顶节点，并返回节点的数据成员。

(9) T top() const 是一个公共成员函数，用于获取栈顶元素，但不弹出它。它检查栈是否为空，如果不为空，则返回栈顶节点的数据成员。

(10) int getSize() const 是一个公共成员函数，用于获取栈的大小。

二、栈的扩容

由链表实现栈时，每次如果是新生成的结点，则不涉及到像顺序表那样的扩容操作。

三、栈的销毁

template<typename T>Stack<T>::~Stack() { // (1)while (head != NULL) { // (2)Node* temp = head;head = head->next;delete temp;}
}

(1) 这是 Stack 类的析构函数的实现代码。它的作用是在对象销毁时，释放动态分配的节点内存。

(2) 不断循环访问栈中的元素，每次取出栈顶元素，存储到临时变量 temp 中，并且弹出栈顶，并且利用 delete 将弹出的元素进行内存释放，直到栈为空为止。

四、入栈

template<typename T>
void Stack<T>::push(T element) {Node* newNode = new Node(element); // （1）newNode->next = head; // （2）head = newNode; // （3）++size; // （4）
}

(1) 创建了一个新的 Node 对象，并将传入的元素赋值给该对象的数据成员。通过使用 new 操作符动态分配了内存来存储新的节点。

(2) 将新节点的 next 指针指向当前的头节点。这样，新节点就被添加到了栈的头部。

(3) 将头节点的指针更新为新节点，使新节点成为栈的新头部。

(4) 将栈的大小计数器加 1，以反映栈中元素数量的增加。

五、出栈

template<typename T>T Stack<T>::pop() {if (head == NULL) {throw std::underflow_error("Stack is empty"); // (1)}T result = head->data; // (2)Node* temp = head; // (3)head = head->next; // (4)delete temp; // (5)--size; // (6)return result; // (7)
}

(1) 如果头节点为空（即栈为空），则抛出一个 std::underflow_error 异常，提示 "Stack is empty"。

(2) 将头节点的数据成员赋值给 result 变量，准备返回弹出的元素。

(3) 将头节点的指针赋值给 temp 变量，用于后续删除头节点。

(4) 将头节点的 next 指针赋值给头节点本身，从而将头节点从链表中移除。

(5) 调用 delete 操作符释放 temp 所指向的节点内存。

(6) 将栈的大小计数器减 1，以反映弹出操作后栈中元素数量的减少。

(7) 返回弹出的元素，通过 result 变量传递返回值。

六、获取栈顶元素

template<typename T>T Stack<T>::top() const {if (head == NULL) {throw std::underflow_error("Stack is empty"); // (1)}return head->data; // (2)
}

(1) 如果栈为空，那么获取栈顶的这个操作是不合法的，抛出异常。

(2) 如果栈不为空，head 指针的 data 域，即栈顶元素。

七、栈的完整源码

#include <iostream>
#include <stdexcept>using namespace std;template<typename T>class Stack {
private:struct Node {T data;Node* next;Node(T d) : data(d), next(NULL) {}};Node* head;int size;
public:Stack() : head(NULL), size(0) {}~Stack();void push(T element);T pop();T top() const;int getSize() const;
};template<typename T>Stack<T>::~Stack() {while (head != NULL) {Node* temp = head;head = head->next;delete temp;}
}template<typename T>void Stack<T>::push(T element) {Node* newNode = new Node(element);newNode->next = head;head = newNode;++size;
}template<typename T>T Stack<T>::pop() {if (head == NULL) {throw std::underflow_error("Stack is empty");}T result = head->data;Node* temp = head;head = head->next;delete temp;--size;return result;
}template<typename T>T Stack<T>::top() const {if (head == NULL) {throw std::underflow_error("Stack is empty");}return head->data;
}template<typename T>int Stack<T>::getSize() const {return size;
}int main() {Stack<int> st;st.push(4);st.push(7);st.push(13);cout << st.top() << endl;st.push(17);cout << st.top() << endl;st.pop();st.pop();cout << st.top() << endl;cout << st.getSize() << endl;return 0;}

题集

1. 进制转换

2. Bitset

#include <iostream>
#include <bitset>
using namespace std;int main() {int n;// 循环读取输入直到文件结束while (cin >> n) {// 使用 bitset 将整数转换为二进制字符串// 因为 0 < n < 1000, 所以我们最多需要 10 位来表示 n 的二进制形式 (2^10 = 1024 > 1000)cout << bitset<10>(n).to_string().substr(10 - (int)log2(n) - 1) << endl;}return 0;
}

这段代码中，我们使用了bitset库，它可以方便地将整数转换为固定长度的二进制字符串。由于题目中指出0 < n < 1000，我们知道最大值999的二进制表示是1111100111，这需要10个二进制位来表示。所以我们创建了一个大小为10的bitset。

然而，当使用bitset<10>(n).to_string()时，它总是返回一个长度为10的字符串，即使对于较小的数字也是如此，比如1会被表示为0000000001。为了去除前导零，我们计算了数字n在二进制下的实际位数（即log2(n)+1），然后从结果字符串中切片得到正确的二进制表示。

需要注意的是，对于n=1的情况，log2(n)会给出0，所以我们对log2(n)的结果进行了类型转换并加1，确保我们不会尝试访问无效的索引。对于n=0的情况，题目已经说明不会出现，因此无需特别处理。

另外，如果想要更简单的实现，可以忽略bitset和log2，而使用循环方式构建二进制字符串，或者使用标准库中的std::stoi与std::string结合自定义逻辑去除前导零。

3. 图书整理 I

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:vector<int> reverseBookList(ListNode* head) {stack<int> stk;while (head) {stk.push(head->val);head = head->next; }vector<int> ans;while (!stk.empty()) {ans.push_back(stk.top());stk.pop();}return ans;}
};

4. 回文链表

class Solution {
public:bool isPalindrome(ListNode* head) {stack<int> stk;ListNode *temp = head; // 使用临时指针来遍历链表// 将所有节点值压入栈中while (temp) {stk.push(temp->val);temp = temp->next;}// 重置指针到链表头部，开始比较temp = head;while (temp) {if (stk.top() != temp->val) return false; // 如果栈顶元素和当前节点值不同，则不是回文stk.pop();temp = temp->next;}return true; // 所有节点值匹配，链表是回文}
};

暂时看看就好

使用双指针方法检查链表是否为回文，可以在O(n)时间复杂度和O(1)空间复杂度下完成。这种方法不需要额外的数据结构来存储节点值。以下是具体步骤：

1. **找到链表的中间节点**：使用快慢指针（Floyd's Cycle Detection Algorithm），慢指针每次移动一步，而快指针每次移动两步。当快指针到达链表末尾时，慢指针将位于链表的中间位置。

2. **反转链表的后半部分**：从中间节点开始，反转链表的后半部分。

3. **比较前后两部分**：将链表分为两部分，前半部分和反转后的后半部分，逐个比较两个部分对应的节点值是否相等。如果所有对应节点的值都相等，则链表是回文；否则不是。

4. **恢复链表（可选）**：如果需要保持链表的原始状态，可以再次反转链表的后半部分以恢复原状。

5. **返回结果**：根据比较的结果返回链表是否为回文。

下面是使用双指针方法实现的代码：

class Solution {
public:bool isPalindrome(ListNode* head) {if (!head || !head->next) return true;// Step 1: Find the middle of the linked list using slow and fast pointersListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// Step 2: Reverse the second half of the list starting from slowListNode *prev = nullptr, *curr = slow, *nextTemp;while (curr) {nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}// Step 3: Compare the first half and reversed second halfListNode *firstHalf = head, *secondHalf = prev;while (secondHalf) { // secondHalf will be shorter or equal in length to firstHalfif (firstHalf->val != secondHalf->val) return false;firstHalf = firstHalf->next;secondHalf = secondHalf->next;}// Step 4: Restore the list (optional)curr = prev; // prev now points to the new head of the reversed second halfprev = nullptr;while (curr) {nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return true;}
};

这段代码实现了上述的每个步骤，并且在最后可以选择性地恢复链表的原始顺序。通过这种方式，我们既能够有效地检查链表是否为回文，又能够在检查结束后保持链表的初始状态。

5. 括号的最大嵌套深度

class Solution {
public:int maxDepth(const std::string& inputString) {int stringLength = inputString.length(), maximumDepth = 0;for (int index = 0, currentDepth = 0; index < stringLength; index++) {if (inputString[index] == '(') currentDepth++;else if (inputString[index] == ')') currentDepth--;maximumDepth = std::max(maximumDepth, currentDepth);}return maximumDepth;}
};

6. 有效的括号

普通栈

剑指 Offer 06. 从尾到头打印链表

反转链表

括号的最大嵌套深度

有效的括号

最长有效括号

剑指 Offer II 027. 回文链表

回文链表

回文链表

棒球比赛

剑指 Offer II 036. 后缀表达式

比较含退格的字符

三合一

验证栈序列

剑指 Offer 31. 栈的压入、弹出序列

从先序遍历还原二叉树

单调栈

最小栈

栈的最小值

剑指 Offer 30. 包含min函数的栈

剑指 Offer II 038. 每日温度

用栈实现队列

剑指 Offer 09. 用两个栈实现队列

化栈为队

最后 K 个数的乘积

去除重复字母

不同字符的最小子序列

柱状图中最大的矩形

剑指 Offer II 039. 直方图最大矩形面积

最大矩形

剑指 Offer II 040. 矩阵中最大的矩形

接雨水

直方图的水量

最大子矩阵


http://www.ppmy.cn/devtools/144545.html

相关文章

Sentinel 学习笔记2- 概念与核心类介绍

Sentinel 学习笔记2- 概念与核心类介绍

本文属于sentinel学习笔记系列。网上看到吴就业老师的专栏&#xff0c;原文地址如下&#xff1a; https://blog.csdn.net/baidu_28523317/category_10400605.html 基本概念 basic-api-resource-rule | Sentinel 官网的基本概念介绍 资源 是 Sentinel 中的核心概念之一。最…
阅读更多...
第三章补充：拉格朗日乘子法（B站：中华科技大学-李柏坚）

第三章补充：拉格朗日乘子法（B站：中华科技大学-李柏坚）

原视频&#xff1a;28-9 拉格朗日乘数_哔哩哔哩_bilibili 我们现在来介绍一下拉格朗日乘子法的用途&#xff1a; 上图&#x1f446;是一个三维空间的曲面&#xff0c;我们现在给它一个限制条件&#xff0c;来求它的极值。 如上图&#x1f446;&#xff0c;假设曲面为&#xff…
阅读更多...
html+css网页设计 美食 爱美食1个页面

html+css网页设计 美食 爱美食1个页面

htmlcss网页设计 美食 爱美食1个页面 网页作品代码简单&#xff0c;可使用任意HTML辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源码 1&#xff0…
阅读更多...
文心一言对接FreeSWITCH实现大模型呼叫中心

文心一言对接FreeSWITCH实现大模型呼叫中心

文心一言对接FreeSWITCH实现大模型呼叫中心 作者&#xff1a;开源大模型智能呼叫中心FreeIPCC&#xff0c;Github&#xff1a;https://github.com/lihaiya/freeipcc 随着人工智能技术的快速发展&#xff0c;特别是大规模语言模型&#xff08;LLM&#xff09;的应用&#xff0…
阅读更多...
Qt之样式表使用（十一）

Qt之样式表使用（十一）

Qt开发 系列文章 - stylesheet&#xff08;十一&#xff09; 目录 前言 一、样式表stylesheet 二、代码更改 1.特定控件样式 ​编辑 2.类型选择器样式 3.ID选择器样式 三、UI上设计 四、qss文件设计 总结 前言 Qt是一个跨平台的C图形用户界面应用程序开发框架&#…
阅读更多...
【论文速读】| FirmRCA：面向 ARM 嵌入式固件的后模糊测试分析，并实现高效的基于事件的故障定位

【论文速读】| FirmRCA：面向 ARM 嵌入式固件的后模糊测试分析，并实现高效的基于事件的故障定位

基本信息 原文标题&#xff1a;FIRMRCA: Towards Post-Fuzzing Analysis on ARM Embedded Firmware with Efficient Event-based Fault Localization 原文作者&#xff1a;Boyu Chang, Binbin Zhao, Qiao Zhang, Peiyu Liu, Yuan Tian, Raheem Beyah, Shouling Ji 作者单位&…
阅读更多...
方正畅享全媒体新闻采编系统 reportCenter.do SQL注入漏洞复现

方正畅享全媒体新闻采编系统 reportCenter.do SQL注入漏洞复现

0x01 产品简介 方正畅享全媒体新闻生产系统是以内容资产为核心的智能化融合媒体业务平台，融合了报、网、端、微、自媒体分发平台等全渠道内容。该平台由协调指挥调度、数据资源聚合、融合生产、全渠道发布、智能传播分析、融合考核等多个平台组成，贯穿新闻生产策、采、编、发…
阅读更多...
游戏AI实现-寻路算法（Dijkstra）

游戏AI实现-寻路算法（Dijkstra）

戴克斯特拉算法&#xff08;英语&#xff1a;Dijkstras algorithm&#xff09;&#xff0c;又称迪杰斯特拉算法、Dijkstra算法&#xff0c;是由荷兰计算机科学家艾兹赫尔戴克斯特拉在1956年发现的算法。 算法过程&#xff1a; 1.首先设置开始节点的成本值为0&#xff0c;并将…
阅读更多...
最新文章

Copyright @ 2022~2023