今天学习了栈和队列的两种实现方式
栈和队列是非常重要的两种数据结构,在软件设计中应用很多。
栈和队列实现回文的两种实现形式
include
include
using namespace std;
typedef struct {
char* base;
int front;
int rear;
}SqQueqe;
typedef struct {
char* base;
char* top;
int stacksize;
}SqStack;
//初始化栈
void initStack(SqStack& s) {
s.base = new char[101];
s.top = s.base;
s.stacksize = 101;
}
//进栈
int Push1(SqStack& s, char c) {
if (s.top - s.base == 101)
return 0;
*s.top++ = c;
return 1;
}
//出栈
int Pop1(SqStack& s, char& c) {
if (s.top == s.base)
return 0;
c = *--s.top;
return 1;
}
//初始化队列
void initQueqe(SqQueqe& q) {
q.base = new char[101];
q.front = q.rear = 0;
}
//进队
int Push2(SqQueqe& q, char c) {
if ((q.rear + 1) % 101 == q.front)
return 0;
q.base[q.rear] = c;
q.rear = (q.rear + 1) % 101;
return 1;
}
//出队
int Pop2(SqQueqe& q, char& c) {
if (q.rear == q.front)
return 0;
c = q.base[q.front];
q.front = (q.front + 1) % 101;
return 1;
}
int main() {
string str;
getline(cin, str);
// for(int i=0;i<str.size();i++){
// if(str[i]==' '){
// str.erase(i,1);
// }
// }
//去掉字符串中的空格
int i = 0;
while (str[i] != '\0') {
if (str[i] == ' ') {
str.erase(i, 1);
i--;
}
i++;
}
char c1, c2;
int flag = 1;
//进栈
SqStack s;
initStack(s);
for (int i = 0; i < str.size(); i++) {
Push1(s, str[i]);
}
//进队列
SqQueqe q;
initQueqe(q);
for (int i = 0; i < str.size(); i++) {
Push2(q, str[i]);
}
for (int i = 0; i < str.size(); i++) {
Pop1(s, c1);
Pop2(q, c2);
if (c1 != c2) {
flag = 0;
break;
}
}
if (flag == 1)
cout << "此字符串是回文串" << endl;
else cout << "此字符串不是回文串" << endl;
return 0;
}