//结点结构体: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); }}
说明:用两个栈能够实现一个队列的功能,那用两个队列能否实现一个队列的功能呢?结果是否定的,因为栈是先进后出,将两个栈连在一起,就是先进先出。而队列是现先进先出,无论多少个连在一起都是先进先出,而无法实现先进后出。