数据结构 - 顺序队的基本操作(C语言)

淡淡的烟草味﹌ 2022-06-04 10:35 195阅读 0赞

**队列定义**：只允许在表的一端插入，另一端删除的限定性线性表。并且把允许插入的一端叫队尾(rear),把允许删除的一端叫队头(front)。

**特点**：先进先出。

当然，队列也有顺序存储和链式存储两种。现在，我们先来看看顺序存储结构的队列。

队列的顺序实现需要注意的几点：

(1)：利用一维数组作队列的顺序存储结构。并设立一个指向对头的指针front,一个指向队尾的指针rear。

(2)：入队：rear++；出队：front++。

(3)：约定：在非空队列中，头指针front总是指向队列中实际队头元素的前面一个位置。

以此它的存储结构如下：

typedef int DataType;
    
    typedef struct
    {
    	DataType data[MAXSIZE];
    	int rear,front;
    }SeQueue;

然而，这样便出现了'假溢出'现象：队尾指针已经移到最后，再有元素入队就会出现溢出，而事实上并未'满员'。解决假溢出现象就是循环队列，充分利用。下篇文章会给出。

顺序队的代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <windows.h>
    
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 100
    
    typedef int DataType;
    
    typedef struct
    {
    	DataType data[MAXSIZE];
    	int rear,front;
    }SeQueue;
    
    void Init_SeQueue(SeQueue *sq);		/*顺序队的初始化*/
    
    int Empty_SeQueue(SeQueue *sq);		/*判空*/
    
    int IsFull_SeQueue(SeQueue *sq);	/*判满*/ 
    
    int Push_SeQueue(SeQueue *sq,DataType x);	/*入队*/
    
    DataType Pop_SeQueue(SeQueue *sq);	 /*出队*/
    
    void Print_SeQueue(SeQueue *sq);	/*打印*/ 
    
    int main()
    {
    	SeQueue *sq = (SeQueue*)malloc(sizeof(SeQueue));
    	
    	/*---------------顺序队的初始化-----------*/ 
    	Init_SeQueue(sq);
    	
    	/*----------------入队并打印--------------*/ 
    	DataType x;
    	printf("请输入队内元素，按-1结束：");
    	scanf("%d",&x);
    	while(x!=-1){
    		if(Push_SeQueue(sq,x)==FALSE){
    			printf("System Error!\n");
    			break; 
    		}
    	scanf("%d",&x);
    	}
    	printf("\n入队后队内元素如下：");
    	Print_SeQueue(sq);
    	
    	/*----------------出队并打印--------------*/ 
    	printf("\n正在出队");
    	for(int i=0;i<=2;i++){
    		Sleep(400);
    		printf(".");
    	}
    	x = Pop_SeQueue(sq);
    	if(x==FALSE){
    		printf("System Error!\n");
    	}
    	else printf("队头元素为：%d\n\n",x);
    	
    	return 0;
    }
    
    void Init_SeQueue(SeQueue *sq)	/*顺序队的初始化*/
    {
    	sq->rear = sq->front = -1;	/*初始化队时,空队列的front=rear=-1*/ 
    }
    
    int Empty_SeQueue(SeQueue *sq)		/*判空*/ 
    {
    	if(sq->rear == sq->front) return FALSE;
    	else return TRUE;
    }
    
    int IsFull_SeQueue(SeQueue *sq)		/*判满*/
    {
    	if(sq->rear - sq->front == MAXSIZE) return FALSE;
    	else return TRUE;
    }
    
    int Push_SeQueue(SeQueue *sq,DataType x)	/*入队.*/
    {
    	if(IsFull_SeQueue(sq)==TRUE){
    		sq->data[++sq->rear] = x; 	/*队尾指针加1*/
    		return TRUE;
    	}
    	else return FALSE;
    }
    
    DataType Pop_SeQueue(SeQueue *sq)	 /*出队*/
    {
    	if(Empty_SeQueue(sq)==TRUE){
    		return sq->data[sq->rear--];	/*队头指针加1*/ 
    	}
    	else return FALSE; 
    }
    
    void Print_SeQueue(SeQueue *sq)		/*打印*/
    {
    	int i=0;
    	for(i=sq->front+1;i<=sq->rear;i++){
    		printf("%d ",sq->data[i]);
    	}
    	printf("\n");
    }

运行结果如下：

![20171211221614780][]

[20171211221614780]: /images/20220604/cec06ac339ab40cf8c5eef5072750ccf.png