代码随想录算法训练营第十天|232用栈实现队列、225用队列实现栈、20有效的括号、1047删除字符串中的所有相邻重复项
day10
1. 232用栈实现队列
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
// push(x) -- 将一个元素放入队列的尾部。
// pop() -- 从队列首部移除元素。
// peek() -- 返回队列首部的元素。
// empty() -- 返回队列是否为空。
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if (stOut.empty()) {
// 从stIn导入数据直到stIn为空
while(!stIn.empty()) {
stOut.push(stIn.top());
//top() 返回栈顶元素的引用，但不移除该元素。可以用来查看栈顶元素的值。
//pop() 从栈中移除栈顶元素，但不返回该元素的值。如果想使用或存储栈顶元素的值，需要在 pop() 之前调用 top()。
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
2. 225用队列实现栈
class MyStack {
public:
//这道题目用一个队列就够了。一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
queue<int> que;
MyStack() {
}
void push(int x) {// 将元素 x 压入栈顶。
que.push(x);
}
int pop() {
// 记录队列的大小
int size = que.size();
size--; // 需要移除栈顶元素，而将其他元素重新添加到队列尾部
// 循环将队列前面的元素（除最后一个以外）重新添加到队列尾部
while (size--) {
que.push(que.front()); // 将队列头部的元素添加到队尾
que.pop(); // 移除原队列头部的元素
}
// 现在队列中的最后一个元素是原栈的栈顶元素
int result = que.front(); // 获取当前队列头部的元素，它是“栈顶元素”
que.pop(); // 将该元素移除
return result; // 返回栈顶元素的值
}
int top() {
int size = que.size(); // 记录队列的当前大小
size--; // 栈顶元素是最后进入队列的元素，因此我们把前 size-1 个元素移到队列尾部
// 将前面的元素（除了最后一个元素外）移动到队列的尾部
while (size--) {
que.push(que.front()); // 将队列前端的元素添加到队列末尾
que.pop(); // 移除队列前端的元素
}
// 此时，队列头部元素就是栈顶元素
int result = que.front(); // 获得“栈顶”元素的值
que.push(que.front()); // 为了保持队列的顺序，将该元素重新加入到队列末尾
que.pop(); // 移除队列头部的元素
return result; // 返回该“栈顶”元素的值
}
bool empty() {//如果栈是空的，返回 true ；否则，返回 false 。
return que.empty(); // 直接返回队列是否为空
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
3. 20有效的括号
思路：
- 如果字符串长度为奇数，直接返回
false，因为成对的括号总会构成偶数长度的字符串。 - 遇到左括号时，将其压入栈中。
- 遇到右括号时，检查栈顶是否为对应的左括号；若匹配，弹出栈顶继续；不匹配则返回
false。 - 循环结束后，如果栈为空，返回
true；否则返回false。
class Solution {
public:
bool isValid(string s) {
stack<int> s1;
if(s.size()%2!=0){
return false;
}
for(int i=0;i<s.size();i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
s1.push(s[i]);
}
if(s[i]==')'||s[i]==']'||s[i]=='}'){
if(s1.empty()){
return false;
}
int result=s1.top();
if(s[i]==')'){
if(result!='('){
return false;
}
else{
s1.pop();
}
}
if(s[i]==']'){
if(result!='['){
return false;
}
else{
s1.pop();
}
}
if(s[i]=='}'){
if(result!='{'){
return false;
}
else{
s1.pop();
}
}
}
}
if(s1.empty()){
return true;
}
else{
return false;
}
}
};
4. 1047删除字符串中的所有相邻重复项
思路：
-
s1：用来存储字符，帮助判断和移除相邻的重复字符。 -
遍历
s，遇到重复字符时从栈中移除，确保栈中无相邻重复字符。 -
将栈中的字符加入
s2（顺序是反的），然后将s2反转。 -
返回结果字符串
s2。
class Solution {
public:
string removeDuplicates(string s) {
stack<int> s1;
string s2;
for(int i=0;i<s.size();i++){
if(s1.empty()){
s1.push(s[i]);
}
else{
int result=s1.top();
if(s[i]==result){
s1.pop();
}
else{
s1.push(s[i]);
}
}
}
while(!s1.empty()){
int j=s1.top();
s2.push_back(j);
s1.pop();
}
int l=0,r=s2.size()-1;
while(l<r){
swap(s2[l++],s2[r--]);
}
return s2;
}
};