学步园

1.队列是先入先出额数据结构，它的实现可以用数组，也可以用链表。用数组实现链表时，需要预先分配数组的大小，用front和rear下标分别表示队头元素下标和队尾元素下标，插入一个元素时，使队尾的下标rear加1，删除一个元素时，front下标加1，判断是否为空的队列只要判断front和rear是否相等。队列的插入操作可表示为

# include <stdio.h>
# include <stdlib.h>
# define Maxsize  100
struct queue 
{
	int front;
	int rear;
	int q[Maxsize];
};

int main()
{   
	void initialqueue(queue*);
	void push(queue *,int);
	int pop(queue*);
	int isempty(queue*);
	int isfull(queue*);
	queue p;
	initialqueue(&p);
	push(&p,1);
	push(&p,2);
	push(&p,3);
    printf("%d\n",isempty(&p));
	printf("%d\n",pop(&p));

	system("pause");
return 0;
}

void initialqueue(queue *p)
{
	p->front=p->rear=0;
}
int isfull(queue *p)
{
	return p->rear==p->front+Maxsize-1;
}

int isempty(queue *p)
{
	return p->front==p->rear;
}
void push(queue* p,int x)
{
if(isfull(p))
{
	printf("queue is full\n");
	exit(-1);
}
p->q[p->rear++]=x;
}

int pop(queue *p)
{
if(isempty(p))
{
printf("queue is empty\n");
exit(-1);
}
return p->q[p->front++];

}

2.链表实现队列

用链表实现队列，需要定义节点结构体存储节点的值和指针，另外还要定义头指针和尾指针，分别指向队头和队尾，插入元素的操作可以表示为

# include <stdio.h>
# include <stdlib.h>
struct node
{
int num;
node *next;
};
typedef struct 
{
	node *front;
	node *rear;
}link;
int main()
{
	void initialqueue(link p);
	link push(link,int);
	int pop(link);
	int isempty(link);
	int isfull(link);
	link p={0,0};
	initialqueue(p);
	p=push(p,1);
	p=push(p,2);
	p=push(p,3);
	printf("%d\n",pop(p));
	system("pause");
return 0;
}

void initialqueue(link p)
{
p.front=p.rear=0;
}
int isempty(link p)
{
	return p.front==NULL&&p.rear==NULL;
}

link push(link p,int x)
{
	node *t=(node *)malloc(sizeof(node));
	t->num=x;
	t->next=NULL;
if(isempty(p))
{
	p.front=p.rear=t;	
}
else
{
	p.rear->next=t;	
	p.rear=t;
}
return p;
}

int pop(link p)
{
	int temp;
	node *t;
if(isempty(p))
{
printf("queue is empty\n");
exit(-1);
}
if(p.front!=p.rear){
temp=p.front->num;
t=p.front;
p.front=p.front->next;
free(t);
}
else
{
temp=p.front->num;
t=p.front;
p.front=p.rear=NULL;
free(t);
}
return temp;
}