初阶数据结构之栈和队列

栈和队列是两种特殊的线性表，都可以用数组或者链表来实现，接下来就让我们看看栈和队列会有什么奥秘吧~ 

目录

1.栈

1.1栈的概念

1.2栈的实现

1.2.1 Stack.h

1.2.2 Stack.c

1.2.3 test.c

2.队列

2.1队列的概念

2.2队列的实现

2.2.1 Queue.h

2.2.2 Queue.c 

2.2.3 test.c

1.栈

1.1栈的概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2栈的实现

由于栈的特点是后进先出，对最后一个元素操作频繁，且无对中间元素的增删查改，故常选择数组（顺序表）来实现栈 

ps：感觉栈就是残疾的顺序表（不敢吱声）

1.2.1 Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDateType;
typedef struct Stack {STDateType* _a;//栈底int _top;//栈顶int _capacity;//容量
}Stack;//初始化
void STInit(Stack* ps);
//销毁
void STDestroy(Stack* ps);
//压栈
void STPush(Stack* ps, STDateType date);
//出栈
void STPop(Stack* ps);
//获取栈顶元素
STDateType STTop(Stack* ps);
//获取栈中有效数据个数
int STSize(Stack* ps);
//判断栈是否为空
bool STEmpty(Stack* ps);
//打印栈中元素
void STPrint(Stack* ps);

1.2.2 Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"//初始化
void STInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_capacity = 0;ps->_top = 0;
}
//销毁
void STDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_capacity = 0;ps->_top = 0;
}
//压栈
void STPush(Stack* ps, STDateType date)
{assert(ps);if (ps->_capacity == ps->_top){int newcapacity = (ps->_top == 0 ? 4 : 2 * ps->_capacity);STDateType* p = (STDateType*)realloc(ps->_a, newcapacity * sizeof(STDateType));if (p == NULL){perror("realloc p false");return;}else {ps->_a = p;}ps->_capacity = newcapacity;}ps->_a[ps->_top] = date;ps->_top++;
}
//出栈
void STPop(Stack* ps)
{assert(ps);assert(ps->_top);ps->_top--;
}
//获取栈顶元素
STDateType STTop(Stack* ps)
{assert(ps);return ps->_a[ps->_top - 1];
}
//获取栈中有效数据个数
int STSize(Stack* ps)
{assert(ps);return ps->_top;
}
//判断栈是否为空
bool STEmpty(Stack* ps)
{assert(ps);if (ps->_top == 0){return true;}else {return false;}
}
//打印栈中元素
void STPrint(Stack* ps)
{assert(ps);int i = 0;for(i = 0; i < ps->_top; i++){printf("%d->", ps->_a[i]);}printf("NULL\n");
}

1.2.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
int main()
{Stack st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);STPrint(&st);STPop(&st);STPrint(&st);STPush(&st, 6);STPrint(&st);int a = STTop(&st);printf("a=%d\n", a);int size = STSize(&st);printf("size=%d\n", size);STPop(&st);STPop(&st);STPop(&st);STPop(&st);STPop(&st);int size2 = STSize(&st);printf("size2=%d\n", size2);bool empty = STEmpty(&st);printf("empty=%d\n", empty);STDestroy(&st);return 0;
}

2.队列

2.1队列的概念

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.2队列的实现

根据队列一端进，一端出的特点，可知对头、尾元素操作频繁，若用数组，在删除队头元素时要进行大量元素的挪动，故我们常选择链表实现。 

2.2.1 Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode //控制队列中的一个节点
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue //控制整条队列
{QNode* head;QNode* tail;int size;
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
//打印
void QueuePrint(Queue* q);

2.2.2 Queue.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->size = 0;}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* cur = (QNode*)malloc(sizeof(QNode));if (cur == NULL){perror("malloc q fail");return;}cur->val = data;cur->next = NULL;if (QueueEmpty(q)){q->head = q->tail = cur;}else {q->tail->next = cur;q->tail = cur;}q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{assert(q);assert(q->head);QNode* cur = q->head;if (cur->next == NULL){q->head = q->tail = NULL;}else{q->head = cur->next;}free(cur);cur = NULL;q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(q->head);return q->head->val;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(q->tail);return q->tail->val;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{assert(q);return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{assert(q);return q->head == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}
}
//打印
void QueuePrint(Queue* q)
{assert(q);QNode* cur=q->head;while (cur){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}

2.2.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);int size=QueueSize(&q);printf("size=%d\n", size);int head=QueueFront(&q);printf("head=%d\n", head);int tail = QueueBack(&q);printf("tail=%d\n", tail);QueuePrint(&q);QueuePop(&q);QueuePop(&q);QueuePop(&q);size = QueueSize(&q);printf("size=%d\n", size);head = QueueFront(&q);printf("head=%d\n", head);tail = QueueBack(&q);printf("tail=%d\n", tail);bool t = QueueEmpty(&q);printf("%d\n", t);QueuePrint(&q);QueueDestroy(&q);return 0;
}

栈和队列属于线性表中比较简单的两环（当然是在掌握了链表之后），相信你勤加练习，多多思考，肯定能够将它们掌握 ！

---------------------------------------------------------------------------------------------------------------------------------

好啦，那这次的分享就到这里，希望看到这里的小伙伴可以多多支持一下鱼头，点赞关注加收藏哦~