void nipr(slink q)
{
	slink p=q->prior;
	cout<<"該棧為:";
	while(p!=q)
	{
		cout<<p->data;
		cout<<(char)32;
		p=p->prior;
	}
	cout<<kg;
}




slink inis()   
{
	slink p;
	p=(slink)malloc(sizeof(snode));
	if(!p) return NULL ;      
	p->prior=p->next=p;
	return p;
}

void prints(slink S)
{
	slink p;
	if(S->prior==S->next)
	{
		cout<<"空棧!"<<endl;
	}
	else
	{
		cout<<"該棧為:"<<endl;
		p=S->next;
		while(p!=S)
		{
			cout<<p->data;
			cout<<(char)32;
			p=p->next;
		}
	}
	cout<<kg;
}

void creats(slink &S)
{
	S=inis();
	slink p;
	cout<<"輸入任意字符,以 0 結束!"<<endl;
	cout<<"例如 :abc0 (中間也可以用空格!)"<<endl;
	cout<<"依次輸入:  ";
	while (true)
	{    
		p = (slink)malloc(sizeof(snode));
		if(!p) exit(0);
		cin>>p->data;
		if (p->data=='0')break;
		p->prior=S;
		p->next=S->next;
		S->next->prior=p;
		S->next=p;
	}
	cout<<"創建成功!"<<endl;
	prints(S);
}

void gettop(slink S,elemtypes &c)
{
	
	
	if(S->prior==S->next) 
		cout<<"棧空"<<endl;
	e=S->next->data;
}


void push(slink S,elemtypes c)
{
	slink p;
	p=(slink)malloc(sizeof(snode));
	p->data=c;
	p->prior=S;
	p->next=S->next;
	S->next->prior=p;
	S->next=p;
}


void push1(slink S,slink p)
{
	p->prior=S;
	p->next=S->next;
	S->next->prior=p;
	S->next=p;
}





void pop(slink S,elemtypes &c)
{
	slink p;
	p=S->next;
	c=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);	
}




void pop1(slink S)
{
	slink p;
	p=S->next;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);
}


status getes(slink S,int i,elemtypes &c)   
{     
	int j=1; 
	slink p=S->next;     
	while(p!=S&&j<i) 
	{	 
		p=p->next;  
		j++;   
	}
	if(p==S)   
		return 0;   
	c=p->data;
	return 1;   
}   


void destroys(slink &S)   
{                          
	slink q,p=S->next;  
	while(p!=S) 
	{
		q=p->next;   
		free(p);   
		p=q;   
	}   
    S->next=S->prior=S;
}  


void traverses(slink L,void (*visit)(elemtypes &c))   
{     
	slink p=S->next; 
	while(p!=S)   
	{   
		visit(p->data);   
		p=p->next;   
	}   
	
	prints(S);
}   

void uprs(elemtypes &c)
{
	c=c>='a'&&c<='z'?c-32:e;
	//cout<<(int)e<<(char)32;
}


void chas()
{	
	int b;
	cout<<"你想查找第幾個元素:"<<endl;
	cin>>b;
	s=getes(S,b,c);
	if(s)
	{ 
		cout<<"第"<<b<<"個元素是"<<c<<endl;
		prints(S);
	}
	else
	{
		cout<<"你要查找的數不存在!"<<endl;
		prints(S);
	}
	
}



int match()
{
	char c;
	elemtypes e;
	S=inis();
	cout<<"輸入任意字符,以 0 結束!"<<endl;
	cin>>c;
	while(c!='0')
	{
		if((c=='[')||(c=='(')||(c=='{'))
			push(S,c);
		else if(c==']')
		{
			pop(S,e);
			if(e!='[')
			return 0;
		}
		else if(c=='}')
		{
			pop(S,e);
			if(e!='{')
			return 0;
		}
		else if(c==')')
		{
			pop(S,e);
			if(e!='(')
			return 0;
		}
	   cin>>c;
	}
	if(S->prior==S->next)
		return 1;
	else 
		return 0;
}

void pipei()
{
	int s=match();
	if(s) cout<<"括號匹配 "<<endl;
	else  cout<<"不匹配 "<<endl;
	flag=1;
}





void charus(slink S)
{
	slink p;
	cout<< "輸入任意字符，以'0'結束!"<<endl;
	cout<<" 依次輸入: ";
	
	for(;;)
	{    
		p=(slink)malloc(sizeof(snode));
		cin>>p->data;
		if(p->data=='0')break;	
		push1(S,p);
	}
	prints(S);	
}


void shanchus(slink S)
{ 
	int n,i;
	cout<<"你想刪除的個數:"<<endl;
	cin>>n;
	for(i=0;i<n;i++)
		pop1(S);
	prints(S);
	
}

void hebing()
{
    slink S1;
	creats(S);
	creats(S1);
	slink p,q,r;
	r=S->prior;
	p=S1->next;
	q=S1->prior;
	p->prior=r;
	r->next=p;
	q->next=S;
	S->prior=q;
	prints(S);
}

int selects()
{
	int n;
	cout<<"   *********************************************************************** "<<endl;   
	cout<<"   *                         1.創建                                      * "<<endl;   
	cout<<"   *                         2.合并                                      * "<<endl;    
	cout<<"   *                         3.查找                                      * "<<endl; 
	cout<<"   *                         4.批量插入                                  * "<<endl;
	cout<<"   *                         5.批量刪除                                  * "<<endl;
	cout<<"   *                         6.逆序                                      * "<<endl;
	cout<<"   *                         7.遍歷(大小寫轉換)                          * "<<endl;
	cout<<"   *                         8.括號匹配                                  * "<<endl;
	cout<<"   *                         9.返回上一層                                * "<<endl;
	cout<<"   *                         0.退出                                      * "<<endl;
	cout<<"   *********************************************************************** "<<endl;       
	cout<<"                            選擇你想進行的操作:                            "<<endl;   
	cout<<"請選擇0~9!"<<endl;
	cin>>n;
	for(;;)
	{
		if(n<0||n>9)
		{
			cout<<"重選"<<endl;
			cin>>n;
		}
		else
			break;
	}
	return n;
	
}