共享栈

根据书上描述，共享栈的特点是：两个栈顶，置放在数组两头，入栈迎面相向，相遇时栈满，看图示：

主要处理两步工作：
第一，栈空的标志。这里沿用前面的约定，左栈用-1，而右栈用MAXSIZE，也就是放在数组的最左右两端。
第二，判满。这里采用左栈+1=右栈表明栈满。

此外，还需要一个状态标志flag，让用户选择是哪一个栈进行操作。综合看过几本书的各自优点，进行记录

#include <iostream>
using namespace std;
#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef struct
{
    int data[MAXSIZE];
    int top[2];/*top[0]:左栈，top[1]：右栈*/
}*SeqStack,Stack;
void InitStack(SeqStack &S)/*初始化*/
{
    S->top[0]=-1;
    S->top[1]=MAXSIZE;
}
int PushStack(SeqStack &S,int e,int flag)/*入栈*/
{
    if(S->top[0]+1==S->top[1])/*栈满的判定*/
    {
        return ERROR;
    }
    switch(flag)/*检测标志flag*/
    {
        case 0: /*左栈*/            
            ++S->top[0];
            S->data[S->top[0]]=e;
            break;
        case 1: /*右栈*/
            --S->top[1];
            S->data[S->top[1]]=e;
            break;
        default:
            return ERROR;
    }
    return OK;
}
int PopStack(SeqStack &S,int &e,int flag)/*出栈*/
{
    if(S->top[0]==-1 || S->top[1]==MAXSIZE)/*栈空判定*/
        return ERROR;
    switch(flag)/*检测标志flag*/
    {
        case 0:/*左栈*/
            e=S->data[S->top[0]];
            --S->top[0];
            break;
        case 1:/*右栈*/
            e=S->data[S->top[1]];
            --S->top[1];
            break;
        default:
            return ERROR;
    }
    return OK;
}
int main(void)
{
       int e;
       SeqStack S=(SeqStack)malloc(sizeof(Stack));/*堆中分配*/
       InitStack(S);/*初始化*/
       PushStack(S,12,1);/*右入栈*/
       cout<<"S.top="<<S->top[1]<<endl;
       cout<<"S.top="<<S->top[0]<<endl;
       PushStack(S,10,0);/*左入栈*/
       cout<<"S.top="<<S->top[1]<<endl;
       cout<<"S.top="<<S->top[0]<<endl;
       PopStack(S,e,0);/*左出栈*/
       cout<<"S.top="<<S->top[1]<<endl;
       cout<<"S.top="<<S->top[0]<<endl;
       free(S);/*释放内存*/      
       return 0;
}

相关推荐