首页 > 代码库 > 队列的基本操作

队列的基本操作

队列的存储结构有两种:一种是线性表存储,一种是链式存储。用线性表存储时,要注意队列的长度有没有超过预先设置的大小,在这个程序中,队列的可以在存满的时候,自动增加队列的长度。用链表存储,则没有长度的限制。下面分别是这两种存储结构的实现。

线性表存储:

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_INIT_SIZE 10
#define QUEUE_REALLOCATION 2

typedef int ElemType;

/*顺序队列的存储结构定义*/
typedef struct SqQueue
{
	ElemType *base;
	int front;
	int rear;
	int QueueLength;
}SqQueue;

void Init_SqQueue(SqQueue *S)
{
	S->base = (ElemType*)malloc(QUEUE_INIT_SIZE*sizeof(ElemType));
	if (!S->base)
		exit(1);
	S->rear = S->front = 0;
	S->QueueLength = QUEUE_INIT_SIZE;
}

void En_SqQueue(SqQueue *S, ElemType e)
{
	if ((S->rear + 1) % S->QueueLength == S->front){
		S->base = (ElemType*)malloc(S->base,(S->QueueLength+QUEUE_REALLOCATION)*sizeof(ElemType));
		if (!S->base)
			exit(1);
		if (S->front > S->rear){
			int i;
			for (i = S->front; i < S->QueueLength; ++i){
				S->base[i + QUEUE_REALLOCATION] = S->base[i];
			}
			S->front += QUEUE_REALLOCATION;
		}
		S->QueueLength += QUEUE_REALLOCATION;
	}
	S->base[S->rear] = e;
	S->rear = (S->rear + 1) % S->QueueLength;
}

int De_SqQueue(SqQueue *S, ElemType *e)
{
	if (S->rear == S->front)
		return 0;
	*e = S->base[S->front];
	S->front = (S->front + 1) % S->QueueLength;
	return 1;
}

int SqQueueLength(SqQueue S)
{
	return (S.rear - S.front + S.QueueLength) % S.QueueLength;
}

int is_SqQueueEmpty(SqQueue S)
{
	if (S.front == S.rear)
		return 1;
	else
		return 0;
}

void SqQueueTest()
{
	SqQueue S;
	Init_SqQueue(&S);
	printf("Please input some numbers to enqueue(Ctrl+Z to end):\n");
	int e;
	while (scanf("%d", &e) != EOF)
		En_SqQueue(&S, e);
	printf("The dequeue sequence is:\n");
	while (!is_SqQueueEmpty(S)){
		De_SqQueue(&S,&e);
		printf("%d ",e);
	}
	printf("\n");
}

int main()
{
	SqQueueTest();
	return 0;
}



链表存储:

#include <stdio.h>
#include <stdlib.h>

/*链式队列的存储结构定义*/
typedef struct LinkQueue_Node
{
	ElemType data;
	struct LinkQueue_Node *next;
}*Queue_pNode, Queue_Node;

typedef struct LinkQueue
{
	struct LinkQueue_Node *front;
	struct LinkQueue_Node *rear;
}LinkQueue;

void Init_LinkQueue(LinkQueue *L)
{
	L->front = L->rear = (Queue_pNode)malloc(sizeof(Queue_Node));
	if (!L->front)
		exit(1);
	L->front->data = http://www.mamicode.com/0;>