两个栈实现一个队列,C语言实现,队列可伸缩,容纳任意数目的元素。

图片 2

  1、头文件:stack_to_queue.h:封装了:队列、栈的数据结构和各种操作的函数。

  如果我们还想继续删除队列的头部应该怎么办呢?剩下的两个元素是b和c,b比c早进入队列,因此b应该先删除。而此时b恰好又在栈顶上,因此直接弹出stack2的栈顶即可。这次弹出操作之后,stack1中仍然为空,而stack2为{c}(如图2.8(c)所示)。

 1 #include<stdio.h>   2 #include"stack_to_queue.h"   3    4 int main()   5 {   6     SqQueue q;   7     int i,data;   8    9     InitQueue(&q);  10     for(i=0;i<1000;i++)  11     {  12         push_queue(&q,i);  13     }  14     while((pop_queue(&q,&data))!=0)  15     {  16         printf("%d  ",data);  17     }  18   19     return 0;  20 }

完整代码:


 

2、主函数:main.c:只为测试用,通过for循环让1000个数0-999入队列,再打印。

  运行结果:

  1 #ifndef STACK_TO_QUEUE_H    2 #define STACK_TO_QUEUE_H    3     4 #include<stdio.h>    5 #include<stdlib.h>    6     7 #define ALLOC_SIZE 512    8 #define ElemType int    9    10 typedef struct sqstack   11 {   12     ElemType *top;          //栈顶指针   13     ElemType *base;         //栈底指针   14     int stack_size;    //栈目前能存储的元素数目   15 }SqStack;                //顺序栈   16    17 typedef struct sqqueue   18 {   19     SqStack front;          //队列头,出口,   20     SqStack rear;           //队列尾,入口   21 }SqQueue;   22    23 /*栈的初始化函数*/   24 void InitStack(SqStack *s)   25 {   26     if((s->top=(ElemType*)malloc(ALLOC_SIZE*sizeof(ElemType)))==NULL)   27     {   28         printf("stack malloc error\n");   29         exit(1);   30     }   31     s->base=s->top;   32     s->stack_size=ALLOC_SIZE;   33 }   34    35 /*出栈函数,栈为空时返回0,成功出栈时返回1*/   36 int pop_stack(SqStack *s,ElemType *data)   37 {   38     if(s->top!=s->base)   39     {   40         s->top--;   41         *data=*s->top;   42         return 1;   43     }   44     else                    //返回值为0,表示栈为空   45     {   46         return 0;   47     }   48 }   49    50 /*入栈函数*/   51 void push_stack(SqStack *s,ElemType data)   52 {   53     if((s->top-s->base)>=s->stack_size)   54     {   55         if((s->base=(ElemType *)realloc(s->base,(s->stack_size+ALLOC_SIZE)*sizeof(ElemType)))==NULL)   56         {   57             printf("stack realloc error\n");   58             exit(1);   59         }   60         else   61         {   62             s->top=s->base+s->stack_size;   63             s->stack_size+=ALLOC_SIZE;   64         }   65     }   66     *(s->top)=data;   67     s->top++;   68 }   69    70 /*队列初始化函数*/   71 void InitQueue(SqQueue *q)   72 {   73     SqStack A,B;   74    75     InitStack(&A);   76     InitStack(&B);   77     q->front=B;        //将栈B作为队列的出口   78     q->rear=A;         //将栈A作为队列的入口   79 }   80    81 /*入队列函数*/   82 void push_queue(SqQueue *q,ElemType data)   83 {   84     push_stack(&q->rear,data);   85 }   86    87 /*出队列函数,队列为空时返回0,成功出队列返回1*/   88 int pop_queue(SqQueue *q,ElemType *data)   89 {   90     if((pop_stack(&q->front,data))==0)       //如果作为出口的栈为空,就将入口栈的内容压入   91     {   92         while((pop_stack(&q->rear,data))!=0)   93         {   94             push_stack(&q->front,*data);   95         }   96     }   97     else        //否则,返回1   98     {   99         return 1;  100     }  101     if((pop_stack(&q->front,data))==0)       //如果将入口栈的内容压人后还为空,说明此时队列为空  102     {  103         return 0;  104     }  105     else  106     {  107         return 1;  108     }  109 }  110 #endif

图片 1

二、代码:

 

之前写的时候犯了一个错误,在stack_to_queue.h中的62行,使用realloc函数重新分配内存后,要将top指针也指向新的位置,我漏掉了这一步,导致出错,检查了很久,最后的解决过程在这:

  接下来再插入一个元素d。我们还是把它压入stack1(如图2.8(d)所示),这样会不会有问题呢?我们考虑下一次删除队列的头部stack2不为空,直接弹出它的栈顶元素c(如图2.8(e)所示)。而c的确是比d先进入队列,应该在d之前从队列中删除,因此不会出现任何矛盾。

一、思路:1、创建两个空栈A和B;2、A栈作为队列的入口,B栈作为队列的出口;3、入队列操作:即是入栈A;4、出队列操作:若栈B为空,则将A栈内容出栈并压人B栈,再出      B栈;不为空就直接出栈;

 

  我们通过一系列栈的压入和弹出操作来分析用两个队列模拟一个栈的过程。如图2.9(a)所示,我们先往栈内压入一个元素a。由于两个队列现在都是空的,我们可以选择把a插入两个队列的任意一个。不妨插入queue1。接下来继续往栈内压入b、c两个元素,我们把它们都插入queue1。这个时候queue1包含3个元素a、b和c,其中a位于队列的头部,c位于队列的尾部。

  接下来我们考虑往栈内压入一个元素d。此时queue1已经有一个元素,我们就把d插入到queue1的尾部(如图2.9(d)所示)。如果我们再从栈内弹出一个元素,此时被弹出的应该是最后被压入的d。由于d位于queue1的尾部,我们只能先从有删除queue1的元素并插入到queue2,直到在queue1中遇到d再直接把它删除(如图2.9(e)所示)。

  对于push和pop操作,其时间为O(n).

 

 

 1 template <typename T> class CQueue
 2 {
 3 public:
 4     CQueue(void);
 5     ~CQueue(void);
 6 
 7     void appendTail(const T& node);
 8     T deleteHead();
 9 
10 private:
11     stack<T> stack1;
12     stack<T> stack2;
13 };

  这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则,由于a比b、c先插入到队列中,最先被删除的元素应该是a。元素a存储在stack1中,但并不在栈顶上,因此不能直接进行删除。注意到stack2我们还一直没有使用过,现在是让stack2发挥作用的时候了。如果我们把stack1中的元素逐个弹出并压入stack2,元素在stack2中的顺序正好和在stack1中的顺序相反。因此经过3次弹出stack1和压入stack2操作之后,stack1为空,而stack2中的元素是{c,b,a},这个时候就可以弹出stack2的栈顶a了。此时的stack1为空,而stack2的元素为{c,b},其中b在栈顶(如图2.8(b)所示)。

完整代码:

  图片 2

  现在我们考虑从栈内弹出一个元素。根据栈的后入先出原则,最后被压入栈的c应该最先被弹出。由于c位于queue1的尾部,而我们每次只能从队列的头部删除元素,因此我们可以先从queue1中依次删除元素a、b并插入到queue2中,再从queue1中删除元素c。这就相当于从栈中弹出元素c了(如图2.9(b)所示)。我们可以用同样的方法从栈内弹出元素b(如图2.9(c)所示)

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注