#include<stdio.h>
#include<stdlib.h>
#define initsize 5
#define len 2
typedef int Elemtype;
typedef struct
{
int bot[2],top[2];
Elemtype *V;
int m; //栈最大可容纳元素个数
}Dblstack;
int initstack(Dblstack &s)
{
Elemtype *arr = (Elemtype *)malloc(sizeof(Elemtype) * initsize);
s.V = arr; //arr是临时指针变量
s.m = initsize;
s.bot[0] = 0;
s.bot[0] = s.m - 1;
s.top[0] = 0;
s.top[1] = s.m - 1;
}
int stackEmty(Dblstack s)
{
if(s.bot[0] == s.top[0] && s.bot[1] == s.top[1])//栈顶和栈底在同一位置时,栈空
return 0;
return 1;
}
int stackFull(Dblstack s)
{
//左右两栈的栈顶在中间相遇,或左栈顶位置超出初始化空间最右侧,或右栈位置超出初始化空间最左侧
if(s.top[0] > s.m - 1 || s.top[1] < 0 || s.top[1] - s.top[0] <= -1)
return 1;
return 0;
}
void extendcapacity(Dblstack &s)
{
/*Elemtype *new_arr = (Elemtype *)malloc(sizeof(Elemtype) * (s.m + len));
int new_size = s.m + len;
int i,j;
for(i = s.bot[0];i<s.top[0];i++)
{
new_arr[i] = s.V[i];
}
int n = s.bot[1] - s.top[1];
for(j = new_size - 1,i = s.m - 1;j>new_size -1 - n;j--,i--)
{
new_arr[j] = s.V[i];
}
s.bot[1] = new_size - 1;
s.top[1] = s.bot[1] - n;
s.m = new_size; //这一步只能放在这个位置,不能往前放
Elemtype *old_arr = s.V;
s.V = new_arr; //此处就可以充分体现中间变量new_arr的作用,充当一个中间变量
free(old_arr);*/
Elemtype *new_arr = (Elemtype *)realloc(s.V,sizeof(Elemtype) * len);
int new_size = s.m + len;
int i,j;
int n = s.bot[1] - s.top[1];
for(j = new_size - 1,i = s.m - 1;j>new_size - 1 - n;j--,i--)
{
new_arr[j] = s.V[i];
}
s.bot[1] = new_size - 1;
s.top[1] = s.bot[1] - n;
s.m = new_size;
s.V = new_arr;
}
int pushLeft(Dblstack &s,Elemtype e)
{
if(stackFull(s) == 1)
{
extendcapacity(s);
}
s.V[s.top[0]] = e;
s.top[0]++;
return 0;
}
int pushRight(Dblstack &s,Elemtype e)
{
if(stackFull(s) == 1)
{
extendcapacity(s);
}
s.V[s.top[1]] = e;
s.top[1]--;
return 0;
}
int popLeft(Dblstack &s)
{
if(stackEmty(s) == 0)
{
exit(0);
}
Elemtype e = s.V[s.top[0]];
s.top[0]--;
return e;
}
int popRight(Dblstack &s)
{
if(stackEmty(s) == 0)
{
exit(0);
}
Elemtype e = s.V[s.top[1]];
s.top[1]++;
return e;
}
int printDblstack(Dblstack s)
{
for(int i=0;i<s.m;i++)
{
printf("|%d|\t",s.V[i]);
}
printf("\n");
}
int main()
{
Dblstack s;
initstack(s);
printf("入栈操作前栈内数据情况:\n\n");
printDblstack(s);
pushLeft(s,1);
pushLeft(s,2);
pushLeft(s,100);
pushRight(s,4);
pushRight(s,3);
printf("入栈完毕之后栈内的数据情况:\n\n");
printDblstack(s);
pushRight(s,101);
pushRight(s,102);
printf("栈扩容之后栈内数据存放情况:\n");
printDblstack(s);
return 0;
}