用两个栈实现一个队列的功能

只看该作者 · 2024-3-16 11:00

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;

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 );
}
return S;
}

「注意」：用两个栈能够实现一个队列的功能，那用两个队列能否实现一个队列的功能呢？结果是否定的，因为栈是先进后出，将两个栈连在一起，就是先进先出。而队列是现先进先出，无论多少个连在一起都是先进先出，而无法实现先进后出。