1 栈
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
1.1 栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
1.1.1栈的接口声明
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDATATYPE;
typedef struct Stack
{
STDATATYPE * _a;
int _top;
STDATATYPE _capatity;
}Stack;
//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPushBack(Stack* ps,STDATATYPE x);
//出栈
void StackPopBack(Stack* ps);
//获取栈顶元素
STDATATYPE* StackTop(Stack* ps);
//获取栈内有效元素个数
int StackSize(Stack* ps);
//判空
int StackEmpty(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);
1.1.2 初始化栈
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_top = 0;
ps->_a = (STDATATYPE*)malloc(sizeof(STDATATYPE)*4);
ps->_capatity = 4;
}
1.1.3 入栈
//入栈
void StackPushBack(Stack* ps, STDATATYPE x)
{
assert(ps);
if (ps->_top == ps->_capatity)
{
STDATATYPE* tmp = (STDATATYPE*)realloc(ps->_a,sizeof(ps->_capatity)*ps->_capatity * 2);//此处为_capatity类型大小乘个数乘倍数
ps->_capatity *= 2;
if (tmp != NULL)
{
ps->_a = tmp;
}
else
{
printf("内存不足\n");
}
}
ps->_a[ps->_top] = x;
ps->_top++;
}
1.1.4 出栈
//出栈
void StackPopBack(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
ps->_top--;
}
1.1.5 获取栈顶元素
//获取栈顶元素
STDATATYPE* StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top>0);
return ps->_a[ps->_top-1];
}
1.1.6 获取栈内有效元素个数
//获取栈内有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
1.1.7 判空
//判空
int StackEmpty(Stack* ps)
{
return ps->_top > 0 ? 0 : 1;
}
1.1.8 销毁栈
//销毁栈
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->_a);
}
2 队列
2.1 队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。
2.1.1 队列的接口声明
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int QUDATATYPE;
typedef struct QueueNode
{
struct QueueNode *_pnext;
QUDATATYPE data;
}QueueNode;
typedef struct Queue
{
QueueNode* _front;
QueueNode* _rear;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//入队
void QueuePush(Queue* pq,QUDATATYPE x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QUDATATYPE QueueFront(Queue* pq);
//获取队尾元素
QUDATATYPE QueueBack(Queue* pq);
//获取对内有效元素个数
int QueueSize(Queue* pq);
//判空
int QueueEmpty(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
2.1.2 初始化队列
//初始化队列
void QueueInit(Queue* pq)
{
pq->_front = NULL;
pq->_rear = NULL;
}
2.1.3入队
//入队
void QueuePush(Queue* pq,QUDATATYPE x)
{
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->data = x;
assert(pq);
if (pq->_rear == NULL)
{
pq->_rear = node;
pq->_front = node;
}
else
{
pq->_rear->_pnext = node;
pq->_rear = node;
}
pq->_rear->_pnext = NULL;
}
2.1.4出队
//出队
void QueuePop(Queue* pq)
{
assert(pq);
QueueNode* tmp = pq->_front->_pnext;
free(pq->_front);
pq->_front = tmp;
}
2.1.5 获取队头元素
//获取队头元素
QUDATATYPE QueueFront(Queue* pq)
{
assert(pq);
return pq->_front->data;
}
2.1.6 获取队尾元素
//获取队尾元素
QUDATATYPE QueueBack(Queue* pq)
{
assert(pq);
return pq->_rear->data;
}
2.1.7 获取队内有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* cur=pq->_front;
int count=0;
while (cur)
{
count++;
cur=cur->_pnext;
}
return count;
}
2.1.8 判空
int QueueEmpty(Queue* pq)
{
assert(pq);
if (pq->_front ==NULL)
{
return 1;
}
return 0;
}
2.1.9 销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QueueNode* next = NULL;
if (pq->_front != NULL)
{
next = pq->_front->_pnext;
}
while (pq->_front)
{
free(pq->_front);
pq->_front = next;
if(next!=NULL)
next = next->_pnext;
}
pq->_front = NULL;
pq->_rear = NULL;
}
标签:ps,pq,队列,void,Queue,实现,front,Stack
From: https://blog.csdn.net/m0_63703622/article/details/141688328