discuss3

Description

将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长（见下图）。试编写双栈初始化，判断栈空、栈满、进栈和出栈算法的函数。函数调用次序依次为：进栈、栈满的判断、出栈、栈空的判断。

双栈数据结构的定义如下：

typedef struct

{

int top[2], bot[2]; //栈顶和栈底指针

SElemType *V; //栈数组

int m; //栈最大可容纳元素个数

}DblStack;

Input

多组数据，每组数据有四行，每行的数据之间均用空格分隔。第一行为一个整数m，表示数组V的大小，第二行为四个整数e0、e1、d0、d1，e0和e1分别代表压入0号栈和1号栈的整数序列E0和E1的长度（依次连续入栈，中间没有出栈的情况），d0和d1分别代表从0号栈和1号栈弹出的序列的长度（依次连续出栈，中间没有入栈的情况）。第三行和第四行分别表示序列E0和E1。当m=0时，输入结束。

Output

对于每组数据输出三行。第一行代表进栈操作完成时栈是否为满（出栈操作尚未执行），栈满输出1，栈不满输出0。第二行和第三行的数据分别对应0号栈和1号栈。第二行包括d0+1个整数，其中前d0个整数代表出栈序列D0，最后一个整数代表出栈操作完成时0号栈是否为空，栈空输出0，不空输出1。第三行包括d1+1个整数，其中前d1个整数代表出栈序列D1，最后一个整数代表出栈操作完成时1号栈是否为空，栈空输出0，不空输出1。整数之间用空格分隔。

Sample Input Copy

7
3 4 2 2
1 2 3
2 3 4 5
12
4 6 4 3
1 3 4 5
1 3 5 6 8 1
0

Sample Output Copy

HINT

		#include<iostream>
	
		using namespace std;
	
		typedef struct
	
		{
	
		    int top[2],bot[2];//栈顶和栈底指针
	
		    int *V;//栈数组
	
		    int m;//栈最大可容纳元素个数
	
		}DblStack;
	
		void InitDblStack(DblStack &S,int m)
	
		{//初始化一个大小为m的双向栈
	
		    S.V=new int[m];            //动态分配一个最大容量为m的数组空间
	
		    S.bot[0]=-1;               //左栈栈底指针
	
		    S.bot[1]=m;                //右栈栈底指针
	
		    S.top[0]=-1;               //左栈栈顶指针
	
		    S.top[1]=m;               //右栈栈顶指针
	
		}
	
		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;
	
		}
	
		void Push(DblStack &S,int i)
	
		{//向指定的i号栈中插入元素x，先移动指针再入栈
	
		    /**************begin************/
	
		    /**************end************/
	
		}
	
		void Pop(DblStack &S,int i)
	
		{//删除指定的i号栈的栈顶元素，先出栈再移动指针
	
		    /**************begin************/
	
		    /**************end************/
	
		}
	
		int main()
	
		{
	
		    DblStack S;
	
		    int m,e0,e1,d0,d1;
	
		    while(cin>>m)
	
		    {
	
		        if(m==0) break;
	
		        InitDblStack(S,m);
	
		        cin>>e0>>e1>>d0>>d1;
	
		        while(e0--)
	
		            Push(S,0);
	
		        while(e1--)
	
		            Push(S,1);
	
		        cout<<IsFull(S)<<endl;
	
		        while(d0--)
	
		            Pop(S,0);
	
		        cout<<!IsEmpty(S,0)<<endl;
	
		        while(d1--)
	
		            Pop(S,1);
	
		        cout<<!IsEmpty(S,1)<<endl;
	
		    }
	
		    return 0;
	
		}

Source/Category

数据结构课程