当前位置：首页 > backend >正文

【数据结构】栈和队列

backend 2025/7/18 19:08:35

1.栈

1.栈的概念

对于栈，这里它不同与系统面的栈，而是一种特殊的线性表，对于这个存储数据的容器，它是一个插入数据（压栈）与删除数据（出栈）在同一端的。我们将插入或删除的一端叫做栈顶，另一端则是栈底。而这样就造成了一个特殊的方式：后进先出（Last In First Out）。

2.栈的实现

对于栈的实现，我们有静态的也有动态的，而在实际上，静态的不是很常用，主要是动态栈。
储存数据的方式有数组或则链表，但数据在这更优，因为栈插入数据时代价小。

3.代码解析

头文件（函数声明）

#pragma once#include<stdio.h>
#include<assert.h>#define N 10
typedef int STDataType;
//静态栈
//typedef struct stack 
//{
//	STDataType a[N];
//	int top;
//}stack;
//动态栈
typedef struct stack
{STDataType* a;int top;int capacity;
}stack;
// 初始化栈
void StackInit(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);

动态是用指针，来动态开辟空间。栈里面有初始化，入栈，压栈，获得栈顶元素，获得有效元素，检查栈情况，销毁栈。定义栈（结构体）里面top和capacity分别是指栈的位置与容量，top可以是0或者-1。这要看你想用哪个，如果0 则top指向的是无数据的空间，-1 则是有数据的空间，只不过要先给它加加，在赋值，0则是先赋值在加加。

源文件（函数的定义）

// 初始化栈
void StackInit(stack* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc failed");return;}ps->top = 0;ps->capacity = 4;
}

初始化：我们先将其结构体的指针开辟空间，再检查指针，接着将top按自己的想法来赋值，capacity 则跟据你开辟的空间来赋值。

// 入栈
void StackPush(stack* ps, STDataType data)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = data;ps->top++;
}

入栈：我们先要考虑栈是否满了，因为我们要插入数据。入过满了，就用realloc再开辟空间。折接着再跟据你top的值来插入数据。

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(stack* ps)
{assert(ps);return ps->top == 0;
}

查看栈是否为空：直接看top就行，而不是capacity 因为capacity是容量不是栈存储的数据请况。

// 出栈
void StackPop(stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}

出栈：首先我们要判断栈是否为空。接着我们访问数据是靠top的，所以只要改变top就行。

// 获取栈顶元素
STDataType StackTop(stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top--];
}

获得栈顶元素：我们既然是获得栈顶元素，而元素是一个数据，所以我们返回值是STDataType 因为我的top初始化时是0，所以要-1才能获得栈顶元素。

// 获取栈中有效元素个数
int StackSize(stack* ps)
{return ps->top;
}

获得栈有效元素个数：由于top初始化是0，则它就可以记录有效元素的个数，如果是-1就要加一。

// 销毁栈
void StackDestroy(stack* ps)
{assert(ps);free(ps->a);ps->a == NULL;ps->top = 0;ps->capacity = 0;
}

销毁栈：我们要看结构体里面有哪些成员：a ，top capacity。既然我们要销毁，那么将a指针赋值为空，top = 0，capacity容量 = 0。

4.总结

栈的话就到此为止了。只要将头文件与源文件弄好就行了，记得加#include"Stack.h"哟！

2.队列

1.队列的概念

对于队列，也是一种特殊的线性表，对于这个存储数据的容器，它是一个插入数据与删除数据在不同的一端。我们将插入数据的一端叫做队尾，删除数据则是队头。而这样就造成了一个特殊的方式：先进先出（First In First Out）

2.队列的实现

对于队列的实现储存数据的方式有数组或则链表，但与栈相反，是用链表因为出队列在数据时效率低。

3.代码解析

头文件（函数声明）

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

对于队列用链表，第一个结构体是用来链表的实现的通过指针指向一个又一个结构体，并储存数据。第二结构体是上一个结构体的指针有头指针和尾指针，以及大小。队列要的功能：初始化，入队列，出队列，获得头部元素，尾部元素，有效元素个数，查看队列是否为空，销毁队列。

（函数的定义）源文件

// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}

初始化：对于链表而言，我们初始化只要将头尾指针弄好就行，并将size记录元素多少的也给初始化。

// 队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

入队（从队尾）：既然是加元素，那么就要创建一个新的存储数据的结构体malloc开辟空间，并将其要加入的值给赋上去。接着有两种况：有元素和没元素，有元素则就是通过尾指针的next指针赋值为nownode，这就相当于将元素加到后面了，链接上了。接下来就将这nownode变成新的尾指针就行了。没元素则就是新加入一个元素头尾指针都要指向它。最后size++，表新加了一个数据。

// 队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}

出队列（队头出）：对于出数据，那么就要检查是否为空了。若不为空，则又有两种情况：有一个数据，多个数据。对于一个数据，我们就只要将头指针free了，并将头尾指针赋为空指针就行了。对于多个数据，这时我们就要新建一个结构体来储存之前的首位的下一位得数据，将原先的头指着的数据给free了，接着让这个新建的结构体成为新的头指针。最后size--，表剔除了一个数据。

// 获取队列头部元素
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

获得头部元素：这很简单，就只要用头指针指向它的数据就行。但要注意这个队列是不是空的。

// 获取队列队尾元素
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

获得尾部元素：这个也一样找尾指针指向的数据。要注意队列是不是空的。

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

队列中有效元素：我们在第二个结构体里有size成员，这个就是记录有效元素个数的，只要返回它就行。

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

检查队列是否为空：这里还是看size，size=0则为空。

// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}