用两个栈实现一个队列

心已赠人 2022-08-08 00:37 280阅读 0赞

最近在自学数据结构，就做了一个非常经典的题，使用两个栈实现一个队列。

其实个人思路就是两个栈倒来倒去，真的很麻烦。不多说了直接上代码。

/*************************************************************************
    	> File Name: starck.c
    	> Author: zmr
    	> Mail: 1797763610@qq.com 
    	> Created Time: Wed 22 Apr 2015 07:35:26 PM CST
     ************************************************************************/
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<malloc.h>
    
    typedef struct node{                     //建立数据元素 
    	int data;
    	struct node *next;
    }_node;
    
    typedef struct nodectl{                 //建立栈的总体结构 
    	_node *top  ;
    	_node *base;
    	int count  ;
    }_ndctl;
    
    void starck_init(_ndctl *ctl)                //初始化栈 
    {
    	memset(ctl,0x00,sizeof(_ndctl));
    }
    
    void push(_ndctl *ctl,_node *node)             //入栈一个元素 
    {
    	if(NULL == ctl && NULL == node)
    	{
    		return ;
    	}
    	if(NULL == ctl->top)
    	{
    		ctl->top=node;
    		ctl->base=node;
    	}
    	else
    	{
    		node->next=ctl->top;
    		ctl->top=node;
    	}
    	ctl->count++ ;
    	
    }
    
    void pop(_ndctl *ct1,int LEN)                       //出栈LEN个元素 
    {
    	_node *p;
    	if(NULL == ct1 && LEN <= ct1->count )
    	{
    		return ;
    	}
    	while(LEN > 0)
    	{
    		p = ct1->top;
    		ct1->top = p->next;
    		free(p);
    		LEN--;
    		ct1->count--;
    	}
    
    }
    
    void stack_destory(_ndctl *ctl)                //删除这个栈 
    {
    	_node *ptemp;
    	if(NULL == ctl)
    	{
    		return ;
    	}
    	while(0<ctl->count)
    	{
    		ptemp=ctl->top->next;
    		free(ctl->top);
    		ctl->top=ptemp;
    		ctl->count--;
    	}
    }
    
    void pushS(_ndctl *S1,_ndctl *S2)           //将一个栈的元素入到另一个栈中 
    {
    	_node *temp;
    	_node *node;
    	_node *p   ;
    	int size;
    	size=S1->count;
    	temp = S1->top;
    	
    	while(size > 0)
    	{
    		
    		node = (_node *)malloc(sizeof(_node));
    		node->data = temp->data ;
    		p = temp;
    		temp=temp->next;
    		free(p);
    		size--;
    		push(S2,node);
    	
    	}
    	
    }	
    
    
    int show(_ndctl *S3)                             //按出栈顺序打印一个栈 
    {
    	_node *ptemp;
    	int icount = S3->count;
    	ptemp = S3->top;
    	while(icount > 0)
    	{
    		printf("->%02d ",ptemp->data);
    		ptemp=ptemp->next;
    		icount--;
    	}
    	printf("\n");
    	return 0;
    }
    
    int main(int ac,char **av)
    {
    	 printf("这是栈转换队列的程序，回车继续，输入quit退出！\n");
         _ndctl ct1 = {NULL,NULL,0};
    	 _ndctl ct2 = {NULL,NULL,0};
    	 _node *node = NULL;
    	 int size =0,cnt,flag;
    	 if(ac <= 1)
    	 {
    		 printf("在命令行输入初始入队的元素个数\n");
    		 return -1;
    	 }
    	 printf("请输入初始元素的值，自动生成队列每一项自增1\n");
    	 scanf("%d",&cnt);
    	 size = atoi(av[1]);
    	 while(size > 0){
    		 node = (_node *)malloc(sizeof(_node));
    		 if(NULL == node)
    		 {
    			 printf("malloc 不能分配更多的内存\n");
    			 break ;
    		 }
    		 node->data = cnt++;
    		 push(&ct1,node);
    		 size--;
    	 }
    	 printf("原始的队列：\n");
    	 show(&ct1);
    	 printf("输入1进队列，输入2出队列，输入quit退出程序：\n");
    	 while(scanf("%d",&flag))
    	 {
    		 int num;
    		 int dat;
    		 _node *node;
    		 if(1 == flag)
    		 {
    			printf("您已选择入队，请输入你要进队元素的个数:\n");
    			scanf("%d",&num);
    			printf("请输入需要进入队列的元素，空格隔开\n");
    			while(0 < num)
    			{
    				
    				node=(_node *)malloc(sizeof(_node));
    				if(NULL == node)
    				{
    					printf("ERROR C:121,malloc not enough!\n");
    					return -1;
    				}
    				scanf("%d",&dat)     ;
    				node->data = dat     ;
    				push(&ct1,node)       ;
    				num--;
    			}
    		
    			pushS(&ct1,&ct2);
    			printf("入队后的序列\n");
    			show(&ct2);
    			starck_init(&ct1);
    			pushS(&ct2,&ct1);
    			starck_init(&ct2);
    			
    		 }
    		 
    		 else if(2 == flag) 
    		 {
    		 	
    			int Snum; 
    			printf("您选择了出队，请输入需要出队的元素个数\n:");
    			scanf("%d",&Snum);
    			if(Snum > ct1.count)
    			{
    				printf("出队数字大与队列元素总和，错误！\n");
    				return -1;
    			}
    			pushS(&ct1,&ct2);
    			starck_init(&ct1);
    			pop(&ct2,Snum);
    			printf("出队后的序列\n");
    			show(&ct2);
    			pushS(&ct2,&ct1);
    			starck_init(&ct2);
    		
    		 }
    		 printf("请输入1进队，或输入2出队，或者输入quit结束程序\n");
    		 printf("____________________________________________\n");
    	 }
    	 return 0;
    }