#ifndef _CONST_H_
#define _CONST_H_

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

typedef enum
{
False = 0,
True,
}Bool;

typedef int ElemType;

#define QUEUE_MAX_SIZE 10

#define STACK_INIT_SIZE 10
#define STACK_INCREMENT_SIZE 2

#define Null ((void *)0)

typedef enum
{
NORMAL = 0,
ERROR,
UNDERFLOW,
OVERFLOW,
STATUSCOUNT,
}Status;

#endif

#ifndef _LINKED_QUEUE_H_
#define _LINKED_QUEUE_H_

#include "Const.h"

typedef struct node
{
ElemType data;
struct node *pNext;
}Node, *pNode;

typedef struct linkedqueue
{
pNode pfront;
pNode prear;
}LinkedQueue, *pLinkedQueue;

Status InitLinkedQueue(pLinkedQueue pQ);

Bool IsLinkedQueueEmpty(pLinkedQueue pQ);

Bool EnLinkedQueue(pLinkedQueue pQ, ElemType elem);

Bool DeLinkedQueue(pLinkedQueue pQ, ElemType *e);

void DestoryLinkedQueue(pLinkedQueue pQ);

void ClearLinkedQueue(pLinkedQueue pQ);

Status GetLinkedQueueHead(pLinkedQueue pQ, ElemType *e);

int GetLinkedQueueLength(pLinkedQueue pQ);

Bool InvertLinkedQueue_Static(pLinkedQueue pQ);

Bool InvertLinkedQueue_Dynamic(pLinkedQueue pQ);

#endif

#include "LinkedQueue.h"
#include "Const.h"
#include "StaticStack.h"
#include "DynamicStack.h"

Status InitLinkedQueue(pLinkedQueue pQ)
{
pNode pN = (pNode)malloc(sizeof(Node));
if (pN == Null)
{
printf("No accessable free memory.\n");
return ERROR;
}
pN->pNext = Null;
pQ->pfront = pN;
pQ->prear = pN;
}

Bool IsLinkedQueueEmpty(pLinkedQueue pQ)
{
if (pQ->pfront == pQ->prear)
{
return True;
}
else
{
return False;
}
}

Bool EnLinkedQueue(pLinkedQueue pQ, ElemType elem)
{
pNode pTempNode = (pNode)malloc(sizeof(Node));
if (pTempNode == Null)
{
printf("No accessable free memory.\n");
return False;
}

pTempNode->data = http://www.mamicode.com/elem;
pTempNode->pNext = Null;

pQ->prear->pNext = pTempNode;
pQ->prear = pTempNode;
}

Bool DeLinkedQueue(pLinkedQueue pQ, ElemType *e)
{
if (IsLinkedQueueEmpty(pQ))
{
printf("The Queue Is Empty.\n");
return False;
}
else
{
pNode pTempNode = pQ->pfront->pNext;
*e = pTempNode->data;
pQ->pfront->pNext = pTempNode->pNext;
//Only has one node in this linked queue.
if (pQ->prear == pTempNode)
{
pQ->prear = pQ->pfront;
}
free(pTempNode);
return True;
}
}

void DestoryLinkedQueue(pLinkedQueue pQ)
{
pNode p = pQ->pfront;
pNode q = Null;
while(p != Null)
{
q = p;
p = p->pNext;
free(q);
}
pQ->pfront = Null;
pQ->prear = Null;
}

void ClearLinkedQueue(pLinkedQueue pQ)
{
pNode p = pQ->pfront->pNext;
pNode q = Null;
while(p != Null)
{
q = p;
p = p->pNext;
free(q);
}
pQ->pfront->pNext = Null;
pQ->prear = pQ->pfront;
}

Status GetLinkedQueueHead(pLinkedQueue pQ, ElemType *e)
{
if (IsLinkedQueueEmpty(pQ))
{
printf("The linked queue is empty.\n");
return ERROR;
}
*e = pQ->pfront->pNext->data;
return NORMAL;
}

int GetLinkedQueueLength(pLinkedQueue pQ)
{
if (IsLinkedQueueEmpty(pQ))
{
return 0;
}
int Count = 0;
pNode pTemp = pQ->pfront;

while(pTemp->pNext != Null)
{
Count++;
pTemp = pTemp->pNext;
}
return Count;
}

Status QueueTraverse(pLinkedQueue pQ, void(*func)(ElemType*))
{
pNode pTemp = pQ->pfront->pNext;
while(pTemp != Null)
{
func(&pTemp->data);
pTemp = pTemp->pNext;
}
return NORMAL;
}

Bool InvertLinkedQueue_Static(pLinkedQueue pQ)
{
pStaticStack pSS = (pStaticStack)malloc(sizeof(StaticStack));
if (NORMAL != InitStaticStack(pSS))
{
return False;
}

ElemType V;
while(!IsLinkedQueueEmpty(pQ))
{
DeLinkedQueue(pQ, &V);
PushStaticStack(pSS, V);
}

while(!IsStaticStackEmpty(pSS))
{
PopStaticStack(pSS, &V);
EnLinkedQueue(pQ, V);
}
DestoryStaticStack(pSS);
return True;
}

Bool InvertLinkedQueue_Dynamic(pLinkedQueue pQ)
{
pDynamicStack pDS = (pDynamicStack)malloc(sizeof(DynamicStack));
if (NORMAL != InitDynamicStack(pDS))
{
return False;
}

ElemType V;
while(!IsLinkedQueueEmpty(pQ))
{
DeLinkedQueue(pQ, &V);
PushDynamicStack(pDS, V);
}

while(!IsDynamicStackEmpty(pDS))
{
PopDynamicStack(pDS, &V);
EnLinkedQueue(pQ, V);
}
DestoryDynamicStack(pDS);
return True;
}

不定长链表队列C语言实现