栈
栈：一种特殊的线性表，其中允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一段称为栈顶，另一端称为栈底，栈中的数据元素遵守后进先出的原则
- LIFO(lost in first out)
压栈：栈的插入操作叫进栈\压栈\入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈，出数据也在栈顶
栈的实现
栈的实现一般可以使用数组或者链表，相比较而言数组的结构实现更优一些，数组在尾部插入数据代价较小
这里简单讲一下，在数据结构中的栈与计算机组成原理中的栈是不同的，是俩个不同学科的内容。
stack.h文件
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> //静态栈 //typedef int SLDataType; //#define N 10 //typedef struct stack //{ // SLDataType SL[N]; // int top; //}stack; //动态栈 typedef int SLDataType; typedef struct stack { SLDataType* SL; //栈顶 int top; //容量 int capacity; }stack; //初始化栈 void StackInit(stack* ps); //销毁栈 void StackDestory(stack* ps); //入栈 void StackPush(stack* ps,SLDataType x); //出栈 void StackPop(stack* ps); //获取栈顶元素 SLDataType StackTop(stack* ps); //获取栈中有效元素个数 int StackSize(stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(stack* ps);
stack.c文件
#include"stack.h" //初始化栈 void StackInit(stack* ps) { ps->SL = (SLDataType*)malloc(sizeof(SLDataType) * 5); if (ps == NULL) { perror("malloc fail"); return; } ps->capacity = 5; ps->top = 0; } //销毁栈 void StackDestory(stack* ps) { assert(ps); free(ps->SL); ps->SL = NULL; ps->capacity = 0; ps->top = 0; } //入栈 void StackPush(stack* ps, SLDataType x) { assert(ps); if (ps->top == ps->capacity) { SLDataType* p = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity * 2); if (p == NULL) { perror("malloc fail"); return; } ps->SL = p; p = NULL; ps->capacity *= 2; } ps->SL[ps->top] = x; ps->top++; } //出栈 void StackPop(stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } //获取栈顶元素 SLDataType StackTop(stack* ps) { assert(ps); return ps->SL[(ps->top) - 1]; } //获取栈中有效元素个数 int StackSize(stack* ps) { assert(ps); return ps->top - 1; } // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(stack* ps) { assert(ps); return (ps->top == 0); }
队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先出先进FIFO(First in First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为对头
一端插入一端删除
队列的实现
队列的实现一般使用链表的形式
queue.h文件
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; //小环境：使用单链表形式表示队列 typedef struct QListNode { QDataType data; struct QListNode* next; }QNode; //大环境：表示队列结构 typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; //队列初始化 void QueueInit(Queue* q); //队列销毁 void Queuedestory(Queue* q); //队尾入队列 void QueuePush(Queue* q,QDataType x); //队头出队列 void QueuePop(Queue* q); //获取队列头元素 QDataType QueueFront(Queue* q); //获取队列尾元素 QDataType QueueBack(Queue* q); //获取队列中有效元素个数 int QueueSize(Queue* q); //检查是否为空 bool QueueEmpty(Queue* q);
queue.c文件
#include"queue.h" //队列初始化 void QueueInit(Queue* q) { assert(q); q->head = NULL; q->tail = NULL; q->size = 0; } //队尾入队列 void QueuePush(Queue* q, QDataType x) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->next = NULL; newnode->data = x; if (q->head == NULL && q->tail == NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } q->size++; } //队头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->head->next == NULL) { free(q->head); q->head = q->tail = NULL; } else { QNode* cur = q->head; q->head = cur->next; free(cur); cur = NULL; } q->size--; } //获取队列头元素 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->head->data; } //获取队列尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->tail->data; } //获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); return q->size; } //检查是否为空 bool QueueEmpty(Queue* q) { assert(q); return q->head == NULL; } //队列销毁 void Queuedestory(Queue* q) { assert(q); QNode* cur = q->head; while (cur) { q->head = cur->next; free(cur); cur = q->head; } cur = NULL; q->head = NULL; q->tail = NULL; q->size--; }
