数据结构（学习）2024.8.8（栈，队列）

今天学习的是线性表里面的栈和队列

链表的相关知识可以查看http://t.csdnimg.cn/NX464

顺序表的相关知识可以查看http://t.csdnimg.cn/5IMAZ

目录

栈

栈的定义

栈的特点

顺序栈

结构体

顺序栈的相关操作案例

链式栈

结构体

链式栈的相关操作案例

总结

队列

队列的定义

队列的特点

顺序队列(又称为循环队列)

结构体

顺序队列的相关操作案例

链式队列 

结构体

链式队列的相关操作案例

栈

栈的定义

        只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶，另一端称为栈底。

栈的特点

先进后出 FILO first in last out   LIFO

顺序栈

1.逻辑结构：线性结构
2.存储结构：顺序存储
3.操作：入栈、出栈

结构体

typedef struct seqstack
{
    int *data;  // 指向栈的存储位置
    int maxlen; // 保存栈的最大长度
    int top;    // 称为栈针，用的时候，心里面可以将按照顺序表里的last来使用， top 始终代表当前栈内最后一个有效元素的下标
} seqstack_t;

顺序栈的相关操作案例

头文件seqstack.h:

#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_
#include <stdio.h>
#include <stdlib.h>
typedef struct seqstack
{int *data;  // 指向栈的存储位置int maxlen; // 保存栈的最大长度int top;    // 称为栈针，用的时候，心里面可以将按照顺序表里的last来使用// top 始终代表当前栈内最后一个有效元素的下标
} seqstack_t;
// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len); // len代表的是创建栈的时候的最大长度
// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p);
// 3.入栈
int PushStack(seqstack_t *p, int data); // data代表入栈的数据
// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p);
// 5.出栈
int PopSeqStack(seqstack_t *p);
// 6. 清空栈
void ClearSeqStack(seqstack_t *p);
// 7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int GetTopSeqStack(seqstack_t *p);
// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p);
#endif

顺序栈函数seqstack.c:

#include "seqstack.h"// 1.创建一个空的栈
seqstack_t *CreateEpSeqStack(int len) // len代表的是创建栈的时候的最大长度
{// 1.开辟一个结构体类型大小的空间seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (p == NULL){perror("CreateEpSeqStack函数创建结构体失败");return NULL;}// 2.初始化p->top = -1;p->maxlen = len;p->data = (int *)malloc(len * sizeof(int));if (p->data == NULL){perror("CreateEpSeqStack函数创建数据空间失败");free(p);p = NULL;return NULL;}return p;
}// 2.判断是否为满,满返回1 未满返回0
int IsFullSeqStack(seqstack_t *p)
{return p->top == p->maxlen - 1;
}// 3.入栈
int PushStack(seqstack_t *p, int data) // data代表入栈的数据
{// 1.容错判断(判满)if (IsFullSeqStack(p)){perror("PushStack函数出错\n");return -1;}// 2.移动指针p->top++;// 3.入栈p->data[p->top] = data;return 0;
}// 4.判断栈是否为空
int IsEpSeqStack(seqstack_t *p)
{return p->top == -1;
}// 5.出栈
int PopSeqStack(seqstack_t *p)
{// 1.容错判断(判空)if (IsEpSeqStack(p)){perror("PopSeqStack函数出错\n");return -1;}// 2.移动指针p->top--;// 3.出栈数据return p->data[p->top + 1];
}// 6. 清空栈
void ClearSeqStack(seqstack_t *p)
{p->top = -1;
}// 7. 获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int GetTopSeqStack(seqstack_t *p)
{while (!IsEpSeqStack(p)){return p->data[p->top];}return -1;
}// 8. 求栈的长度
int LengthSeqStack(seqstack_t *p)
{return p->top + 1;
}

主函数main.c:

#include "seqstack.h"int main(int argc, char const *argv[])
{int data;seqstack_t *p = CreateEpSeqStack(5);PushStack(p, 1);PushStack(p, 2);PushStack(p, 3);printf("目前栈里的数据为：\n");for (int i = 0; i < LengthSeqStack(p); i++){printf("%d ", GetTopSeqStack(p));}printf("\n");printf("请输入你要插入的数据：\n");scanf("%d", &data);PushStack(p, data);printf("出栈操作：\n");while (!IsEpSeqStack(p)){printf("出栈的数据为：%d ", PopSeqStack(p));}printf("\n");free(p->data);p->data = NULL;free(p);p = NULL;return 0;
}

链式栈

1.逻辑结构：线性结构
2.存储结构：链式存储
3.操作：入栈、出栈

结构体

typedef struct linkstack
{
    datatype data;          // 数据域
    struct linkstack *next; // 指针域
} linkstack_t;

链式栈的相关操作案例

头文件linkstack.h:

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include <stdio.h>
#include <stdlib.h>
// 入栈和出栈只在第一个节点位置操作
typedef int datatype;
typedef struct linkstack
{datatype data;          // 数据域struct linkstack *next; // 指针域
} linkstack_t;// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop);
// 2.入栈   data是入栈的数据
// 参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，
// 那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data);
// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top);
// 4.出栈
datatype PopLinkStack(linkstack_t **ptop);
// 5.清空栈
void ClearLinkStack(linkstack_t **ptop); // 用二级指针，是因为清空后需要将main函数中的top变为NULL
// 6.求栈的长度
int LengthLinkStack(linkstack_t *top); // 用一级指针，是因为我只是求长度，不需要修改main函数中top指针的指向
// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top);
#endif

链式栈函数linkstack.c:

#include "linkstack.h"// 1.创建一个空的栈
void CreateEpLinkStack(linkstack_t **ptop)
{*ptop = NULL;
}// 2.入栈
// data是入栈的数据
// 参数上之所以采用二级指针，因为我们要随着入栈添加新的节点作为头，top需要永远指向当前链表的头，那么修改main函数中的top，我们采用地址传递
int PushLinkStack(linkstack_t **ptop, datatype data)
{// 1.创建一个新节点，并初始化linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));if (pnew == NULL){perror("PushLinkStack函数出错\n");return -1;}pnew->data = data;pnew->next = NULL;// 2.将新节点插到无头单向链表中pnew->next = *ptop;// 3.移动栈针，栈针永远指向无头单向链表的第一个节点*ptop = pnew;return 0;
}// 3.判断栈是否为空
int IsEpLinkStack(linkstack_t *top)
{return top == NULL;
}// 4.出栈     *ptop-->top
datatype PopLinkStack(linkstack_t **ptop)
{// 1.容错判断(判空)if (IsEpLinkStack(*ptop)){perror("PopLinkStack函数出错\n");return -1;}// 2.定义pdel指向被删除节点linkstack_t *pdel = *ptop;// 3.定义一个变量temp保存出栈数据datatype temp = pdel->data; // datatype temp = (*ptop)->data;// 4.移动指针*ptop = pdel->next; // *ptop = (*ptop)->next;// 5.释放被删除节点free(pdel);pdel = NULL;return temp;
}// 5.清空栈
void ClearLinkStack(linkstack_t **ptop) // 用二级指针，是因为清空后需要将main函数中的top变为NULL
{while (!(IsEpLinkStack(*ptop))){PopLinkStack(ptop);}
}// 6.求栈的长度
int LengthLinkStack(linkstack_t *top) // 用一级指针，是因为只是求长度，不需要修改main函数中top指针的指向
{int len = 0;while (top != NULL){top = top->next;len++;}return len;
}// 7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype GetTopLinkStack(linkstack_t *top)
{if (IsEpLinkStack(top)){perror("GetTopLinkStack函数出错\n");return -1;}return top->data;
}

主函数main.c:

#include "linkstack.h"int main(int argc, char const *argv[])
{linkstack_t *p = NULL;for (int i = 1; i <= 5; i++){PushLinkStack(&p, i);}printf("栈的长度为：%d\n", LengthLinkStack(p));while (!(IsEpLinkStack(p))){printf("%d ", PopLinkStack(&p));}printf("\n");ClearLinkStack(&p);return 0;
}

总结

顺序栈和链式栈的区别

(1)存储结构不同，顺序栈相当于数组，连续的，链式栈 链表非连续的 
(2)顺序栈的长度受限制，而链栈不会

队列

顺序队列(循环队列) 和 链式队列 

队列的定义

只允许在两端进行插入和删除操作的线性表，在队尾插入，在队头删除 插入的一端，被称为"队尾"，删除的一端被称为"队头"。

在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。

队列的特点

先进先出 FIFO  first in first out

后进后出 LILO  last

顺序队列(又称为循环队列)

1.逻辑结构: 线性结构

2.存储结构：顺序存储结构

3.操作：入列，出列

结构体

 #define N 5

typedef int datatype;

typedef struct

{

datatype data[N];

int rear;  //存数据端  rear 后面

int front; //取数据端  front 前面

}sequeue_t;//sequence 顺序  queue队列

 注意：

循环队列中，假设数组的元素个数为N，那么循环队列中存储最多的数据个数为N-1个

原因：舍去数组上的一个存储位置,用于判断队列是否为满

顺序队列的相关操作案例

头文件sequeue.h:

#ifndef _SEQUEUE_H_
#define _SEQUEUE_H_
#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef int datatype;
typedef struct
{datatype data[N]; // 循环队列的数组int rear;         // 存数据端 rear 后面int front;        // 取数据端 front 前面
} sequeue_t;
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue();
// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data);
// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p);
// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p);
// 5.出列
datatype OutSequeue(sequeue_t *p);
// 6.求队列的长度
int LengthSequeue(sequeue_t *p);
// 7.清空队列函数
void ClearSequeue(sequeue_t *p);
#endif

顺序队列函数sequeue.c:

#include "sequeue.h"
// 1.创建一个空的队列
sequeue_t *CreateEmptySequeue()
{// 1.开辟一个结构体大小的空间sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));if (p == NULL){perror("CreateEmptySequeue函数报错\n");return NULL;}// 2.初始化p->rear = p->front = 0;return p;
}// 2.入列 data代表入列的数据
int InSequeue(sequeue_t *p, datatype data)
{// 1.判满if (IsFullSequeue(p)){perror("InSequeue函数出错\n");return -1;}// 2.将数据入列p->data[p->rear] = data;p->rear = (p->rear + 1) % N;return 0;
}// 3.判断队列是否为满
int IsFullSequeue(sequeue_t *p)
{return (p->rear + 1) % N == p->front;
}// 4.判断队列是否为空
int IsEmptySequeue(sequeue_t *p)
{return p->rear == p->front;
}// 5.出列
datatype OutSequeue(sequeue_t *p)
{// 1.判空if (IsEmptySequeue(p)){perror("OutSequeue函数出错\n");return -1;}// 2.出列// 取出数据datatype temp = p->data[p->front];// 移动头指针p->front = (p->front + 1) % N;return temp;
}
// 6.求队列的长度
int LengthSequeue(sequeue_t *p)
{// // 1.方法一// if (p->rear >= p->front)// {//     return p->rear - p->front;// }// else// {//     return p->rear - p->front + N;// }// 2.方法二return (p->rear - p->front + N) % N;
}
// 7.清空队列函数
void ClearSequeue(sequeue_t *p)
{p->front = p->rear;
}

主函数main.c:

#include "sequeue.h"int main(int argc, char const *argv[])
{sequeue_t *p = CreateEmptySequeue();for (int i = 0; i < 4; i++){InSequeue(p, i);}printf("顺序队列的长度为：%d\n", LengthSequeue(p));OutSequeue(p);OutSequeue(p);OutSequeue(p);InSequeue(p, 10);printf("顺序队列的长度为：%d\n", LengthSequeue(p));while (!IsEmptySequeue(p)){printf("%d ", OutSequeue(p));}printf("\n");printf("清空顺序队列\n");ClearSequeue(p);free(p);p = NULL;return 0;
}

链式队列 

1.逻辑结构: 线性结构

2.存储结构：链式存储

3.操作：入列 、出列

结构体

typedef struct node

{

datatype data;//数据域

struct node *next;//指针域

}linkqueue_node_t,*linkqueue_list_t;

typedef struct//将队列头指针和尾指针封装到一个结构体里

{

linkqueue_list_t front;//相当于队列的头指针

linkqueue_list_t rear;//相当于队列的尾指针

//有了链表的头指针和尾指针，那么我们就可以操作这个链表

}linkqueue_t; 

链式队列的相关操作案例

头文件linkqueue.h:

#ifndef _LINKQUEUE_H_
#define _LINKQUEUQ_H_#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{datatype data;     // 数据域struct node *next; // 指针域
} linkqueue_node_t, *linkqueue_list_t;// linkqueue_list_t p === linkqueue_node_t *
typedef struct // 将队列头指针和尾指针封装到一个结构体里
{linkqueue_list_t front; // 相当于队列的头指针linkqueue_list_t rear;  // 相当于队列的尾指针// 有了链表的头指针和尾指针，那么我们就可以操作这个链表
} linkqueue_t;
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue();
// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data);
// 3.出列
datatype OutLinkQueue(linkqueue_t *p);
// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p);
// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p);
// 6.清空队列
void ClearLinkQueue(linkqueue_t *p);
#endif

链式队列函数linkqueue.c:

#include "linkqueue.h"
// 1.创建一个空的队列
linkqueue_t *CreateEmptyLinkQueue()
{// 1.创建存放头尾指针的空间linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));if (p == NULL){perror("CreateEmptyLinkQueue函数创建存放头尾指针的空间出错\n");return NULL;}// 2.初始化p->front = p->rear = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (p->front == NULL){perror("CreateEmptyLinkQueue函数创建链表结构体的空间出错\n");return NULL;}p->front->next = NULL;return p;
}// 2.入列 data代表入列的数据
int InLinkQueue(linkqueue_t *p, datatype data)
{// 1.开辟一个节点并初始化存放数据linkqueue_list_t pnew = (linkqueue_list_t)malloc(sizeof(linkqueue_node_t));if (pnew == NULL){perror("InLinkQueue函数出错\n");return -1;}pnew->next = NULL;pnew->data = data;// 2.数据入队p->rear->next = pnew;// 3.移动尾指针p->rear = pnew;return 0;
}// 3.出列
datatype OutLinkQueue(linkqueue_t *p)
{// 1.判空if (IsEmptyLinkQueue(p)){perror("OutLinkQueue函数出错\n");return -1;}// 2.出列数据// (1)定义pdel指向头节点linkqueue_list_t pdel = p->front;// (2)移动头指针p->front = p->front->next;// (3)释放头节点free(pdel);pdel = NULL;// (4)出队数据return p->front->data;
}// 4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_t *p)
{return p->rear == p->front;
}// 5.求队列长度的函数
int LengthLinkQueue(linkqueue_t *p)
{int len = 0;linkqueue_list_t q = p->front;while (q->next!= NULL){q = q->next;len++;}return len;
}// 6.清空队列
void ClearLinkQueue(linkqueue_t *p)
{while (!IsEmptyLinkQueue(p)){OutLinkQueue(p);}
}

主函数main.c：

#include "linkqueue.h"int main(int argc, char const *argv[])
{linkqueue_t *p = CreateEmptyLinkQueue();InLinkQueue(p, 1);InLinkQueue(p, 2);InLinkQueue(p, 3);printf("链式队列的长度为：%d\n", LengthLinkQueue(p));printf("%d ", OutLinkQueue(p));printf("%d ", OutLinkQueue(p));printf("%d ", OutLinkQueue(p));printf("\n");printf("清空链式队列\n");ClearLinkQueue(p);free(p->front);p->front = NULL;free(p);p = NULL;return 0;
}