您阅读这篇文章共耗时:
栈和队列
栈 定义和特点
栈是一种线性结构，限定在表尾进行插入和删除的线性表。
常规来讲，我们将栈的表尾端定义为栈顶，表头端定义为栈底。
此外，当返回栈顶元素时循环队列出队，最后插入的元素会被返回，因此，栈的特点是“后进先出”
表示和实现
栈支持的操作有：
插入、删除、返回栈顶元素、计算栈中元素个数、判断栈是否为空
同时，还要注意栈的初始化和销毁
顺序栈
顺序栈是指用顺序存储结构实现的栈：数组
设置一个栈的结构体，包含动态开辟的数组存放元素，一个维护数组大小，一个top指针表示栈顶元素在表中的位置 （栈顶的）坐标-1
int ;
struct
{
* a;
int top;
int ;
}Stack;
接下来对这个栈进行初始化
void StackInit(Stack*ps）
{
assert(ps);
STDataType* p=(STDataType*)malloc(sizeof(STDataType)*SIZE);
//创建SIZE个元素大小的数组
if (p == NULL) {
perror("malloc fail\n");
exit(-1);
}ps->a = p;
ps->top=0;
ps->capacity=SIZE;
}
下面进行元素入栈操作，即将给定的元素尾插到数组中
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
//先判定栈是否已满，满则扩容
if(StackSize(ps)==ps->capacity)
{
STDataType* p=(STDataType*)realloc(ps->a,ps->capacity*2* sizeof(STDataType));
if (p != NULL) {
ps->a = p;
ps->capacity *= 2;
}
else {
perror("realloc fail");
exit(-1);
}
}ps->a[ps->top++]=x;
}
元素的出栈操作为从栈顶删除元素,直接改变栈顶元素位置即可
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
//确保栈不为空
ps->top--;
}
返回栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
下面分别列出判空和计算栈中元素个数的操作
bool StackEmpty(Stack*ps)
{
assert(ps);
return ps->top==0;
}
int StackSize(Stack*ps)
{
assert(ps);
return ps->top;
}
最后别忘了销毁栈，否则内存会泄漏
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a=NULL;
ps->capacity = ps->top = 0;
}
链式栈
链式栈是指用链式结构实现的栈，通常创建一个个结点，链接。
由于链表的头删和头插比较容易实现，故链式栈的栈顶为链表的表头。
实现过程如下：
首先定义结点结构体，与单链表创建类似：
int ;
struct
{
data;
struct * next;
};
链栈的初始化就是创造一个空栈，主函数处创建一个栈顶指针*head，初始化函数就是将栈顶指针置空，表示空栈
void InitStack(StackNode** ps)
{
*ps = NULL;
}
入栈时，创建结点，头插在栈顶，同时修改栈顶指针
void StackPush(StackNode** ps, ElemType x)
{
struct StackNode* newnode = BuyNode(x);
//创建结点
newnode->next = *ps;
//头插
*ps = newnode;
//修改栈顶指针
}
出栈先判空，若不空，则头删
void StackPop(StackNode** ps)
{
assert(*ps);
struct StackNode* newhead = (*ps)->next;
free(*ps);
*ps = newhead;
}
返回栈顶元素和销毁
ElemType StackTop(StackNode* ps)
{
assert(ps);
return ps->data;
}
//链式栈的销毁需要一个一个free
void StackDestory(StackNode* ps)
{
assert(ps);
while (ps)
{
struct StackNode* cur = ps;
ps=ps->next;
free(cur);
}
}
队列 定义和特点
队列和栈的特性相反，是一种“先进先出”的线性表。
队列只允许元素在队头删除，在队尾插入。因此，最早进入队列的元素最早出队。
循环队列
循环队列是队列的一种顺序表示循环队列出队，使用数组实现，同时需要两个指针分别指向队头和队尾。
由于队列的特性，先进先出，当有元素入队的时候队尾指针+1，出队时队头指针+1。而会存在一种队列未满（队头删除了一些元素），尾指针指向数组边界，新元素无法入队的情况，如下图所示：
故需要将顺序空间更改为环状空间，即使用循环队列：
头、尾指针取模运算，在顺序表内以头尾相衔接的模式移动。
新位置下标=（旧位置下标+1）%数组容量
为方便判断队满和队空，需要少用一个元素的空间
队空的条件：
队满的条件：(rear+1)%数组容量front
typedef struct {
int* a;
int front;
int rear;
int size;
} MyCircularQueue;
//创建一个容量大小为K的循环队列
MyCircularQueue* myCircularQueueCreate(int k)
{
//创建队列
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//队列初始化
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->rear=obj->front=0;
obj->size=k+1;
return obj;
}
//判断队满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return obj->front==obj->((rear+1)%(obj->size));
}
//入队，成功返回true
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(!myCircularQueueIsFull(obj))
{
obj->a[obj->rear]=value;
rear=(rear+1)%(obj->size);
return true;
}return false;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->front==obj->rear;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if(!myCircularQueueIsEmpty(obj))
{
obj->front=(obj->front+1)%(obj->size);
return true;
}
return false;
}
//返回队首元素
int myCircularQueueFront(MyCircularQueue* obj)
{
if(!myCircularQueueIsEmpty(obj))
{
return obj->a[obj->front];
}
}
//返回队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj))
{
return -1;
}
else
{
//return obj->a[obj->rear-1]错误，如果此时rear=0,-1会非法访问
return obj->a[(obj->rear + obj->size-1) % (obj->size)];
}
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {
//分批次销毁，动态开辟的栈和数组都要销毁
free(obj->a);
free(obj);
}
链式队列
一个队列需要由头尾指针和若干结点组成，为方便管理，设置两个结构体
int ;
//队列的链式结点
struct
{
data;
struct * next;
};
//队列结构
struct Queue
{
* head;
* tail;
int size; //方便计算元素个数
}Queue;
接下来实现队列的操作
//队列初始化
void QueueInit(Queue* p)
{
assert(p);
p->head = NULL;
p->tail = NULL;
p->size = 0;
}
//入队
void Enqueue(Queue* p, QueueType x)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail\n");
exit(-1);
}newnode->data = x;
newnode->next = NULL;
//尾插到队列尾指针操作
if (QueueEmpty(p))
{
p->head = p->tail = newnode;
}
else {
p->tail->next = newnode;
p->tail = newnode;
}p->size++;
}
//出队
void Dequeue(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
if (p->head == p->tail)
{
free(p->head);
p->head = p->tail = NULL;
}
else {
QueueNode* del = p->head;
p->head = p->head->next;
free(del);
}
p->size--;
}
//返回队头元素
QueueType QueuePeek(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->head->data;
}
//返回队尾元素
QueueType QueueBack(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->tail->data;
}
//计算队列元素个数
int QueueSize(Queue* p)
{
assert(p);
return p->size;
}
//判空
int QueueEmpty(Queue* p)
{
assert(p);
return p->head == NULL;
}
//销毁队列
void QueueDestory(Queue* p)
{
assert(p);
QueueNode* cur = p->head;
while (cur)
{
QueueNode* del = cur;
cur = cur->next;
free(del);
}p->head = p->tail = NULL;
p->size = 0;
}
