目录

一.栈和队列的概念

?1.栈的概念：?

?2.队列的基本概念?

二.栈和队列的基本操作

?1.栈的基本操作?

初始化

入栈 

出栈

获取栈顶元素

获取栈元素个数

判空

销毁

?2.队列的基本操作?

初始化

入队

出队

获取队头元素

获取队尾元素

获取元素个数

判空

销毁

---

?一.栈和队列的概念?

?1.栈的概念：?

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底 。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作称为进栈/压栈/入栈。插入数据在栈顶插入 出栈：栈的删除操作称为出栈。删除数据也在栈顶删除

栈的实现：栈的实现有数组和链表两种方式，相对而言数组的结构实现更优一些，因为数组在尾部插入数据更加方便和高效

?2.队列的基本概念?

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾 出队列：进行删除操作的一端称为 队头

 

 

队列的实现：队列的实现有数组和链表两种方式，使用链表的结构更优一些，因为其头出数据更加方便和高效，而数组头出数据效率较低

?二.栈和队列的基本操作?

?1.栈的基本操作?

        栈采用数组实现更优，栈的基本操作有初始化、入栈、出栈、返回栈顶元素、获取栈元素个数、判空、销毁等操作

数组实现：

typedef int STDataType; typedef struct Stack{STDataType* a;int top;//栈顶元素的下一个位置int capacity;//栈的最大容量}Stack;

初始化

        栈的初始化需要给栈开辟一定的空间，top指针为栈顶元素的下一个元素，一开始栈没有元素，故将top置为0，然后给capacity一个值，这里我们设定为4，后续空间不够时再动态扩容

void StackInit(Stack* ps){assert(ps);ps->a = (STDataType *)malloc(sizeof(STDataType)*4);//申请空间if (ps->a ==NULL)//申请失败则报错{perror("error:ps->a");return;}ps->top = 0;//栈顶指向当前元素的下一个位置ps->capacity = 4;//初始容量为4}

入栈 

        栈的入栈步骤：首先判断栈是否已满，若栈满则需要扩容，这里我们将最大容量翻倍，即增容为原来容量的2倍，扩容后再将值赋给top位置，top加1，若栈未满则直接将值赋给top位置，top加1

void StackPush(Stack* ps, STDataType data ){assert(ps);if (ps->top >= ps->capacity)//栈顶下标大于最大容量则扩容{ps->capacity = ps->capacity * 2;//容量翻倍ps->a = (STDataType*)realloc(ps->a, ps->capacity*sizeof(STDataType));}ps->a[ps->top++] = data;//元素入栈，栈顶指针+1}

出栈

        栈的出栈步骤为：首先判断栈是否为空，为空则不能出栈，直接报错，若栈不为空则将top减1即可

void StackPop(Stack* ps){assert(ps);assert(ps->top != 0);//栈为空则直接报错ps->top--;//出栈，即将栈顶指针减1}

获取栈顶元素

        获取栈顶元素首先需要判断栈是否为空，若栈为空则直接报错，若栈不为空，因为top为栈顶元素的下一个位置，故栈顶元素下标为top-1，返回top-1下标的值即可

STDataType StackTop(Stack* ps){assert(ps);assert(ps->top != 0);//栈为空则直接报错return ps->a[ps->top - 1];//返回栈顶元素}

获取栈元素个数

        由于top为栈顶元素的下一个位置，故其值就为栈元素的个数，将其返回即可

int StackSize(Stack* ps){assert(ps);return ps->top;//返回栈顶指针}

判空

        栈的判空只需判断top是否为0，如果为0则说明栈没有元素即栈空，返回真，若不为0说明栈有元素即栈不为空，返回假

int StackEmpty(Stack* ps){assert(ps);if (ps->top == 0)//栈顶指针为0则说明栈空return 1;return 0;}

销毁

        栈的销毁只需将在堆上申请的数组空间给释放，然后指向该空间的指针置空，栈的top和最大容量置为0

void StackDestroy(Stack* ps){assert(ps);free(ps->a);//释放指针指向的空间ps->a = NULL;ps->top  = ps->capacity = 0;}

?2.队列的基本操作?

        队列由单链表实现结构更优，由于队列有队头和队尾两个指针，故我们用一个结构体将两个指针封装起来，队列的基本操作有初始化、入队、出队、获取队头元素、获取队尾元素、获取队列元素个数、判空、销毁等操作

单链表实现：

typedef int QDataType;typedef struct QListNode{struct QListNode* next;QDataType data;}QNode;// 队列的结构 typedef struct Queue{QNode* front;QNode* rear;}Queue;

初始化

        队列的初始化只需将两个指针都置为空即可

void QueueInit(Queue* q){assert(q);//队头和队尾指针置为空q->front = NULL;q->rear = NULL;}

入队

        队列的入队步骤：首先新建一个节点，再判断是否是第一次入队，即如果队列为空，则让队头和队尾指针都指向该节点，如果队列不为空，则类似于链表的尾插，将队尾指针rear指向的节点的next指向新节点，再将队尾指针rear指向新节点，即实现入队

void QueuePush(Queue* q, QDataType data){assert(q);QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的节点newnode->data = data;if (q->rear ==NULL)//如果队列为空队列，则让队头和队尾都指向该新节点{q->rear = q->front = newnode;}else{//不为空则将新节点进行尾插操作q->rear->next = newnode;q->rear = newnode;}}

出队

        队列的出队步骤：首先判断队列是否为空，为空则直接报错，再判断队列是否只有一个元素，只有一个元素则将该元素删除，队头和队尾指针置为空，如果队列不只有一个元素，则类似于单链表的头删，定义一个临时指针指向队头元素，然后让队头指针往后走一步，再删除临时指针指向的元素即可

void QueuePop(Queue* q){assert(q);assert(q->rear != NULL);//队列为空则报错if (q->rear == q->front)//如果队列只有一个元素，则将该元素出列，队头队尾指针置为空{free(q->front);q->rear = q->front = NULL;}else{//如果队列不只有一个元素，则进行出列操作，即头删操作QNode* cur = q->front;q->front = q->front->next;free(cur);}}

获取队头元素

        获取队头元素首先判断队头指针是否为空，为空则返回空，否则则直接返回队头指针指向的元素

QDataType QueueFront(Queue* q){assert(q);if (q->front == NULL)return NULL;return q->front->data;//返回队头指针指向的元素值}

获取队尾元素

        获取队尾元素首先判断队尾指针是否为空，为空则返回空，不为空则直接返回队尾指针指向的元素

QDataType QueueBack(Queue* q){assert(q);if (q->rear == NULL)return NULL;return q->rear->data;//返回队尾指针指向的元素值}

获取元素个数

        获取元素个数首先判断队列是否为空，为空则返回0，不为空则定义一个遍历指针，从队头遍历到队尾，遍历该队列统计元素个数即可

int QueueSize(Queue* q){assert(q);if (q->rear == NULL)//队列为空则返回空return 0;QNode* cur = q->front;//定义遍历指针int num = 1;//统计元素个数while (cur != q->rear)//遍历统计元素个数{num++;cur = cur->next;}return num;}

判空

        队列的判空只需判断队头指针等于队尾指针且都为空即可，若是则队列为空，否则不为空

int QueueEmpty(Queue* q){assert(q);if((q->front == q->rear) && (q->front == NULL))//队头队尾指针相等且都为空则队列为空return 1;return 0;}

销毁

        队列的销毁首先判断队列是否为空，为空则直接返回，不为空则定义遍历指针，从队头遍历到队尾依次删除节点即可，最后将队头和队尾指针置空即可

void QueueDestroy(Queue* q){assert(q);if (QueueEmpty(q))//队列为空则直接返回return;if (q->front == q->rear)//队列只有一个元素，删除这个元素，将两个指针置空{free(q->front);q->front = q->rear = NULL;}else{QNode* cur = q->front;//定义临时指针while (cur != q->rear)//遍历删除元素{q->front = q->front->next;free(cur);cur = q->front;}free(q->rear);//删除队尾q->front = q->rear = NULL;//两个指针置空}}

好啦，栈和队列就先学习到这，如果对您有所帮助，欢迎一键三连~

种一棵树最好的时间是十年前，其次是现在