[C语言]两个栈实现队列
2014-04-15 by muzi前言
这是学习c语言的第一个训练题。刚开始写得真的非常差!!后来在大男哥的知道下学会了如何写c语言。本篇教程是:如何使用两个栈实现队列的功能。基本上这个代码也是他手把手教的。
算法
如何使用两个栈实现队列? 大家都能想到需要在pop的时候从一个栈到另一个栈倒一下,再pop,这样就有做到先入先出了。但是如何判别哪一个是目前正在使用的,而哪一个又是用来接收第一个栈pop数据的呢?
其实有一个好办法就是,指定一个是专门用于入栈的栈in_stack,所有数据入栈的时候必须入到这个栈中,而出栈的时候,需要将数据pop到另一个栈中,然后再从另一个栈中出栈。第二次出栈的时候直接从out_stack。直到out_stack的数据为空,则将in_stack的数据pop到out_stack中。这样就能保证出栈的顺序是FIFO了。
同时,in_stack的深度就是队列的最小深度。
最大深度是len(in_stack+out_stack).当且仅当第一次push时,全部push到满,然后pop数据,之后继续push直到满。严格意义上来说应该是len(in_stack+out_stack)-1,因为有一个pop掉了。
实现
stack的实现
首先我们要实现stack。以下是stack.h
/*
##################
Author: muzi
Date:2014/4/10
TODO: Using the stack to complete the list function.
##################
*/
#ifndef _STACK_H_
#define _STACK_H_
typedef struct _stack
{
void ** buttom;
int top;
int max_size;
}stack_t;
stack_t * stack_create();
void stack_destroy(stack_t * stack);
void * stack_push(stack_t * stack, void * data);
void * stack_pop(stack_t * stack);
#endif
stack.h中定义了stack的结构体,以及以下相关的函数,如push,pop等。当然类似于面向对象中的构造函数的stack_create()也是必须的。最后还不忘定义destroy去释放内存。
#include <stdlib.h>
#include "stack.h"
stack_t* stack_create(){
stack_t * p = (stack_t *)malloc(sizeof(stack_t));
p->max_size = 10;
p->buttom = (void **)malloc(sizeof(void *) * p->max_size);
p->top = 0;
return p;
}
void stack_destroy(stack_t * stack){
free(stack->buttom);
free(stack);
}
void * stack_push(stack_t * stack, void * data)
{
if(stack->top >= stack->max_size)
{
return NULL;
}
stack->buttom[stack->top] = data;
stack->top++;
return data;
}
void * stack_pop(stack_t * stack)
{
if (stack->top > 0)
{
stack->top--;
return (stack->buttom[stack->top]);
}
return NULL;
}
这些都是基本的函数,相比应该不难,不做更多解释。
queue的实现
同样的先,先写queue.h
#ifndef _QUEUE_H_
#define _QUEUE_H_
#include "stack.h"
typedef struct _QUEUE_H_
{
stack_t * in;
stack_t * out;
}queue_t;
queue_t * queue_create();
void queue_destroy(queue_t * queue);
void * queue_push(queue_t * queue, void * data);
void * queue_pop(queue_t * queue);
#endif
这个文件定义了struct queue_t,成员有 两个stack的指针。(喜欢python的人是绝对不喜欢c的指针的,比如我。不过不得不说,不会c的程序员,真不好意思说自己是程序员。)
我们要在queue.c中去实现queue.h定义的内容。
关键算法也在这里。
#include "queue.h"
#include <stdlib.h>
queue_t * queue_create()
{
queue_t * queue = (queue_t *)malloc(sizeof(queue_t));
queue->in = stack_create();
queue->out = stack_create();
return queue;
}
void queue_destroy(queue_t * queue)
{
stack_destroy(queue->in);
stack_destroy(queue->out);
}
void * queue_push(queue_t * queue, void * data)
{
return stack_push(queue->in, data);
}
void * queue_pop(queue_t * queue)
{
if(queue->out->top == 0) //最关键的其实就是这个判断以及这个判断所执行的语句(如果out stack都出栈了,那么需要从in中倒换过来。)
{
while(queue->in->top > 0) //如果in中有数据的话。
{
stack_push(queue->out,stack_pop(queue->in));
}
}
return stack_pop(queue->out);//始终返回的是out_stack的数据
}
就是这么简单,就把功能实现了。跟着大男哥学习c语言编程,还是有很多收获的。
main函数测试。
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
//#include "stack2list.h"
void int_printer(void * data);
int main()
{
queue_t * queue = queue_create();
int * data = (int *)malloc(sizeof(int));
*data = 1;
queue_push(queue,data);
data = (int *)malloc(sizeof(int));
*data = 2;
queue_push(queue,data);
data = (int *)malloc(sizeof(int));
*data = 3;
queue_push(queue,data);
data = (int *)malloc(sizeof(int));
*data = 4;
queue_push(queue,data);
data = (int *)malloc(sizeof(int));
*data = 5;
queue_push(queue,data);
int i = 0;
for(i = 0; i<2 ; i++)
{
data = (int *)queue_pop(queue);
printf("%d,",*data);
free(data);
}
data = (int *)malloc(sizeof(int));
*data = 6;
queue_push(queue,data);
data = (int *)malloc(sizeof(int));
*data = 7;
queue_push(queue,data);
for(i = 0; i<5 ; i++)
{
data = (int *)queue_pop(queue);
printf("%d,",*data);
free(data);
}
return 0;
}
void int_printer(void * data)
{
printf("%d",*((int *)data));
}
至此功能实现。
在写代码的过程中,发现设计的重要性,一个好的逻辑思维,设计风格,能让代码写得非常优雅。其实写代码也是一个有讲究的活。就像一个工程师设计一个模型一样,既要美观实用,又要能随时被拿走,放到别处使用。代码的风格,结构的设计,实现方案等等,都是一个很好玩的事情。
希望不久之后我能学好c语言!感谢大男哥的帮助!