打印
[其它应用]

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

[复制链接]
1270|1
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
duo点|  楼主 | 2024-3-17 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;
}

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

使用特权

评论回复
沙发
CarterERO| | 2024-3-18 11:00 | 只看该作者
这个是怎么实现的啊

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

434

主题

1627

帖子

1

粉丝