加入训练营有点晚，没跟上任务就开始有些偷懒没有真的认真开始，从第十天开始下决心认真完成每天任务还有博客记录学习过程。
栈与队列理论基础
首先是学习了栈和队列的理论基础，队列 先进先出，栈 先进后出。
栈 以底层容器完成其所有的工作，且对外接口统一，有.push,.pop等，不提供走访，不提供迭代器。
-
栈
本身是一种抽象的数据结构，它并不直接去处理元素的存储细节等具体事务。而是借助如前面提到的 vector、deque、list 等底层容器来实际完成这些基础工作。无论栈选择哪种底层容器（vector、deque 还是 list）来实现，它对使用者呈现出的操作接口都是统一的。 - 不提供走访
栈的设计初衷是遵循后进先出原则来管理数据，它不是为了让用户能够随意遍历其中的所有元素而存在的。
与数组（比如 vector，如果把它单纯作为数组看待）或者链表（list）等数据结构不同，这些数据结构通常会提供一些方式让用户可以逐个访问其中的每个元素，比如通过索引（对于数组）或者沿着指针（对于链表）去走访每个节点。但栈一般不提供这样的功能，因为走访元素的操作不符合栈的后进先出逻辑，而且可能会破坏栈数据结构的特性。如果允许随意走访，用户可能会在不遵循后进先出原则的情况下访问和操作元素，从而导致栈失去其原本应有的功能和数据结构的一致性。
- 不提供迭代器。
迭代器是一种用于遍历容器中元素的工具，很多容器（如 vector、list 等）都提供迭代器来方便用户按照一定顺序访问容器内的元素。
然而栈不提供迭代器，原因和不提供走访功能类似。栈重点在于实现后进先出的操作，如入栈、出栈等特定功能，而不是为了让用户能够像遍历数组或链表那样全面地去查看和处理其中的每个元素。提供迭代器可能会诱导用户去做一些不符合栈逻辑的操作，比如在迭代过程中随意插入或删除元素，这会破坏栈的后进先出特性以及整体的结构完整性。所以为了保持栈的纯粹性和特性，一般不提供迭代器。
232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
使用两个栈实现先入先出队列，关键点在于如何用后入先出的特性来实现先入先出的特性。
这点也很好理解，将输入序列倒序之后的先入先出即为后入先出，为了实现这个有以下代码：
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if (stOut.empty()) {
// 从stIn导入数据直到stIn为空
while(!stIn.empty()) {
stOut.push(stIn.top());//.top()获取栈顶元素但不移除
stIn.pop();//从栈顶移除
}
}
int result = stOut.top();
stOut.pop();
return result;
}
/** Get the front element. */
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;//直接使用已有定义的函数，避免资源浪费（也是为什么不用.top的原因？）
}
/** Returns whether the queue is empty. */
bool empty() {
return stIn.empty() && stOut.empty();
}
};225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
用两个队列实现一个后入先出（LIFO）的栈，队列的特点是先入先出，如何做到后入先出呢，这里的思路是将“先入”的队列先让他们去旁边等一等，也就是复制到另一个队列。具体代码如下：
class MyStack {
public:
queue<int> que1;
queue<int> que2; // 辅助队列，用来备份
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que1.size();
size--;
while (size--) { // 将que1 导入que2，但要留下最后一个元素
que2.push(que1.front());//.front() 获取队列1队首值，排入队列2
que1.pop();//将队首值移除
}
int result = que1.front(); // 留下的最后一个元素就是要返回的值（队尾）
que1.pop();
que1 = que2; // 再将que2赋值给que1
while (!que2.empty()) { // 清空que2
que2.pop();
}
return result;
}
/** Get the top element.
** Can not use back() directly.
*/
int top(){//操作与pop相同，区别在于保留了队尾元素，一起排入队列2
int size = que1.size();
size--;
while (size--){
// 将que1 导入que2，但要留下最后一个元素
que2.push(que1.front());
que1.pop();
}
int result = que1.front(); // 留下的最后一个元素就是要回返的值
que2.push(que1.front()); // 获取值后将最后一个元素也加入que2中，保持原本的结构不变
que1.pop();
que1 = que2; // 再将que2赋值给que1
while (!que2.empty()){
// 清空que2
que2.pop();
}
return result;
}
/** Returns whether the stack is empty. */
bool empty() {
return que1.empty();
}
};20. 有效的括号
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
卡尔：括号匹配是使用栈解决的经典问题。
这里有三种不匹配的情况：
-
第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
-
第二种情况，括号没有多余，但是 括号的类型没有匹配上。
-
第三种情况，字符串里右方向的括号多余了，所以不匹配。
卡尔制作的匹配动画如下：
动画看起来非常直观了，简要解释：将左括号依次填入栈，在遇到对应右括号时从栈中移除。
在代码具体实现过程中卡尔提到一个小技巧，就像动画展示的，遍历左括号时向栈中压入相应右括号，这样在匹配括号时，只用判断其是否与右括号相等。
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty();
}
};(题目中输入字符串只有括号所以相对较为简单，小菜鸡的我遇到含有别的字符的可能还是不会写)
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串
s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在
s上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
这题的解题思路：反复执行相邻重复项删除，实际上和20中的括号匹配思路相似，我们可以将字符串遍历压入栈中，首先比对其与前一位，也就是栈顶元素，是否相等，如相等，将栈顶移除，接下来比对下一位，如不相等，将其压入栈顶，直至字符串末尾。如动画所示：
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for (char s : S) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
string result = "";
while (!st.empty()) { // 将栈中元素放到result字符串汇总
result += st.top();
st.pop();
}
reverse (result.begin(), result.end()); // 此时字符串需要反转一下
return result;
}
};也可以直接将字符串作为栈。（个人理解：将字符串当作栈进行操作）
push_back和pop_back是 C++ 中string类用于处理字符串末尾字符的成员函数：
push_back：用于在字符串末尾添加一个字符，会使字符串长度增加 1，示例中可将指定字符添加到已有字符串末尾。
pop_back：用于移除字符串末尾的一个字符，会使字符串长度减 1，能将已有字符串的最后一个字符删除。
这两个函数在字符串的动态处理、类似栈操作等场景中较为常用。
class Solution {
public:
// 函数 removeDuplicates 用于从输入字符串S中移除相邻的重复字符
string removeDuplicates(string S) {
// 用于存储处理后的结果字符串
string result;
// 遍历输入字符串S中的每个字符
for (char s : S) {
// 如果结果字符串为空，或者当前字符与结果字符串的最后一个字符不相等
if (result.empty() || result.back()!= s) {
// 将当前字符添加到结果字符串中
result.push_back(s);
} else {
// 如果当前字符与结果字符串的最后一个字符相等，说明出现了相邻重复字符
// 则移除结果字符串的最后一个字符，以达到移除相邻重复字符的目的
result.pop_back();
}
}
// 返回处理后的结果字符串
return result;
}
};总结：
Day10题目相对比较简单，理解数据结构中栈和队列是重点。
标签：第十天,队列,随想录,pop,que1,push,字符串,empty From： https://blog.csdn.net/qq_53853175/article/details/143668367