|
栈和队列
一、栈栈是什么栈的实现栈的基本操作栈类型的定义初始化栈检查栈是否为满入栈出栈获取栈顶元素检测栈是否为空测试函数
完整代码Stack.hStack.cmain.c
二、队列队列是什么队列的实现队列类型的定义申请一个节点初始化队列队尾入队列队头出队列获取队列头部元素获取队列队尾元素获取队列中有效元素个数检测队列是否为空销毁队列测试函数
完整代码Queue.hQueue.cmain.c
三、环形队列假溢出问题
一、栈
栈是什么
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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
#include
#include
#include
// 初始化栈
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
#include
#include
//申请一个节点
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的方法判断是否为满或空。 
|