c语言实现循环队列和链式队列

2017-08-25

c语言实现循环队列和链式队列。队列与栈不同，队列必须是先进先出(first in first out)，而栈是后进先出的(last in first out)。链式队列与单链表的区别是，链式队列不能随意的增加，删除，以及读取队列中间的某一个数据。

循环队列

front = rear表示队列空

(rear + 1) % MaxSize = front表示队列满

rear = 4 front =0 5的位置为空的储存单元，这个时候队列满

```typedef struct{
ElemType data[MaxSize];
int front, rear;
}SqQueue;

void InitQueue(SqQueue * Q);
int QueueEmpty(SqQueue Q);
int EnQueue(SqQueue * Q, ElemType e);
int DeQueue(SqQueue * Q, ElemType * e);
int GetHead(SqQueue * Q, ElemType * e);
int ElemNumber(SqQueue Q);
```

```void InitQueue(SqQueue * Q){
Q->front = Q->rear = 0;
}

int QueueEmpty(SqQueue Q){
if(Q.front == Q.rear) return 1;
return 0;
}

int EnQueue(SqQueue * Q, ElemType e){
if((Q->rear + 1) % MaxSize == Q->front){
printf("queue is full!");
return 0;}//队列满，牺牲一个存储单元
Q->data[Q->rear] = e;
Q->rear = (Q->rear+1) % MaxSize;
return 1;
}

int DeQueue(SqQueue * Q, ElemType * e){
if(QueueEmpty(* Q)) return 0;
* e = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
return 1;
}

int ElemNumber(SqQueue Q){
return ((Q.rear + MaxSize - Q.front) % MaxSize);
}
```

链式队列

```typedef struct LinkNode{
ElemType data;
typedef struct{

int EnListQueue(LinkQueue * Q, ElemType e);
int DeListQueue(LinkQueue * Q, ElemType * e);
```

```void InitListQueue(LinkQueue * Q){
Q->front->next = NULL;
}

if(Q.front == Q.rear) return 1;
return 0;
}

int EnListQueue(LinkQueue * Q, ElemType e){
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
return 1;
}

int DeListQueue(LinkQueue * Q, ElemType * e){
if(Q->front == Q->rear) return 0;
* e = p->data;
Q->front->next = p->next;
if(p == Q->rear) Q->front = Q->rear;//如果队列中只有一个节点，那么变为空
free(p);
return 1;
}
```

```int main(int argc, const char * argv[]) {
SqQueue Q;
InitQueue(& Q);
printf("front:%d,rear:%d\n", Q.front, Q.rear);
printf("Empty:%d\n",QueueEmpty(Q));
EnQueue(& Q, 1);
printf("front:%d,rear:%d\n", Q.front, Q.rear);
printf("Empty:%d\n",QueueEmpty(Q));
EnQueue(& Q, 2);
EnQueue(& Q, 3);
EnQueue(& Q, 4);
printf("front:%d,rear:%d\n", Q.front, Q.rear);
printf("Empty:%d\n",QueueEmpty(Q));
printf("ElemNumber:%d\n",ElemNumber(Q));
int e;
DeQueue(& Q, & e);
printf("DeNumber:%d\n",e);
printf("ElemNumber:%d\n",ElemNumber(Q));
printf("front:%d,rear:%d\n", Q.front, Q.rear);
EnQueue(& Q, 5);
printf("ElemNumber:%d\n",ElemNumber(Q));
printf("front:%d,rear:%d\n", Q.front, Q.rear);
return 0;
}
```