目录
第一题：2022年4月15日 星期五 晚上19：20 - 19：35
【算法思想】
两栈共享向量空间，将两栈栈底设在向量两端，初始时，左栈顶指针为-1，右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向增长，栈顶指针指向栈顶元素。左栈是通常意义下的栈，在进栈操作时，其栈顶指针右移(加1)，出栈时，栈顶指针左移(减1)。而右栈进栈操作时，其栈顶指针左移(减1)，出栈时，栈顶指针右移(加1)。
【算法描述】
typedef struct{
int top[2], bot[2]; //栈顶和栈底指针
ElemType* V; //栈数组
int m; //栈最大可容纳元素个数
}DblStack; //两栈类型
//1
Status InitDblStack(DblStack& S, int m)
{//初始化一个大小为m的双向栈s
S.V = new ElemType[m]; //动态分配一个最大容量为m的数组空间
S.bot[0] = -1; //左栈栈底指针
S.bot[1] = m; //右栈栈底指针
S.top[0] = -1; //左栈栈顶指针
S.top[1] = m; //右栈栈顶指针
return 0;
}
Status DblPush(DblStack S, int i,int x)
{//向指定的i号栈中插入元素x
if (S.top[i] - S.top[0] == 1)
{
return ERROR;
}
if (i == 0)
{
S.V[++S.top[0]] = x; //左栈；栈顶指针先加1，然后按照此地址进栈
}
else
{
S.V[--S.top[1]] = x; //左栈；栈顶指针先加1，然后按照此地址进栈
}
}
Status DblPop(DblStack& S, int i, ElemType& x)
{//删除指定的i号栈的栈顶元素，用x返回其值
if (S.top[i]==S.top[i]) //栈空
{
return ERROR;
}
if (i == 0)
{
x = S.V[S.top[0]--]; //左栈；栈顶指针减1
}
else
{
x = S.V[S.top[0]++]; //左栈；栈顶指针加1
}
return OK;
}
int IsEmpty(DblStack S, int i)
{//判断指定的i号栈是否为空，空返回1，否则返回0
return (S.top[i] == S.bot[i]);
}
int IsFull(DblStack S)
{//判断栈是否满，满则返回1，否则返回0
if (S.top[0] + 1 == S.top[1])
{
return 1;
}
else
{
return 0;
}
}
//测试
int main()
{
int m; //双向栈的元素个数
int i; //栈号
ElemType x; //元素
cout << "可以运行啊！nice啊！";
cout << endl;
DblStack S;
cout << "请输入双向栈的元素个数：";
cin >> m;
if (InitDblStack(S, m))
{
cout << "初始化成功！" << endl;
}
cout << "初始化栈" << endl;
cout << "向第几号栈添加元素：";
cin >> i;
for (int j = 0; j < m/2; j++)
{
cout << "将第" << j << "个元素入栈"<<i<<"中： ";
cin >> x;
DblPush(S, i, x);
}
cout << "删除第几号栈顶元素：";
cin >> i;
if (DblPop(S, i, x))
{
cout << "删除成功！";
}
else
{
cout << "删除失败！";
}
cout << "判断第几号栈是否为空：";
cin >> i;
if (IsEmpty(S,i))
{
cout << "栈为空！"<<endl;
}
else
{
cout << "栈不为空！"<<endl;
}
cout << "判断当前栈是否为满：";
if (IsFull(S))
{
cout << "栈已满！";
}
else
{
cout << "栈未满！";
}
cout << endl;
cout << "20213002624李季鸿代码";
system("pause");
return 1;
}
【算法思想】
将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再出栈一个元素与后一个字符比较，以此类推，直至栈空，在这种情况下可判定该字符序列是回文。如果出栈元素与串中的字符进行比较时出现不等的情况，则可判定该字符序列不是回文。
【算法描述】
int IsPalindrome(char* t)
{//判断t字符向量是否为回文，若是，返回1，否则返回0
int i;
char temp,e;
SqStack S;
InitStack(S);
int len = strlen(t); //求向量的长度
for ( i = 0; i < len / 2; i++)
{//将一半字符入栈
Push(S, t[i]);
}
if (len % 2 != 0)
{
i++; //长度为奇数，跳过中间字段
}
while (!StackEmpty(S))
{//每弹出一个字符与相应字符比较
temp = Pop(S,e);
if (temp != t[i])
{
return 0; //不等则返回0
}
else
{
i++;
}
}
return 1; //比较完毕均相等则返回1
}由于第三题实在没有含金量，就不写了。
【算法思想】
根据ai的值判断进行入栈或者出栈操作，入栈前首先判断是否栈满，出栈前先判断是否栈空，
随后再进行相关操作。
【算法描述】
（持续更新中。。。。。。）
