【C语言】能否用两个栈实现一个队列的功能

5119

参考答案:

//结点结构体:
typedef struct node
{
   int data;
   node *next;
}node, *LinkStack;
//创建空栈:
LinkStack CreateNULLStack(LinkStack &S)
{
   S = (LinkStack)malloc(sizeof(node)); //申请新结点
   if (NULL == S)
   {
   	printf("Fail to malloc a new node.\n")
   		return NULL;
   }
   S->data = 0; //初始化新结点
   S->next = NULL;
   return S;
}
//栈的插入函数:
LinkStack Push(LinkStack &S, int data)
{
   if (NULL == S) //检验栈
   {
   	printf("There no node in stack!");
   	return NULL;
   }
   LinkStack p = NULL;
   p = (LinkStack)malloc(sizeof(node)); //申请新结点
   if (NULL == p)
   {
   	printf("Fail to malloc a new node.\n");
   	return S;
   }
   if (NULL == S->next)
   {
   	p->next = NULL;
   }
   else
   {
   	p->next = S->next;
   }
   p->data = data; //初始化新结点
   S->next = p; //插入新结点
   return S;
}
//出栈函数:
node Pop(LinkStack &S)
{
   node temp;
   temp.data = 0;
   temp.next = NULL;
   if (NULL == S) //检验栈
   {
   	printf("There no node in stack!");
   	return temp;
   }
   temp = *S;
   10
   	if (S->next == NULL)
   	{
   		printf("The stack is NULL,can't pop!\n");
   		return temp;
   	}
   LinkStack p = S->next; //节点出栈
   S->next = S->next->next;
   temp = *p;
   free(p);
   p = NULL;
   return temp;
}
//双栈实现队列的入队函数:
LinkStack StackToQueuPush(LinkStack &S, int data)
{
   node n;
   LinkStack S1 = NULL;
   CreateNULLStack(S1); //创建空栈
   while (NULL != S->next) //S 出栈入 S1
   {
   	n = Pop(S);
   	Push(S1, n.data);
   }
   Push(S1, data); //新结点入栈
   while (NULL != S1->next) //S1 出栈入 S
   {
   	n = Pop(S1);
   	Push(S, n.data);
   }
}


说明:用两个栈能够实现一个队列的功能,那用两个队列能否实现一个队列的功能呢?结果是否定的,因为栈是先进后出,将两个栈连在一起,就是先进先出。而队列是现先进先出,无论多少个连在一起都是先进先出,而无法实现先进后出。


特别声明:本文仅供交流学习 , 版权归属原作者,并不代表游民部落赞同其观点和对其真实性负责。若文章无意侵犯到您的知识产权,损害了您的利益,烦请与我们联系vmaya_gz@126.com,我们将在24小时内进行修改或删除。

相关推荐:

教程推荐