栈和队列
一、栈
栈是什么
??栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈遵循先进后出原则
栈的实现
??栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的基本操作
栈类型的定义
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
int size;
}Stack;
初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a=(STDataType*)malloc(sizeof(STDataType)*5);
if(NULL==ps->a)
{
assert(0);
return;
}
ps->capacity=5;
ps->size=0;
}
检查栈是否为满
void CheckStack(Stack* ps)
{
assert(ps);
if(ps->capacity==ps->size)
{
//1.申请空间
int newcapacity=ps->capacity*2;
STDataType *temp=(STDataType*)malloc(sizeof(STDataType)*newcapacity);
if(temp==NULL)
{
assert(0);
return;
}
//2.拷贝元素
memcpy(temp,ps->a,sizeof(STDataType)*ps->size);
//3.释放旧空间
free(ps->a);
//4.使用新空间
ps->a=temp;
ps->capacity=newcapacity;
}
}
入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
CheckStack(ps);
ps->a[ps->size]=data;
ps->size++;
}
出栈
void StackPop(Stack* ps)
{
assert(ps);
if(!StackEmpty(ps))
{
ps->size--;
}
return;
}
获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->size-1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->size;
}
检测栈是否为空
int StackEmpty(Stack* ps)
{
assert(ps);
return 0==ps->size;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
if(ps->a)
{
free(ps->a);
ps->a=NULL;
ps->capacity=0;
ps->size=0;
}
}
测试函数
void TestStack()
{
Stack s;
StackInit(&s);
StackPush(&s,1);
StackPush(&s,2);
StackPush(&s,3);
StackPush(&s,4);
StackPush(&s,5);
StackPush(&s,6);
StackPush(&s,7);
printf("%d\n",StackTop(&s));
printf("%d\n",StackSize(&s));
StackPop(&s);
StackPop(&s);
StackPop(&s);
printf("%d\n",StackTop(&s));
printf("%d\n",StackSize(&s));
StackDestroy(&s);
}
完整代码
Stack.h
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
int size;
}Stack;
// 初始化栈
void StackInit(Stack* ps);
//检查栈是否为慢
void CheckStack(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
void TestStack();
Stack.c
#include "Stack.h"
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<string.h>
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a=(STDataType*)malloc(sizeof(STDataType)*5);
if(NULL==ps->a)
{
assert(0);
return;
}
ps->capacity=5;
ps->size=0;
}
// 检查栈是否满
void CheckStack(Stack* ps)
{
assert(ps);
if(ps->capacity==ps->size)
{
//1.申请空间
int newcapacity=ps->capacity*2;
STDataType *temp=(STDataType*)malloc(sizeof(STDataType)*newcapacity);
if(temp==NULL)
{
assert(0);
return;
}
//2.拷贝元素
memcpy(temp,ps->a,sizeof(STDataType)*ps->size);
//3.释放旧空间
free(ps->a);
//4.使用新空间
ps->a=temp;
ps->capacity=newcapacity;
}
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
CheckStack(ps);
ps->a[ps->size]=data;
ps->size++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
if(!StackEmpty(ps))
{
ps->size--;
}
return;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
return ps->a[ps->size-1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->size;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return 0==ps->size;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
if(ps->a)
{
free(ps->a);
ps->a=NULL;
ps->capacity=0;
ps->size=0;
}
}
void TestStack()
{
Stack s;
StackInit(&s);
StackPush(&s,1);
StackPush(&s,2);
StackPush(&s,3);
StackPush(&s,4);
StackPush(&s,5);
StackPush(&s,6);
StackPush(&s,7);
printf("%d\n",StackTop(&s));
printf("%d\n",StackSize(&s));
StackPop(&s);
StackPop(&s);
StackPop(&s);
printf("%d\n",StackTop(&s));
printf("%d\n",StackSize(&s));
StackDestroy(&s);
}
main.c
#include "Stack.h"
int main()
{
TestStack();
return 0;
}
二、队列
队列是什么
??队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
队列的实现
??队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列类型的定义
typedef int QDataType;
typedef struct QNode
{
struct QNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;
}Queue;
申请一个节点
QNode* buyQNode(QDataType data)
{
QNode *newnode=(QNode*)malloc(sizeof(QNode));
if(NULL==newnode)
{
assert(0);
return NULL;
}
newnode->data=data;
newnode->next=NULL;
return newnode;
}
初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front=q->rear=NULL;
q->size=0;
}
队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode *newnode=buyQNode(data);
if(NULL==q->front)
{
q->front=newnode;
}
else
{
q->rear->next=newnode;
}
q->rear=newnode;
q->size++;
}
队头出队列
void QueuePop(Queue* q)
{
assert(q);
if(QueueEmpty(q))
{
return;
}
else
{
QNode *delndoe=q->front;
q->front=delndoe->next;
free(delndoe);
if(NULL==q->front)
{
q->rear=NULL;
}
}
q->size--;
}
获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(!QueueEmpty(q));
return q->front->data;
}
获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(!QueueEmpty(q));
return q->rear->data;
}
获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(!QueueEmpty(q));
return q->size;
}
检测队列是否为空
int QueueEmpty(Queue* q)
{
assert(q);
return NULL==q->front;
}
销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode *cur=q->front;
while(cur)
{
q->front=cur->next;
free(cur);
cur=q->front;
}
q->rear=NULL;
q->size=0;
}
测试函数
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
printf("%d\n", QueueFront(&q));
printf("%d\n", QueueBack(&q));
printf("%d\n", QueueSize(&q));
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
printf("%d\n", QueueFront(&q));
printf("%d\n", QueueBack(&q));
printf("%d\n", QueueSize(&q));
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
if(QueueEmpty(&q))
{
printf("队列已经为空\n");
}
else{
printf("队列不为空\n");
}
QueueDestroy(&q);
}
完整代码
Queue.h
//链式结构：表示队列
typedef int QDataType;
typedef struct QNode
{
struct QNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* front;
QNode* rear;
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
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
///
void TestQueue();
Queue.c
#include"Queue.h"
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
//申请一个节点
QNode* buyQNode(QDataType data)
{
QNode *newnode=(QNode*)malloc(sizeof(QNode));
if(NULL==newnode)
{
assert(0);
return NULL;
}
newnode->data=data;
newnode->next=NULL;
return newnode;
}
//初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front=q->rear=NULL;
q->size=0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode *newnode=buyQNode(data);
if(NULL==q->front)
{
q->front=newnode;
}
else
{
q->rear->next=newnode;
}
q->rear=newnode;
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
if(QueueEmpty(q))
{
return;
}
else
{
QNode *delndoe=q->front;
q->front=delndoe->next;
free(delndoe);
if(NULL==q->front)
{
q->rear=NULL;
}
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(!QueueEmpty(q));
return q->front->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(!QueueEmpty(q));
return q->rear->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(!QueueEmpty(q));
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return NULL==q->front;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode *cur=q->front;
while(cur)
{
q->front=cur->next;
free(cur);
cur=q->front;
}
q->rear=NULL;
q->size=0;
}
/
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
printf("%d\n", QueueFront(&q));
printf("%d\n", QueueBack(&q));
printf("%d\n", QueueSize(&q));
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
printf("%d\n", QueueFront(&q));
printf("%d\n", QueueBack(&q));
printf("%d\n", QueueSize(&q));
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
if(QueueEmpty(&q))
{
printf("队列已经为空\n");
}
else{
printf("队列不为空\n");
}
QueueDestroy(&q);
}
main.c
#include"Queue.h"
int main()
{
TestQueue();
return 0;
}
三、环形队列
假溢出问题
??正常顺序队列若进行插入和删除，会使前部分的空间浪费，从而造成假溢出的情况。
??未解决假溢出的问题，大佬们提出了一种叫做环形队列的结构，环形队列可以使用数组实现，也可以使用循环链表实现。
??判断循环队列是否为空或者满的问题，通常用（rear-front+N）%N的方法判断是否为满或空。
