28 March 2014
/* 数组实现的队列 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAXSIZE 100
typedef int DataType;

typedef struct
{
    DataType se[MAXSIZE];
    int num, rear;
} SeQueue;


SeQueue* InitQueue();             // 初始化队列
int Queue_In(SeQueue* q, DataType data);    // 入队
int Queue_Out(SeQueue* q,  DataType* elem); // 出队


int main()
{
    DataType elem;
    SeQueue* q = InitQueue();
    Queue_In(q, 4);
    Queue_In(q, 5);
    if(Queue_Out(q, &elem) == 0)
        printf("elem:%d", elem);

    if(Queue_Out(q, &elem) == 0)
        printf("elem:%d", elem);

    if(Queue_Out(q, &elem) == 0)
        printf("elem:%d", elem);
    return 0;
}


SeQueue* InitQueue()
{
    SeQueue* q = malloc(sizeof(SeQueue));
    assert(q != NULL);  // 断言,判断内存是否申请成功
    q->rear = -1;
    q->num = 0;
    return q;
}


int Queue_In(SeQueue* q, DataType data)
{
    int error;

    if(q == NULL) error = 1; // 传入参数有误
    else if(q->num == MAXSIZE)   error = 2; // 队列已满
    else
    {
        q->rear = (q->rear + 1) % MAXSIZE;
        q->se[q->rear] = data;
        q->num++;
        error = 0;  // 入队成功

    }
    return error;
}

int Queue_Out(SeQueue* q, DataType* elem)
{
    int error;

    if(q == NULL) error = 1; // 传入参数有误
    else if(q->num == 0) error = 3; // 队列为空
    else
    {

        int pos = (q->rear - q->num + 1) % MAXSIZE;
        *elem = q->se[pos];
        q->num--;
        error = 0; // 出队成功
    }
    return error;
}

/* 链表实现的队列 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAXSIZE 100
typedef int DataType;

typedef struct linkqueue
{
	struct linkqueue* rear;
	DataType data;
} LinkQueue;


LinkQueue* InitQueue();             // 初始化队列
int Queue_In(LinkQueue** q, DataType data);    // 入队
int Queue_Out(LinkQueue** q, DataType* elem); // 出队
void Queue_Clear(LinkQueue** q);     // 清空队列


LinkQueue* InitQueue()
{
	LinkQueue* q = (LinkQueue*)malloc(sizeof(LinkQueue));
	assert(q != NULL);  // 断言,判断内存是否申请成功
	q->rear = q;
	return q;
}


int Queue_In(LinkQueue** q, DataType data)
{
	int error;

	if (*q == NULL) error = 1; // 传入参数有误
	else
	{
		LinkQueue *node = (LinkQueue*)malloc(sizeof(LinkQueue));
		assert(node != NULL);
		node->data = data;
		node->rear = (*q)->rear;
		(*q)->rear = node;
		(*q) = node;  // 改变指针

		error = 0;  // 入队成功
	}
	return error;
}

int Queue_Out(LinkQueue** q, DataType* elem)
{
	int error;

	if (*q == NULL) error = 1; // 传入参数有误
	else if ((*q)->rear == *q) error = 3; // 队列为空
	else
	{
		LinkQueue *temp, *p;
		p = (*q)->rear;
		temp = p->rear;
		p->rear = temp->rear;
		*elem = temp->data;
		if (p->rear == p) *q = p;  // 改变指针
		free(temp);
		error = 0; // 出队成功
	}
	return error;
}


void Queue_Clear(LinkQueue** q)
{
	int error;

	if (q == NULL) error = 1; // 传入参数有误
	else
	{
		LinkQueue* p;
		*q = (*q)->rear;
		for (p = (*q)->rear; p != (*q); p = (*q)->rear)
		{
			(*q)->rear = p->rear;
			free(p);
		}
	}
}



int main()
{
	DataType elem;
	LinkQueue* q = InitQueue();
	Queue_In(&q, 4);
	Queue_In(&q, 5);

	Queue_Clear(&q);

	if (Queue_Out(&q, &elem) == 0)
		printf("elem:%d\n", elem);

	if (Queue_Out(&q, &elem) == 0)
		printf("elem:%d", elem);

	if (Queue_Out(&q, &elem) == 0)
		printf("elem:%d", elem);

	return 0;
}

Tip: 为了能够在函数内部对传入的队列指针进行重新赋值,因此使用二级指针


借助栈将但链表逆序

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

#define MAXSIZE 100
typedef char DataType;
typedef struct linklist
{
    DataType data;
    struct linklist *next;
} LNode, *LinkList;

typedef struct
{
    DataType elems[MAXSIZE];
    int currentPos;
} SeqStack;

LinkList List_Init();
void List_Insert(LinkList L, DataType data);

SeqStack* Stack_Init(); // 初始化栈
int Stack_Push(SeqStack* s, DataType data);     // 压栈
int Stack_Pop(SeqStack* s, DataType* value);    // 出栈

int main()
{
    LinkList L = List_Init();
    SeqStack *s = Stack_Init();
    int i;
    DataType ch, value;

    // 构造一个单链表
    LNode *r = L, *node;
    printf("请输入字符串序列,以@结束\n");
    while((ch = getchar()) != '@')
    {
        node = malloc(sizeof(LNode));
        assert(node != NULL);
        node->data = ch;
        node->next = NULL;
        r->next = node;
        r = node;
    }


	/* 链表入栈 */
	r = L->next;
	while(r != NULL)
	{
		Stack_Push(s,r->data);
		r = r->next;
	}

	r = L;	// 将出栈的元素重新构造一个链表
	/* 链表出栈 */
	while(Stack_Pop(s, &value))
	{
		node = malloc(sizeof(LNode));
        assert(node != NULL);
        node->data = value;
        node->next = NULL;
        r->next = node;
        r = node;
	}


	/* 输出序列 */
	r = L->next;
	while(r!= NULL)
	{
		printf("%c", r->data);
		r = r->next;
	}
    return 0;
}

/* 初始化链表 */
LinkList List_Init()
{
    LinkList l = (LinkList)malloc(sizeof(LNode));
    assert(l != NULL);
    l->next = NULL;
    return l;
}


/* 初始化栈 */
SeqStack* Stack_Init()
{
    SeqStack *s = (SeqStack*)malloc(sizeof(SeqStack));
    assert(s != NULL);  // 判断内存是否申请成功
    s->currentPos = -1;
    return s;
}

/* 压栈 */
int Stack_Push(SeqStack* s, DataType data)
{
    int error;
    if(s == NULL) error = 0;
    else if(s->currentPos >= MAXSIZE) error = 0;
    else
    {
        s->elems[++s->currentPos] = data;
        error = 1;
    }
    return error;
}

int Stack_Pop(SeqStack* s, DataType* value)
{
	int error;
    if(s == NULL) error = 0;
    else if(s->currentPos == -1) error = 0;
    else
    {
        *value = s->elems[s->currentPos--];
        error = 1;
    }
    return error;
}