双栈

你的名字 2022-06-16 12:17 80阅读 0赞

双栈意思就是双向栈，基本思想就是在一段内存里面，栈从两边分别向中间生长，这样可以提高内存的利用率。下面是C的实现代码，仅仅是基本的功能，重在于思想。

#include <stdio.h>
    #include <stdlib.h>
    
    #define INIT_STACK_SIZE 100
    
    typedef int ElemType;
    typedef struct DoubleStack{
    	ElemType *array;
    	int top1;	//SP for stack1
    	int top2;	//SP for stack2
    }DouStack,*pDouStack;
    
    void InitialDouStack(pDouStack S);
    void Push(pDouStack S,ElemType add_data,int flags);//flags==1,for stack1;flags==2,for stack2
    void Pop(pDouStack S,ElemType *del_data,int flags);//flags==1,for stack1;flags==2,for stack2
    void PrintDoubleStack(pDouStack S);
    
    int main()
    {
    	DouStack S;
    	InitialDouStack(&S);	
    	for(int i = 1; i <= 20; ++i)
    	{
    		Push(&S,i,i%2 + 1);//for debug,flag2 is 1 or 2
    	}
    	PrintDoubleStack(&S);	//print stack1 and stack2
    	ElemType temp = 0;	//accept data pop from stack;
    	for(int i = 1; i <= 25; ++i)
    	{
    		Pop(&S,&temp,i%2 + 1);
    	}
    	PrintDoubleStack(&S);	
    
    	return 0;
    }
    
    void InitialDouStack(pDouStack S)
    {
    	S->array = (ElemType *)calloc(INIT_STACK_SIZE,sizeof(DouStack));
    	if(!S->array)
    	{
    		printf("allocate memory error \n");
    		return ;
    	}
    	S->top1 = 0;
    	S->top2 = INIT_STACK_SIZE;
    }
    
    void Push(pDouStack S,ElemType add_data,int flags)
    {
    	if(S->top2 == S->top1)
    	{
    		printf("Full double stack\n");
    		return ;
    	}	
    	switch(flags)
    	{
    		case 1:	//push into stack1
    			S->array[S->top1++] = add_data;			
    			break;
    		case 2: //push into stack2
    			S->array[--S->top2] = add_data;			
    			break;
    		default :
    			return;
    	}
    	return;
    }
    
    void PrintDoubleStack(pDouStack S)
    {
    	int top1 = S->top1;
    	int top2 = S->top2;
    	
    	printf("Stack 1 : \n");
    	while(top1)
    	{
    		printf("Stack 1 %d : %d \n",top1,S->array[--top1]);
    	}
    	
    	printf("Stack 2 : \n");
    	while(top2 < INIT_STACK_SIZE)
    	{
    		printf("Stack 2 %d : %d \n",top2,S->array[top2++]);
    	}
    }
    
    void Pop(pDouStack S,ElemType *del_data,int flags)
    {
    	switch(flags)
    	{
    		case 1:	//pop from stack1
    			if(S->top1 == 0)
    			{	
    				printf("Stack1 is empty!\n");
    				return;
    			}
    			*del_data = S->array[--S->top1];			
    			break;
    		case 2: //pop from stack2
    			if(S->top2 == INIT_STACK_SIZE)
    			{
    				printf("Stack2 is empty!\n");
    				return;
    			}
    		        *del_data = S->array[S->top2++];			
    			break; 
    	}
    }