数据结构栈和队列的应用

在昨天分享了有关栈和队列的基础知识和基本操作后，今天来分享一些有关栈和队列的应用

栈和队列的应用

删除字符串中的所有相邻重复项

#include <iostream>
#include <stack>
using namespace std;
string remove(string S)
{stack<char> charStack;for (int i = 0; i < S.length(); ++i){char c=S[i];if (!charStack.empty() && charStack.top() == c){charStack.pop();}else{charStack.push(c);}}string result;while (!charStack.empty()){result = charStack.top() + result;charStack.pop();}return result;
}
int main()
{string in;cin >> in;string result = remove(in);cout<<result;return 0;
}

括号匹配问题(类比20.LeetCode 有效的括号）

#include <iostream>
#include <stack>
#include <string>using namespace std;bool match(string input)
{stack<char> s;for (int i = 0; i < input.length(); i++){char bracket = input[i];if (bracket == '(' || bracket == '{' || bracket == '['){s.push(bracket);}else if (bracket == ')' || bracket == '}' || bracket == ']'){if (s.empty()){return false;}char top = s.top();s.pop();if ((bracket == ')' && top != '(') || (bracket == '}' && top != '{') || (bracket == ']' && top != '[')){return false;}}}return s.empty();
}int main()
{string input;cin >> input;if (match(input)){cout << "yes" << endl;}else{cout << "no" << endl;}return 0;
}

计算后缀表达式

#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <cstdlib>using namespace std;int customAtoi(const string &str)
{int result = 0;int sign = 1;size_t i = 0;if (str[0] == '-'){sign = -1;i = 1;}for (; i < str.length(); i++){if (isdigit(str[i])){result = result * 10 + (str[i] - '0');}else{cerr << "Error: Invalid character in input: " << str[i] << endl;std::exit(1);}}return result * sign;
}bool isOperator(const string &token)
{return (token == "+" || token == "-" || token == "*");
}int evaluatePostfixExpression()
{stack<int> operands;string token;while (cin >> token){if (token == "#"){break;}if (!isOperator(token)){operands.push(customAtoi(token));}else{int operand2 = operands.top();operands.pop();int operand1 = operands.top();operands.pop();int result;if (token == "+"){result = operand1 + operand2;}else if (token == "-"){result = operand1 - operand2;}else if (token == "*"){result = operand1 * operand2;}operands.push(result);}}if (!operands.empty()){return operands.top();}cerr << "Error: Invalid expression." << endl;std::exit(1);
}int main()
{int result = evaluatePostfixExpression();cout << result << endl;return 0;
}

表达式求值

#include <iostream>
#include <stack>
#include <string>
#include <cctype>using namespace std;int precedence(char op)
{if (op == '+' || op == '-'){return 1;}else if (op == '*' || op == '/'){return 2;}return 0;
}int evaluateExpression(const string &expression)
{stack<int> values;stack<char> operators;for (size_t i = 0; i < expression.length(); i++){if (isspace(expression[i])){continue;}else if (isdigit(expression[i])){int num = 0;while (i < expression.length() && isdigit(expression[i])){num = num * 10 + (expression[i] - '0');i++;}i--;values.push(num);}else if (expression[i] == '('){operators.push(expression[i]);}else if (expression[i] == ')'){while (!operators.empty() && operators.top() != '('){char op = operators.top();operators.pop();int operand2 = values.top();values.pop();int operand1 = values.top();values.pop();if (op == '+'){values.push(operand1 + operand2);}else if (op == '-'){values.push(operand1 - operand2);}else if (op == '*'){values.push(operand1 * operand2);}else if (op == '/'){values.push(operand1 / operand2);}}operators.pop(); }else if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || expression[i] == '/'){while (!operators.empty() && operators.top() != '(' && precedence(operators.top()) >= precedence(expression[i])){char op = operators.top();operators.pop();int operand2 = values.top();values.pop();int operand1 = values.top();values.pop();if (op == '+'){values.push(operand1 + operand2);}else if (op == '-'){values.push(operand1 - operand2);}else if (op == '*'){values.push(operand1 * operand2);}else if (op == '/'){values.push(operand1 / operand2);}}operators.push(expression[i]);}}while (!operators.empty()){char op = operators.top();operators.pop();int operand2 = values.top();values.pop();int operand1 = values.top();values.pop();if (op == '+'){values.push(operand1 + operand2);}else if (op == '-'){values.push(operand1 - operand2);}else if (op == '*'){values.push(operand1 * operand2);}else if (op == '/'){values.push(operand1 / operand2);}}return values.top();
}int main()
{string expression;getline(cin, expression);int result = evaluateExpression(expression);cout << result << endl;return 0;
}

回文链表

#include <bits/stdc++.h>
using namespace std;
struct Node
{int data;Node *next;
};
void createList(Node *&h,int n)
{Node *p,*r;h=new Node;h->next=NULL;r=h;for(int i=1; i<=n; i++){p=new Node;cin>>p->data;r->next=p;r=p;}r->next=NULL;
}
void printList(Node *h)
{Node *p;p=h->next;while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;
}bool isPalindrome(Node *head)
{if (!head || !head->next){return true;}Node *slow = head;Node *fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}Node *prev = NULL;Node *curr = slow;while (curr){Node *next = curr->next;curr->next = prev;prev = curr;curr = next;}Node *left = head->next;Node *right = prev;while (left && right){if (left->data != right->data){return false;}left = left->next;right = right->next;}return true;
}int main()
{int n;Node *h;cin>>n;createList(h,n);cout<<(isPalindrome(h)?"yes":"no");return 0;
}