数据结构~10.顺序队和链队

本文是上一篇文章的后续,详情点击该连接~

顺序队

循环队列

       在顺序队中,一般让队尾指针rear指向刚进队的元素位置,让队首指针front指向刚出队的元素位置。所以,元素进队的时候,rear要向后移动:元素出队的时候,front也要向后移动。这样通过一系列的出队和进队操做之后,两个指针最终会达到数组末端MAXSIZE - 1 处。虽然队中已经没有元素,但仍然没法让元素进队,这就是所谓的 "假溢出"。要解决这个问题,咱们能够把数组弄成一个环，让rear和front绕着一个环走,这样就永远不会出现二者来到数组尽头没法继续往下走的状况。web

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//顺序队的定义
typedef struct { 
 
  
	int data[MAXSIZE];
	int front;				//队首指针
	int rear;				//队尾指针
}SqQueue;					//顺序队结点类型定义

//初始化操做
void initQueue(SqQueue &list) { 
 
  
	//队首和队尾指针重合而且指向0
	list.front = list.rear = 0;
}

//判断队空算法
int isEmpty(SqQueue list) { 
 
  
	//不论队首和队尾在哪一个位置,重合便是空
	return list.front == list.rear ? 1 : 0;
}

//进队算法
int push(SqQueue &list,int x) { 
 
  
	//假如队满,则不能进队
	if ((list.rear + 1) % MAXSIZE == list.front) { 
 
  
		return 0;
	}
	//若是没满就先移动指针
	list.rear = (list.rear + 1) % MAXSIZE;
	//存入元素
	list.data[list.rear] = x;
	return 1;
}

//出队算法
int pop(SqQueue &list) { 
 
  
	//若是队列空,则不能出队
	if (isEmpty(list) == 1) { 
 
  
		return 0;
	}
	//若是队列不空,就先移动指针
	list.front = (list.front + 1) % MAXSIZE;
	//取出元素
	return list.data[list.front];
}

//遍历
void Print(SqQueue list) { 
 
  
	int i;
	for (i = list.front + 1; i <= list.rear; i++) { 
 
  
		//判断是否到了最后
		if (i != list.rear) { 
 
  
			printf("%d -> ",list.data[i]);
		}
		else { 
 
  
			printf("%d\n",list.data[i]);
		}
	}
}

int main(int argc,char *argv[]) { 
 
  
	SqQueue list;
	initQueue(list);
	int i;
	for (i = 1; i < 10; i++) { 
 
  
		push(list,i);
	}
	Print(list);
	//出队
	int n = pop(list);
	printf("出队的元素: %d\n",n);
	Print(list);
	getchar();
}

链队

       链队就是采用链式存储结构存储队列,这里的话呢,就采用单链表来实现吧!链队的特色主要就是基本上不存在满的状况。算法

链队的状态

       队空状态数组

list->rear == NULL 或者 list->front == NULL

链队代码实现

#include<stdio.h>
#include<stdlib.h>
//链队定义
//队结点类型
typedef struct QNode { 
 
  
	int data;				//数据域
	struct QNode* next;		//指针域
}QNode;						//队结点类型定义
//链队类型定义
typedef struct { 
 
  
	QNode* front;			//队头指针
	QNode* rear;			//队尾指针
}LiQueue;					//链队类型定义

//初始化链队
void initQueue(LiQueue *&list) { 
 
  
	list = (LiQueue*)malloc(sizeof(LiQueue));
	list->front = list->rear = NULL;
}

//判断队空
int isEmpty(LiQueue *list) { 
 
  
	return (list->front == NULL || list->rear == NULL) ? 1 : 0;
}

//入队
void push(LiQueue *list,int x) { 
 
  
	QNode* p = (QNode*)malloc(sizeof(QNode));
	p->data = x;
	p->next = NULL;
	if (list->rear == NULL) { 
 
  
		//若是队列为空,那么新结点便是队尾也是队首
		list->front = list->rear = p;
	}
	else { 
 
  
		//将新结点链接到队尾,rear指向它
		list->rear->next = p;
		list->rear = p;
	}
}
//出队操做
int pop(LiQueue *list) { 
 
  
	QNode* p;
	int x;
	//队空不能出队
	if (list->rear == NULL) { 
 
  
		return 0;
	}
	else { 
 
  
		p = list->front;
	}
	//队列中只有一个结点时出队操做需特殊处理
	if (list->front == list->rear) { 
 
  
		list->front = list->rear = NULL;
	}
	else { 
 
  
		list->front = list->front->next;
	}
	x = p->data;
	free(p);
	return x;
}

//遍历操做
void Print(LiQueue *list) { 
 
  
	// 遍历
	QNode* temp = list->front;
	while (temp != NULL) { 
 
  
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

int main(int argc,char*argv[]) { 
 
  
	LiQueue* list;
	int n;
	//初始化
	initQueue(list);
	int i;
	//进队
	for (i = 1; i < 10; i++) { 
 
  
		push(list,i);
	}
	//遍历
	Print(list);
	//出队
	n = pop(list);
	printf("出队的值是: %d\n",n);
	Print(list);
	return 0;
}