[原创]C语言面试题 两个栈实现一个队列

思路： 栈是先入后出，所以我们可以考虑把栈一的数据从栈顶把数据压到另一个缓冲栈栈里。然后缓冲栈依次出栈，就实现了先入先出的逻辑，然后再把数据压回去。

#include <iostream>

#include<stdio.h>

#include<stdlib.h> 

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int size=0;

typedef struct no

{

int data;

struct no *pnext;                       //构造链表 

struct no *ppre;

}node;

typedef struct 

{

node head;                 //构造链表头和链表尾 

node tail;

}lht;

void link_show(const lht *p)

 { node *pn=(node*)p->head.pnext;

     while(pn!=&p->tail)

     {

         printf("%d ",pn->data);                    //遍历显示链表 

         pn=pn->pnext;

     }

     printf("\n");

 }

void link_init(lht *p)

 {

     p->head.pnext=&p->tail;

     p->head.ppre=NULL;

     p->tail.pnext=NULL;                //初始化链表 

     p->tail.ppre=&p->head;

 }

  void link_deinit(lht *p)

  {

      node *pf=NULL,*pm=NULL,*pl=NULL;

      while(p->head.pnext!=&p->tail)

      {

      pf=&p->head;

      pm=pf->pnext;

      pl=pm->pnext;                            //清空链表 

      pf->pnext=pm->pnext;

    pl->ppre=pf; 

      free(pm);

      pm=NULL;

      }

  }

 int link_empty(lht **p)

 {

     if((*p)->head.pnext==&(*p)->tail)    //判断空链表 

     return 1;

     return 0;

 }

int link_add(lht *p,int i)

{

      node *pf=NULL,*pm=NULL,*pl=NULL,*pn=NULL;   //进栈 

      pn=(node*)malloc(sizeof(node));

      if(pn==NULL)

      return 0;

      pf=&p->head;

      pm=pf->pnext;

      pl=pm->pnext;

    pf->pnext=pn;

      pn->pnext=pm;

    pn->ppre=pf; 

    pm->ppre=pn;

    pn->data=i;

    return 1;

}

int link_sub(lht *p)     //出栈

{

      node *pf=NULL,*pm=NULL,*pl=NULL,*pn=NULL;

      pf=&p->head;

      pm=pf->pnext;

      pl=pm->pnext;

      pf->pnext=pm->pnext;

      pl->ppre=pm->ppre;

    free(pm);

    pm=NULL;     

}

void link_pop(lht *p)       //出队列 

{    

    if(link_empty((lht **)&p))   //判断队列是否为空 

    return; 

    node *pf=NULL,*pm=NULL,*pl=NULL;;

    lht l1={0};

    link_init(&l1);       //初始化缓冲栈 

    pf=&p->head;

    pm=pf->pnext;

    pl=pm->pnext;

    while(pl!=NULL)

    {

        link_add(&l1,pm->data);  //把栈里的数据压进缓冲栈并清空栈1 

        pf->pnext=pm->pnext;

          pl->ppre=pm->ppre;

        free(pm);

        pm=NULL; 

        pm=pf->pnext;

        pl=pm->pnext;

    } 

link_sub(&l1);   //弹出缓冲栈的第一个节点，相当于先入先出 

pf=&l1.head;

pm=pf->pnext;         

pl=pm->pnext;

    node *pf1=NULL,*pm1=NULL,*pl1=NULL,*pn=NULL;

        pf1=&p->head;

    while(pm!=&l1.tail)//把数据压从缓冲栈回栈1 

    {

      pn=(node*)malloc(sizeof(node));

      if(pn==NULL)

      return; 

      pm1=pf1->pnext;    

    pf1->pnext=pn;

      pn->pnext=pm1;

    pn->ppre=pf1; 

    pm1->ppre=pn;

    pn->data=pm->data;

    pm=pm->pnext;

    } 

    link_deinit(&l1);    

} 

int main(int argc, char *argv[]) {

    lht l1={0};

    link_init(&l1);

    link_add(&l1,1);

    link_add(&l1,2);

    link_add(&l1,3);

    link_add(&l1,4);

    link_add(&l1,5);

    link_add(&l1,6);

    link_pop(&l1);    

    link_show(&l1);

    return 0;

}

上传的附件

两个栈实现一个队列.png