概念

• 操作受限的线性表，其插入和删除操作在表的异端进行，而且只能在端点操作
• 特点：先进先出（FIFO)
• 队头：能够被删除的一端称为队头
• 队尾：能够插入的一端称为队尾

顺序队列

• 顺序存储的队列称为顺序队列

• 顺序队列的组成

  • 一个连续存储的内存，用于存放整个队列中的元素
  • 两个变量分别记录队头和队尾所在的元素下标

• 缺点：存在假溢满现象

  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aDfxXRuP-1691582951366)(C:\Users\无实的谎言花\Desktop\上海\数据结构\图片\假溢满现象.png)]

• 循环顺序队列

• 用于解决假溢满现象

队列结构体类型

typedef int datatype;
typedef struct
{datatype data[MAX];            //存储队列的数组容器int front;                  //记录对头所在元素的下标int tail;                    //记录最后一个元素的下一个位置的下标
}QUeue, *QueuePtr;

创建循环队列

/*
函数功能：在堆区申请一个队列的大小，队头和队尾同时指0
函数参数：无
函数返回值：成功：返回队列地址  失败：NULL
*/
QueuePtr queue_create() 
{ //创建一个循环顺序队列 QueuePtr Q = (QueuePtr)malloc(sizeof(Queue)); if(NULL == Q) { printf("队列创建失败\n"); return NULL; } //初始化 Q->front = Q->tail = 0; printf("队列创建成功\n"); return Q; 
} 

判空、判满

/*
函数功能：判断队列是否为空
函数参数：队列首地址
函数返回值：传参异常：-1  为空：1  非空：0
*/
//判空
int queue_empty(QueuePtr Q) 
{ //判断逻辑 if(NULL == Q) { printf("所给队列不合法\n"); return -1; } //当队尾和队头在同一个位置为空return Q->front == Q->tail; 
} /*
函数功能：判断队列是否为满
函数参数：队列首地址
函数返回值：传参异常：-1  已满：1  未满：0
*/
int queue_full(QueuePtr Q) 
{ //判断逻辑 if(NULL == Q) { printf("所给队列不合法\n"); return -1; } //当队头和队尾相差1个空间为满return (Q->tail+1)%MAX == Q->front; 
}

入队

/*
函数功能：入队
函数参数：队列首地址，入队的数据
函数返回值：传参异常：0  成功：1
*/
int queue_push(QueuePtr Q, datatype e) 
{ //判断逻辑 if(NULL == Q || queue_full(Q)) { printf("入队失败\n"); return 0; } //入队逻辑：将数据放在队尾所在地方 Q->data[Q->tail] = e; //队尾后移 
// Q->tail = Q->tail + 1; Q->tail = (Q->tail+1)%MAX; printf("入队成功\n"); return 1; 
} 

遍历

/*
函数功能：遍历队列
函数参数：队列首地址
函数返回值：传参异常：0  成功：1
*/
void queue_show(QueuePtr Q) 
{ //判断逻辑 if(NULL==Q || queue_empty(Q)) { printf("遍历失败\n"); return ; } //开始遍历 printf("从队头到队尾元素分别是："); for(int i=Q->front; i!=Q->tail; i=(i+1)%MAX ) { printf("%d\t", Q->data[i]); } printf("\n"); 
} 

出队

/*
函数功能：将队头所在的位置元素删除，然后队头后移
函数参数：队列首地址
函数返回值：传参异常：0  成功：1
*/
int queue_pop(QueuePtr Q) 
{ //判断逻辑 if(NULL==Q || queue_empty(Q)) { printf("出队失败\n"); return 0; } //出队逻辑 printf("%d出队成功\n", Q->data[Q->front]); //队头后移 Q->front = (Q->front+1)%MAX; return 1; 
}

求队列长度

/*
函数功能：算出队列的长度
函数参数：队列首地址
函数返回值：传参异常：0  成功：1
*/
int queue_size(QueuePtr Q) 
{ //判断逻辑 if(NULL==Q) { printf("所给链表不合法\n"); return -1; } return (Q->tail + MAX - Q->front)%MAX; 
} 

释放队列

/*
函数功能：释放队列
函数参数：队列首地址
函数返回值：无
*/
void queue_free(QueuePtr Q) 
{ //判断逻辑 if(NULL != Q) { free(Q); Q =NULL; printf("释放成功\n"); return; } printf("所给队列不合法\n"); return; 
} 

链式队列

队列结构体类型

typedef int datatype;//定义节点类型
typedef struct Node
{union{datatype data;int len;};struct Node *next;
}Node;//定义链队
typedef struct
{Node *Head;Node *tail;
}LinkQueue, *LinkQueuePtr;

创建链式队列

*
函数功能：在堆空间中申请一个队列，再申请一个链表 
函数参数：无
函数返回值：失败：NULL  成功:队列首地址
*/
LinkQueuePtr list_create()
{//创建一个队列LinkQueuePtr LQ = (LinkQueuePtr)malloc(sizeof(LinkQueue));if(NULL == LQ){puts("创建失败");return NULL;}//创建成功的话，说明里面有两个指针//申请一个链表，将Head指针指向头节点LQ->Head = (Node*)malloc(sizeof(Node));if(NULL == LQ->Head){puts("指针创建失败");return NULL;}//成功后需要对链表初始化LQ->Head->len = 0;LQ->Head->next = NULL;//将尾指针指向头节点LQ->tail = LQ->Head;puts("创建成功");return LQ;
}

判空

/*
函数功能：判空
函数参数：队列首地址
函数返回值：传参异常:-1  为空：1  非空：0
*/
int list_empty(LinkQueuePtr LQ)
{//判断逻辑if(NULL == LQ || NULL == LQ->Head){puts("memory error");return -1;}return LQ->Head == LQ->tail;
}

入队

/*
函数功能：申请一个节点封装数据后，入队
函数参数：队列首地址，要插入数据
函数返回值：传参异常:-1 节点创建失败：-2 成功：0
*/
int list_push(LinkQueuePtr LQ, datatype value)
{//判断逻辑if(NULL == LQ){puts("memory error");return -1;}//申请节点Node* q = (Node*)malloc(sizeof(Node));if(NULL == q){puts("入队失败");return -2;}//数据封装q->data = value;q->next = NULL;//入队逻辑LQ->tail->next = q;LQ->tail = q;LQ->Head->len++;puts("入队成功");return 0;}

遍历

/*
函数功能：遍历队列
函数参数：队列首地址
函数返回值：传参异常:-1 成功：0
*/
int list_show(LinkQueuePtr LQ)
{if(NULL == LQ || list_empty(LQ)){puts("出队失败");return -1;}Node *q = LQ->Head->next;while(q != NULL){printf("%d\t", q->data);q = q->next;}puts("");return 0;
}

出队

/*
函数功能：出队
函数参数：队列首地址
函数返回值：传参异常:-1 成功：0
*/
int list_pop(LinkQueuePtr LQ)
{if(NULL == LQ || list_empty(LQ)){puts("出队失败");return -1;}//头删Node* p = LQ->Head->next;LQ->Head->next = p->next;free(p);p = NULL;//表长自减LQ->Head->len--;//判空,尾指针归位，否则多删会段错误if(LQ->Head->next == NULL){LQ->tail = LQ->Head;}puts("出队成功");return 0;
}

销毁

/*
函数功能：释放队列
函数参数：队列首地址
函数返回值：传参异常:-1 成功：0
*/
int list_free(LinkQueuePtr LQ)
{//判断逻辑if(NULL == LQ){puts("销毁失败");return -1;}//队内数据全部出队while(!list_empty(LQ)){list_pop(LQ);}//释放链表头节点free(LQ->Head);LQ->Head = LQ->tail = NULL;//释放队列free(LQ);LQ = NULL;puts("释放成功");return 0
}

概念

• 操作受限的线性表，对该容器的插入和删除操作只能在同一端进行
• 栈顶：能够操作的一端，称为栈顶
• 栈底：不能被操作的一端，称为栈底
• 栈的特点：先进后出（FILO），后进先出（LIFO）
• 分类：顺序栈，链式栈
• 基本操作：创建栈，判空，判满，入栈，出栈，获取栈顶元素、求栈大小、遍历栈、销毁栈

顺序栈

• 概念：顺序存储的栈叫顺序栈

• 特点：使用一片连续的存储空间，来存储一个栈，但是除了存储栈的容器外，还需要一个记录栈顶元素下标的变量

• 结构体类型

  •   #define MAX 8typedef int datatype;typedef struct{datatype *data;     //指向堆区空间，用于存储栈的容器int top;                //记录栈顶元素的下标}Stack, *StackPtr;

创建栈

/*
函数功能：在堆区申请一个顺序栈
函数参数：void
函数返回值：失败：NULL 成功：栈空间首地址
*/
StackPtr stack_create()
{//在堆区申请一个顺序栈的大小StackPtr S = (StackPtr)malloc(sizeof(Stack));if(NULL == S){puts("Stack malloc file");return NULL;}//给栈中的连续空间申请内容S->data = (datatype *)malloc(sizeof(datatype)*MAX);if(NULL == S->data){puts("Data malloc file");free(S);return NULL;}//初始化S->top = -1;puts("Stack create complete");return S;
}

判空

/*
函数功能：栈空间判空
函数参数：栈首地址
函数返回值：传参异常：-1 非空：0  为空：1
*/
int stack_empty(StackPtr S)
{if(NULL == S){puts("memory error");return -1;}return S->top == -1;
}

判满

/*
函数功能：栈空间判满
函数参数：栈首地址
函数返回值：传参异常：-1 未满：0  已满：1
*/
int stack_full(StackPtr S)
{if(NULL == S){puts("memory error");return -1;}return S->top == MAX-1;
}

入栈

/*
函数功能：栈空间插入数据
函数参数：栈首地址，要插入的数据
函数返回值：传参异常：-1 成功：0
*/
int stack_push(StackPtr S, datatype value)
{if(NULL == S || stack_full(S)){puts("memory error");return -1;}//先加后压S->top++;S->data[S->top] = value;//将数据存放到栈中puts("入栈成功");printf("%d\n", S->top);return 0;
}

遍历栈

/*
函数功能：遍历栈
函数参数：栈首地址
函数返回值：传参异常：-1 成功：0
*/
int stack_show(StackPtr S)
{if(NULL == S || stack_empty(S)){puts("memory error");return -1;}int i = S->top;while(i != -1){printf("%d\t", S->data[i]);i--;}puts("");return 0;
}

出栈

/*
函数功能：出栈
函数参数：栈首地址
函数返回值：传参异常：-1 成功：0
*/
int stack_pop(StackPtr S)
{if(NULL == S || stack_empty(S)){puts("memory error");return -1;}S->data[S->top] = 0;S->top--;puts("出栈成功");return 0;
}

获取栈顶元素

/*
函数功能：获取栈顶元素
函数参数：栈首地址
函数返回值：传参异常：NULL 成功：栈顶元素地址
*/
datatype *stack_top(StackPtr S)
{if(NULL == S || stack_empty(S)){puts("memory error");return NULL;}return &S->data[S->top];
}

求栈大小

/*
函数功能：求栈大小
函数参数：栈首地址
函数返回值：传参异常：-1 成功：栈大小
*/
int stack_size(StackPtr S)
{if(NULL == S || stack_empty(S)){puts("memory error");return -1;}return S->top+1;
}

销毁栈

/*
函数功能：销毁栈
函数参数：栈首地址
函数返回值：传参异常：-1 成功：0
*/
int stack_free(StackPtr S)
{if(NULL == S){puts("memory error");return -1;}free(S->data);S->data = NULL;free(S);S = NULL;puts("释放成功");return 0;
}

链式栈

• 链式存储的栈
• 实现方式：单向链表
  • 对单向链表进行头插（入栈）、头删（出栈），此时链表的头部就是链栈的栈顶，链表的尾部，就是链栈的栈底
• 本质就是单链表只进行头插和头删

构建栈结构体

typedef int datatype;//定义栈结构体
typedef struct Node
{union{datatype data;int top;};struct Node* next;
} LinkStack, *LinkStackPtr;

创建栈

/*
函数功能：在堆区空间申请一个栈空间的头节点
函数参数：void
函数返回值：成功：栈空间首地址  失败：NULL
*/
LinkStackPtr stack_create()
{//在堆空间申请一片空间作为栈的头节点LinkStackPtr LS = (LinkStackPtr)malloc(sizeof(LinkStack));if(NULL == LS){puts("创建失败");return NULL;}//头节点的初始化LS->top = -1;LS->next = NULL;return LS;
}

判空

/*
函数功能：判断栈空间是否为空
函数参数：栈空间的头节点地址
函数返回值：传参异常：-1  非空：0  为空：1
*/
int stack_empty(LinkStackPtr LS)
{//判断逻辑if(NULL == LS){puts("栈非法");return -1;}//当top为-1意味着栈为空return LS->top == -1;
}

入栈

/*
函数功能：讲数据封装进入节点，入栈
函数参数：栈空间的头节点地址，需要封装的数据
函数返回值：传参异常：-1  封装失败：-2  成功：0
*/
int stack_push(LinkStackPtr LS, datatype value)
{if(NULL == LS){puts("栈非法");return -1;}LinkStackPtr p = (LinkStackPtr)malloc(sizeof(LinkStack));if(NULL == p){puts("创建失败");return -2;}p->data = value;//头插p->next = LS->next;LS->next = p;puts("入栈成功");LS->top++;return 0;
}

出栈

/*
函数功能：出栈，将top位置的数据移除
函数参数：栈空间的头节点地址
函数返回值：传参异常：-1  成功：0
*/
int stack_pop(LinkStackPtr LS)
{//判断逻辑if(NULL == LS || stack_empty(LS)){puts("出栈失败");return -1;}//单链表头删LinkStackPtr p = LS->next;LS->next = LS->next->next;//释放节点printf("%d出栈完成\n", p->data);free(p);p = NULL;//top变化LS->top--;return 0；
}

遍历

/*
函数功能：遍历栈空间，并输出
函数参数：栈空间的头节点地址
函数返回值：传参异常：-1  成功：0
*/
int stack_show(LinkStackPtr LS)
{//判断逻辑if(NULL == LS || stack_empty(LS)){puts("遍历失败");return -1;}//创建一个临时指针，从第一个节点遍历栈LinkStackPtr q = LS->next;//遍历逻辑while(q != NULL){printf("%d\t", q->data);q = q->next;}puts("");puts("遍历完成");return 0;
}

释放栈

/*
函数功能：将整个栈空间释放销毁
函数参数：栈空间的头节点地址
函数返回值：传参异常：-1  成功：0
*/
//释放栈
int stack_free(LinkStackPtr LS)
{//判断逻辑if(NULL == LS){puts("释放失败");return -1;}//创建一个临时指针遍历栈空间LinkStackPtr q = LS->next;while(q != NULL){//循环出栈stack_pop(LS);q = q->next;}//将剩余的头节点释放，置NULLfree(LS);LS = NULL;puts("释放完成");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！