思想：先开辟一段连续的存储空间（一个数组）；两个栈栈顶分别指向数组的两端，随着push操作两栈的栈顶向数组内侧移动；随着pop操作两栈的栈顶向数组外侧移动。
 

 
 
 
#include <stdio.h>
#include <stdlib.h>
//栈的顺序存储结构，用一维数组实现


#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
typedef int ElemType;


//用一个数组来存储两个栈；思想是两个栈的栈顶分别在数组的两端
typedef struct{
    ElemType data[MAXSIZE];
    int top1;//栈1的栈顶
    int top2;//栈2的栈顶
}DoubleStack;
//1. 初始化操作
Status InitDS(DoubleStack *DS){
    memset(DS->data,'\0',sizeof(ElemType)*MAXSIZE);/*注意memset是以字节来置数的，置零时不必考虑这么多，但置其他数时必须考虑基本元素的数据类型*/
    DS->top1=-1;
    DS->top2=MAXSIZE;
    return OK;
}


//2. 对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数
Status DoublePush(DoubleStack *DS,ElemType e,int s_number){
    if(DS->top1+1==DS->top2){
        //当两个栈顶重合时，数组已经满了
        return ERROR;
    }
    if(s_number==1){
        //往栈1插入元素
        ++(DS->top1);
        DS->data[DS->top1]=e;
    }else if(s_number==2){
        --(DS->top2);
        DS->data[DS->top2]=e;
    }
    return OK;
}
//两栈共享空间的pop方法
Status DoublePop(DoubleStack *DS,ElemType *e,int s_number){
    if(DS->top1==-1 && DS->top2==MAXSIZE){
        printf("两栈均为空！，不能执行此项操作！");
        return ERROR;
    }else if(DS->top1==-1){
        //栈1为空，只能对2进行弹栈
        if(s_number!=2){
            printf("此时栈1为空，栈的标号必须为2!\n");
            return ERROR;
        }
    }else if(DS->top2==MAXSIZE){
        if(s_number!=1){
            printf("此时栈2为空，栈的标号必须为1!\n");
            return ERROR;
        }
    }
    if(1==s_number){
        *e=DS->data[DS->top1];
        --DS->top1;
    }else if(2==s_number){
        *e=DS->data[DS->top2];
        ++DS->top2;
    }else{
        printf("请检查输入的栈号，必须为1或2\n");
        return ERROR;
    }
    return OK;
}
int main()
{
    
    DoubleStack DS;
    if(OK==InitDS(&DS)){
        printf("初始化成功！");
    }
    int e,s_number;
    printf("想要插入的值及栈号\n");
    while(2==scanf("%d,%d",&e,&s_number)){
            if(OK==DoublePush(&DS,e,s_number)){
                int i,j;
                i=0;
                j=MAXSIZE-1;
                printf("栈1的元素为：");
                while(i<=DS.top1){
                    printf("%d\t",DS.data[i++]);
                }
                printf("\n栈2的元素为：");
                while(j>=DS.top2){
                    printf("%d\t",DS.data[j--]);
                }
            }


    }
    printf("输入出栈的栈号\n");
    while(1==scanf("%d",&s_number)){
        printf("出栈的值为：");
        if(OK==DoublePop(&DS,&e,s_number))
            printf("%d\t",e);
    }


    return 0;
}

 

 
 
#include <iostream>
using namespace std;

const int StackSize = 100;

class BothStack
{

private:
    int data[StackSize];  ///存放两个栈的数组
    int top1, top2; ///两个栈的栈顶指针，分别为各自栈顶元素在数组中的下标

public:
    BothStack() {
        top1 = -1;
        top2 = StackSize;
    }  ///构造函数，将两个栈分别初始化
    ~BothStack() {} ///析构函数为空
    void Push(int i, int x); //入栈操作，将元素x压入栈i
    int Pop(int i);  ///出栈操作，对栈i执行出栈操作）
    int Empty(int i) {
        if (top1 == -1 && top2 == StackSize)
            return 1;
        else
            return 0;
    }  ///判断栈是否为空

};

void BothStack::Push(int i, int x) ///入栈操作，将元素x入栈
{
    if (top1 == top2 - 1)  throw "上溢"; ///判断是否栈满
    if (i == 1)  data[++top1] = x; ///在栈1中插入
    if (i == 2)  data[--top2] = x; ///在栈2中插入
}

int BothStack::Pop(int i)  ///出栈操作，将栈顶元素弹出
{
    if (i == 1) { ///在栈1中删除
        if (top1 == -1) ///判断栈1是否为空
            throw "下溢";
        return data[top1--];
    }
    if (i == 2) { ///在栈2中删除
        if (top2 == StackSize) ///判断栈2是否为空
            throw "下溢";
        return data[top2++];
    }
}

int main()
{
	BothStack B;
	B.Push(1,1);
	B.Push(2,2);
	B.Push(1,3);
	B.Push(2,4);
	cout << B.Pop(1) <<endl;
	cout << B.Pop(1) <<endl;
	cout << B.Empty(1) <<endl;
    return 0;
}


 
 

 

 
文章目录
 
引言
实现之两栈共享空间
插入元素
删除元素
完整代码
   
  
 

 
引言
 
栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过栈有一个比较大的缺陷，就是必须事先确定数组存储空间的大小。万一不够用，就需要手动编程来扩展数组的容量，非常麻烦。对于一个栈，我们也尽可能考虑周全，设计出合适大小的数组来处理，单相对于两个相同类型的栈，我们却可以做到极大限度的利用其事先开辟的存储空间来进行操作。
 
打个比方，两个大学室友毕业同时到北京工作，开始时，他们觉得住了这么多年学校的集体宿舍，现在工作了-要有自己的私密空间。于是他们都希望租房时能找到独住的一居室，可找来找去却发现，最便宜的一居室也要每月1500 元，地段还不好，实在是承受不起，最终他俩还是合租了一套两居室，-一共2000元，各出一半，还不错。
 对于一个两居室，都有独立的卫生间和厨房，是私密了，但大部分空间的利用率却不高。而两居室，两个人各有卧室，还共享了客厅，厨房和卫生间，房间的利用率就显著提高，而且租房成本也下降了。
 
同样的道理，如果我们有两个相同类型的栈，我们为了他们各自开辟了数组空间，极有可能是第一个栈满了，在进栈就溢出了，而另外一个栈还有很多存储空间空闲，这时候我们可以用一个数组存储两个栈。
 
实现之两栈共享空间
 
数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的低端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处，这样，如果两个栈增加元素，就是两端点向中间延伸。
 其关键思路就是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要他们两不见面，两个栈就可以一直使用。
 栈1为空时，就是top1 = -1，top2等于n时，栈2就是空栈。
 
极端的情况：栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之栈1为空栈，top2等于0时，为栈2满。但是在更多的情况下，就是两个栈见面之时，也就是两个指针之间相差1，top1 +1 ==top2为栈满。
 
//两栈共享空间结构
typedef struct
{
	SElemType data[MAXSIZE];
	int top1;  //栈1栈顶指针
	int top2;	//栈2栈顶指针
}SqDoubleStack
 
插入元素
 
对于两栈共享空间的push方法，我们除了要插入元素值之外，还需要判断是栈1还是栈2的栈号参数。
 
/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
        if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
                return ERROR;	
        if (stackNumber==1)			/* 栈1有元素进栈 */
                S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
        else if (stackNumber==2)	/* 栈2有元素进栈 */
                S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */
        return OK;
}
 
删除元素
 
对于删除，就是判断栈1和栈2的stackNumber。
 
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{ 
        if (stackNumber==1) 
        {
                if (S->top1==-1) 
                        return ERROR; /* 说明栈1已经是空栈，溢出 */
                *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
        }
        else if (stackNumber==2)
        { 
                if (S->top2==MAXSIZE) 
                        return ERROR; /* 说明栈2已经是空栈，溢出 */
                *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
        }
        return OK;
}
 
事实上，使用这样的数据结构，通常就是当连个栈的空间需求有相反关系时，也就是一个栈增长是，另外一个栈在缩短的情况。
 
完整代码
 
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 

typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


/* 两栈共享空间结构 */
typedef struct 
{
        SElemType data[MAXSIZE];
        int top1;	/* 栈1栈顶指针 */
        int top2;	/* 栈2栈顶指针 */
}SqDoubleStack;


Status visit(SElemType c)
{
        printf("%d ",c);
        return OK;
}

/*  构造一个空栈S */
Status InitStack(SqDoubleStack *S)
{ 
        S->top1=-1;
        S->top2=MAXSIZE;
        return OK;
}

/* 把S置为空栈 */
Status ClearStack(SqDoubleStack *S)
{ 
        S->top1=-1;
        S->top2=MAXSIZE;
        return OK;
}

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */
Status StackEmpty(SqDoubleStack S)
{ 
        if (S.top1==-1 && S.top2==MAXSIZE)
                return TRUE;
        else
                return FALSE;
}

/* 返回S的元素个数，即栈的长度 */
int StackLength(SqDoubleStack S)
{ 
        return (S.top1+1)+(MAXSIZE-S.top2);
}

/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S,SElemType e,int stackNumber)
{
        if (S->top1+1==S->top2)	/* 栈已满，不能再push新元素了 */
                return ERROR;	
        if (stackNumber==1)			/* 栈1有元素进栈 */
                S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */
        else if (stackNumber==2)	/* 栈2有元素进栈 */
                S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */
        return OK;
}

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber)
{ 
        if (stackNumber==1) 
        {
                if (S->top1==-1) 
                        return ERROR; /* 说明栈1已经是空栈，溢出 */
                *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
        }
        else if (stackNumber==2)
        { 
                if (S->top2==MAXSIZE) 
                        return ERROR; /* 说明栈2已经是空栈，溢出 */
                *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
        }
        return OK;
}

Status StackTraverse(SqDoubleStack S)
{
        int i;
        i=0;
        while(i<=S.top1)
        {
                visit(S.data[i++]);
        }
        i=S.top2;
        while(i<MAXSIZE)
        {
                visit(S.data[i++]);
        }
        printf("\n");
        return OK;
}

int main()
{
        int j;
        SqDoubleStack s;
        int e;
        if(InitStack(&s)==OK)
        {
                for(j=1;j<=5;j++)
                        Push(&s,j,1);
                for(j=MAXSIZE;j>=MAXSIZE-2;j--)
                        Push(&s,j,2);
        }

        printf("栈中元素依次为：");
        StackTraverse(s);

        printf("当前栈中元素有：%d \n",StackLength(s));

        Pop(&s,&e,2);
        printf("弹出的栈顶元素 e=%d\n",e);
        printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));

        for(j=6;j<=MAXSIZE-2;j++)
                Push(&s,j,1);

        printf("栈中元素依次为：");
        StackTraverse(s);

        printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));

        
        ClearStack(&s);
        printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
        
        return 0;
}

一个数组实现两个栈，既然是一个数组变成两个栈，首先得把你的数组分成两部分，
 
这是一个十个元素的数组，有几种方法把他分成两部分呢？

这么分！
 
还是这么分！
 
或者这么分！
言归正传，其实分成两部分还是有两种分发的，第一种就是我上边画的第三种从中间开始分，将你的数组分成两个，分别成为一个栈。但是还有一种分发，是比较不容易想到的，那就是将你的数据的数据进行奇偶分开。
 
 
下标是红色的是一个栈，绿色的是另外一个栈。
 
上边的将数组从中间分开，也是有两种情况的
 
从中间分开，初始情况下top1和top2都是在中间值，然后从中间开始向两侧增长，
 
另一种情况是将top1赋值为数组第一个元素，top2是最后一个元素，从两侧开始往中间增长。
也就是说目前供我们选择的有三种方法，其实三种方法的实现难度大同小异，实质上区别也不大，但是最好的方法确是我最后介绍的，让数组从两侧开始往中间增长的。现在设想一下，你的数组初始大小为20也就是说你每个栈分到的大下是10个数据的空间，假如你现在要往其中一个栈中存入10000个数据，内存不够是不是需要扩展，你扩展必定是扩展整个数组，一个栈中放了10个数据，另一个放了10000个数据，会导致你的空间利用率比较低，但是第三种情况就很好的避免了这种情况，只有在你两个栈顶指针遇到的时候才会认为你的空间使用完了，进行空间扩容。
typedef struct SNode{
ElementType *Data;
Position Top1, Top2;
int MaxSize;
}*Stack;
先创建结构体，结构体中包含你的数组，以及两个栈的指针，还有你在动态分配的时候的数组的初始最大空间。
Stack CreateStack(int MaxSize)

{

 

Stack L = (Stack)malloc(sizeof(struct SNode));

L->Data = (ElementType*)malloc(sizeof(ElementType)*MaxSize);

L->Top1 = -1;

L->Top2 = MaxSize;

L->MaxSize = MaxSize;

return L;

}


创造结构体函数，给你的结构体分配空间以及初始化。
void Push(Stack S, ElementType X, int Tag){

if (S->Top1 == S->Top2 - 1){

printf("Stack Full\n");

return ;

}

if (Tag == 1)

S->Data[++S->Top1] = X;   

else

S->Data[--S->Top2] = X;

return ;

}


这是push函数，在push的时候，之前的push需要穿入栈，以及你要插入的值，这里需要再加入一个标志，来判断你是给你左边的栈插入元素，还是给右边的栈插入元素。
ElementType Pop(Stack S, int Tag){

if (Tag == 1){

if (S->Top1 == -1){

printf("Stack %d Empty\n", Tag);

return -1;

}

else

return S->Data[S->Top1--];

}

else if (S->Top2 == S->MaxSize){

printf("Stack %d Empty\n", Tag);

return -1;

}

else return S->Data[S->Top2++];

}


Pop也是同理，需要多传入一个标志参数，来判断你是想出哪个栈中的数据。
 
无论在哪个位置当你的S->Top1 == S->Top2 - 1的时候，就代表你的数组已经满了。
 
当你的数组扩充之后要将你的后边栈的数据全部搬到当前数组的最后部分。
 
void IncreaseArea(Stack S, int MaxSize)

{

ElementType N;

S->Top2 = MaxSize;

S->Data = (ElementType*)malloc(sizeof(ElementType)*MaxSize*2);

N = MaxSize * 2;

while (S->Top2 != S->Top1)

{

S->Data[N] = S->Data[S->Top2];

N--;

S->Top2--;

}

S->Top2 = N;

return;

}


分配好空间之后，将你的top2指向之前数组的最后边，也就是你后边栈的第一个元素位置，然后将N指向扩充后的最后位置。这时候一一对应将数据复制过去，然后将N和TOP2都往后移动。直到TOP2指向了最后一个元素。然后将top2指向当前栈的栈顶元素就结束了。