数据结构初阶之栈和队列（C语言版）

2024-01-02 16:35:59

加粗样式

?栈

栈是数据结构的一种，一个栈可以用来对数据进行增删查改，但是它遵循一个原则，就是数据必须是后入先出，什么意思呢？就是先入栈的数据后出栈，后入栈的数据先出栈。我们可以使用链表和动态数组来实现栈。

我们使用动态数组来实现栈，为了实现后入先出，我们可以将栈看作只有尾插和尾删功能（也就是没有头插头删）的动态顺序表，其它都很相似。

?栈的结构设计

// 支持动态增长的栈
typedef int STDataType;
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 
bool StackEmpty(Stack* ps);

// 销毁栈 
void StackDestroy(Stack* ps);

?栈的各个接口的实现

这里我们使用动态增长的数组来实现栈，尾插和尾删对应我们的入栈和出栈，利用链表实现也可以，但是动态数组操作起来更加简单，也不需要挪动数据，出栈更是只需要简单的_top--就可以完成，何乐而不为呢。

👺StackInit(初始化)

栈对象在主程序已经创建好了，传结构体指针可以修改结构体里面的成员，初始化栈只需要把动态数组、栈的元素个数、栈的空间大小初始化就可以了。

// 初始化栈 
void StackInit(Stack* ps)
{
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

👺push（入栈）

入栈其实就是动态顺序表里的尾插，如果小伙伴有疑惑，可以看数据结构初阶之顺序表（C语言实现）

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	
	if (ps->_top == ps->_capacity)//判断是否需要扩容
	{
		STDataType* tmp = ps->_capacity == 0 ? (STDataType*)realloc(ps->_a, sizeof(STDataType) * 4) : (STDataType*)realloc(ps->_a, sizeof(STDataType)* (ps->_capacity * 2));
		if (tmp == NULL)
		{
			perror("realloc Failed");
			exit(-1);
		}
		ps->_a = tmp;
		ps->_capacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
	}
	
	ps->_a[ps->_top++] = data;//尾插新的元素，_top++
}

上述代码用到了三目操作符，如果不知道这个操作符的话可能就看不懂代码，这里博主来简单的说一下。它的构成是这样的：

表达式1?语句1: 语句二;
如果表达式1成立则执行语句1，否则执行语句二。

👺pop（出栈）

出栈操作就更不用说了，由于入栈是尾插由于要满足栈后进先出的原则，我们直接把最后一个入栈的删除就可以了，等价于元素个数_top--。

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}

👺获取栈顶元素

栈的元素个数减一就是栈顶元素的下标位置，返回该下标位置的值就可以了。

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	
	return ps->_a[ps->_top-1];
}

👺获取栈中有效元素的个数

直接返回栈的元素个数。

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

👺判断栈是否为空

直接看栈的元素个数是否为0，为空返回true，反之返回false。

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

👺销毁栈

这里栈对象是在外面就创建了，不一定是动态开辟的，所以我们只释放栈里面动态数组的空间就可以。

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

?队列

队列也是数据结构的一种，它和栈很像，区别就是队列数据必须是先进先出，什么意思呢？就是先入队列的数据先出队列，后入队列的数据后出队列。我们可以使用链表和动态数组来实现栈。

这里我们使用链表来实现队列，为了实现队列先入先出的功能，我们可以将我们实现的队列看成出数据只能头删、入数据只能尾插的单链表。

可能有小伙伴说，那我将最后面的数据视作队头，最前面的数据视作队尾，利用单链表的头插和尾删也可以实现队列呀，这也是可行的，只要保证先入先出的原则就可以，下面的图是两者的区别。

在这里插入图片描述

无论怎么样，要保证先入先出，队头始终是先进队列的。这里可能就有小伙伴突发奇想了，既然队列可以这样，栈可不可以把栈顶放在动态数组的左边去，使用头插和头删来维护栈呢？由于动态顺序表的头删和头插都需要挪动数据，时间开销太大，我们一般不这样做。

👻队列的结构的设计

typedef  int QDataType;//typedef重命名数据类型，下次改数据类型时改这个地方就可以了。
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}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 
bool QueueEmpty(Queue* q);

// 销毁队列 
n'/void QueueDestroy(Queue* q);

👻队列的各个接口实现

队列用到了很多基础的链表的知识，如果你不太懂链表，请看这篇博客。

🐷Init（初始化队列）

初始化，将头节点指针和尾节点置空就可以了。

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	
	q->_front = NULL;
	q->_rear = NULL;
}

🐷队尾入队列

和单链表里的尾插的区别是，这里我们已经维护了尾节点，不用循环遍历去找尾节点了，没有数据的情况需要特殊判断一下。

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc Failed\n");
		exit(-1);
	}
	newnode->_data = data;
	newnode->_next = NULL;

	if (q->_rear == NULL)//没有节点的情况
	{
		q->_front = q->_rear = newnode;
	}
	else//一般情况
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
}

🐷队头出队列

等价于链表中的头删，但是需要特判一下只有一个数据的情况。

// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front);
	
	QNode* new_front = q->_front->_next;
	free(q->_front);
	q->_front = new_front;
	if (q->_front == NULL)//特判一下一个节点的情况
		q->_rear = NULL;
}

🐷获取队列队头元素

直接返回头节点的节点值。

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	
	return q->_front->_data;
}

🐷获取队列队尾元素

直接返回尾节点的节点值。

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	
	return q->_rear->_data;
}

🐷判断队列是否为空

等价于判断头节点或者尾节点是否为空。

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

🐷获取队列的有效元素个数

循环遍历累加到临时变量中去，然后返回。

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		size++;
		cur = cur->_next;
	}
	return size;
}

注意：这里计算队列的大小不能使用指针减指针，因为链表每一个节点都是随机开的空间，而不是像动态数组一样连续的空间。

🐷销毁队列

由于链表的节点的空间是一个一个开的，所以需要一个一个依次销毁，最后不要忘了将队列的两个指针置空。

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	assert(q->_front);//如果队列已经为空，就不用销毁了

	QNode* cur = q->_front;
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;

下面我们用两道力扣上的简单题来熟悉一下栈和队列：

?OJ题之用两个队列实现栈

在这里插入图片描述
这是题目链接
先贴C语言ak代码：

typedef  int QDataType;  // 定义队列中数据类型为整数

// 链式结构：表示队列节点
typedef struct QListNode {
    struct QListNode* _next;  // 指向下一个节点的指针
    QDataType _data;          // 节点存储的数据
} QNode;

// 队列的结构
typedef struct Queue {
    QNode* _front;  // 指向队列头部节点的指针
    QNode* _rear;   // 指向队列尾部节点的指针
} Queue;

// 初始化队列
void QueueInit(Queue* q) {
    assert(q);  // 确保指针不为空
    q->_front = NULL;  // 将队列头部指针置空
    q->_rear = NULL;   // 将队列尾部指针置空
}

// 队尾入队列
void QueuePush(Queue* q, QDataType data) {
    assert(q);  // 确保指针不为空

    // 创建新的节点并分配内存空间
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc Failed\n");
        exit(-1);
    }
    newnode->_data = data;  // 存储数据到新节点中
    newnode->_next = NULL;  // 新节点的下一个节点置空

    // 如果队列为空，则新节点即为队列的唯一节点
    if (q->_rear == NULL) {
        q->_front = q->_rear = newnode;
    } else {  // 否则将新节点接入队列尾部，并更新队列尾部指针
        q->_rear->_next = newnode;
        q->_rear = newnode;
    }
}

// 队头出队列
void QueuePop(Queue* q) {
    assert(q);        // 确保指针不为空
    assert(q->_front); // 确保队列不为空

    // 移动队列头部指针至下一个节点，并释放原头部节点的内存空间
    QNode* new_front = q->_front->_next;
    free(q->_front);
    q->_front = new_front;

    // 如果队列为空，则同时更新队列尾部指针为空
    if (q->_front == NULL)
        q->_rear = NULL;
}

// 获取队列头部元素
QDataType QueueFront(Queue* q) {
    assert(q);        // 确保指针不为空
    assert(q->_front); // 确保队列不为空
    return q->_front->_data;  // 返回队列头部节点存储的数据
}

// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
    assert(q);        // 确保指针不为空
    assert(q->_rear); // 确保队列不为空
    return q->_rear->_data;  // 返回队列尾部节点存储的数据
}

// 获取队列中有效元素个数
int QueueSize(Queue* q) {
    assert(q);  // 确保指针不为空
    int size = 0;
    QNode* cur = q->_front;
    while (cur) {  // 遍历队列节点计算节点数目
        size++;
        cur = cur->_next;
    }
    return size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q) {
    assert(q);  // 确保指针不为空
    return q->_front == NULL;  // 判断队列是否为空
}

// 销毁队列
void QueueDestroy(Queue* q) {
    assert(q);  // 确保指针不为空

    // 释放队列中所有节点的内存空间，并将队列头部和尾部指针置空
    QNode* cur = q->_front;
    while (cur) {
        QNode* next = cur->_next;
        free(cur);
        cur = next;
    }
    q->_front = q->_rear = NULL;
}

// 定义一个栈结构，使用两个队列实现
typedef struct {
    Queue* q1;  // 第一个队列
    Queue* q2;  // 第二个队列
} MyStack;

// 创建一个新的栈结构
MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));  // 分配栈结构内存空间
    obj->q1 = (Queue*)malloc(sizeof(Queue));  // 初始化第一个队列
    QueueInit(obj->q1);
    obj->q2 = (Queue*)malloc(sizeof(Queue));  // 初始化第二个队列
    QueueInit(obj->q2);
    return obj;
}

// 元素入栈
void myStackPush(MyStack* obj, int x) {
    Queue* noempty = obj->q1;  // 初始化非空队列指针为q1
    if (QueueEmpty(noempty))  // 如果q1为空，则指向q2
        noempty = obj->q2;
    QueuePush(noempty, x);  // 将元素入队到非空队列中
}

// 元素出栈
int myStackPop(MyStack* obj) {
    Queue* noempty = obj->q1;  // 初始化非空队列指针为q1
    Queue* empty = obj->q2;    // 初始化空队列指针为q2
    if (QueueEmpty(noempty)) {  // 如果q1为空，则交换指针
        noempty = obj->q2;
        empty = obj->q1;
    }

    // 将非空队列中的数据放入空队列中，并留下最后一个数据
    while (QueueSize(noempty) > 1) {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }
    int top = QueueFront(noempty);  // 获取栈顶元素
    QueuePop(noempty);  // 将栈顶元素出队
    return top;
}

// 获取栈顶元素
int myStackTop(MyStack* obj) {
    int top = myStackPop(obj);  // 获取栈顶元素
    Queue* noempty = obj->q1;   // 初始化非空队列指针为q1
    if (QueueEmpty(noempty))    // 如果q1为空，则指向q2
        noempty = obj->q2;
    QueuePush(noempty, top);    // 将栈顶元素重新入栈
    return top;
}

// 检测栈是否为空
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(obj->q1) && QueueEmpty(obj->q2);  // 判断两个队列是否均为空
}

// 释放栈结构内存空间
void myStackFree(MyStack* obj) {
    QueueDestroy(obj->q1);  // 销毁队列1
    QueueDestroy(obj->q2);  // 销毁队列2
    free(obj->q1);  // 释放队列1的内存空间
    obj->q1 = NULL;
    free(obj->q2);  // 释放队列2的内存空间
    obj->q2 = NULL;
    free(obj);      // 释放栈结构的内存空间
}

ak截图：

在这里插入图片描述

这里由于C语言没有现成的轮子（也就是写好的队列）给我们用，所以只能自己手撕一个队列上去,所以代码比较长，不过小伙伴如果刚开始接触编程不用担心，等以后学了C++/java，上面那段代码可以减少很多，下面是C++代码示例：

#include <queue>

class MyStack {
private:
    std::queue<int>* q1;  // 第一个队列指针
    std::queue<int>* q2;  // 第二个队列指针

public:
    // 构造函数初始化两个队列
    MyStack() {
        q1 = new std::queue<int>;
        q2 = new std::queue<int>;
    }
    
    // 元素入栈
    void push(int x) {
        std::queue<int>* noempty = q1;  // 初始化非空队列指针为q1
        if (q1->empty())  // 如果q1为空，则指向q2
            noempty = q2;
        noempty->push(x);  // 将元素入队到非空队列中
    }
    
    // 元素出栈
    int pop() {
        std::queue<int>* noempty = q1;  // 初始化非空队列指针为q1
        std::queue<int>* empty = q2;    // 初始化空队列指针为q2
        if (q1->empty()) {  // 如果q1为空，则交换指针
            noempty = q2;
            empty = q1;
        }
     
        // 将非空队列中的数据放入空队列中，并留下最后一个数据
        while (noempty->size() > 1) {
            empty->push(noempty->front());
            noempty->pop();
        }
        int top = noempty->front();  // 获取栈顶元素
        noempty->pop();  // 将栈顶元素出队
        return top;
    }
    
    // 获取栈顶元素
    int top() {
        int top = pop();  // 获取栈顶元素
        std::queue<int>* noempty = q1;  // 初始化非空队列指针为q1
        if (q1->empty())  // 如果q1为空，则指向q2
            noempty = q2;
        noempty->push(top);  // 将栈顶元素重新入栈
        return top;
    }
    
    // 检测栈是否为空
    bool empty() {
        return q1->empty() && q2->empty();  // 判断两个队列是否均为空
    }
    
    // 析构函数释放队列内存空间
    ~MyStack() {
        delete q1;
        delete q2;
    }
};

ak截图：

在这里插入图片描述

C++的代码看不懂不要紧，关键我们要把这题的思路学会：

在这里插入图片描述

相信如果小伙伴了解了本题的思路，再去看代码就很简单了。
这里就C语言代码的几个关键点作一下说明：

myStackCreate()函数部分，这个函数是用来初始化栈的，返回值是指针（地址），所以我们必须使用动态开辟函数在堆上申请空间，否则出了这个函数，那片地址就会被回收，另外栈的两个指针成员也要初始化，同样需要在其它函数中使用，需要动态开辟申请空间，如果不初始化他们就是野指针了。
在pop、push栈函数部分我们都使用到了noempty或者是empty，这样做就不用考虑谁是空，谁不是空了，不容易出错，这也是我们设计栈的成员的时候使用指针的原因，如果这里empty、noempty不是指针就无法改变原队列的数据，就需要去具体的考虑谁是空，谁不是空了。
myStackFree()释放内存函数部分，由于我们给两个队列的节点和队列对象q1、q2、栈对象都在堆上申请了空间，需要把他们一一释放，注意顺序即可。

?OJ题之用两个栈实现队列

这是题目：

在这里插入图片描述

原题点这里

这里我们也是先贴ak代码：

// 定义栈结构
typedef int STDataType; // 定义栈中数据类型为整数
typedef struct Stack {
    STDataType* _a; // 存储栈元素的数组指针
    int _top;       // 栈顶位置索引
    int _capacity;  // 栈的容量
} Stack;

// 初始化栈
void StackInit(Stack* ps) {
    ps->_a = NULL;
    ps->_top = ps->_capacity = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data) {
    assert(ps); // 确保栈指针不为空
    if (ps->_top == ps->_capacity) { // 当栈满时扩容
        STDataType* tmp = ps->_capacity == 0 ? (STDataType*)realloc(ps->_a, sizeof(STDataType) * 4) : (STDataType*)realloc(ps->_a, sizeof(STDataType) * (ps->_capacity * 2));
        if (tmp == NULL) {
            perror("realloc Failed");
            exit(-1);
        }
        ps->_a = tmp;
        ps->_capacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
    }
    ps->_a[ps->_top++] = data; // 将元素入栈并更新栈顶位置
}

// 出栈
void StackPop(Stack* ps) {
    assert(ps); // 确保栈指针不为空
    assert(ps->_top > 0); // 确保栈不为空
    ps->_top--; // 出栈操作，栈顶位置减一
}

// 获取栈顶元素
STDataType StackTop(Stack* ps) {
    assert(ps); // 确保栈指针不为空
    return ps->_a[ps->_top - 1]; // 返回栈顶元素
}

// 获取栈中有效元素个数
int StackSize(Stack* ps) {
    assert(ps); // 确保栈指针不为空
    return ps->_top; // 返回栈中元素个数即栈顶位置索引
}

// 检测栈是否为空
bool StackEmpty(Stack* ps) {
    assert(ps); // 确保栈指针不为空
    return ps->_top == 0; // 返回栈是否为空
}

// 销毁栈
void StackDestroy(Stack* ps) {
    assert(ps); // 确保栈指针不为空
    free(ps->_a); // 释放栈数组内存空间
    ps->_a = NULL;
    ps->_capacity = 0;
    ps->_top = 0;
}

// 定义一个队列结构，使用两个栈实现
typedef struct {
    Stack* st1; // 入队列栈
    Stack* st2; // 出队列栈
} MyQueue;

// 创建一个新的队列结构
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); // 分配队列结构内存空间
    obj->st1 = (Stack*)malloc(sizeof(Stack)); // 初始化入队列栈
    StackInit(obj->st1);
    obj->st2 = (Stack*)malloc(sizeof(Stack)); // 初始化出队列栈
    StackInit(obj->st2);
    return obj;
}

// 元素入队
void myQueuePush(MyQueue* obj, int x) {
    while (!StackEmpty(obj->st2)) { // 将出队列栈中的元素全部转移到入队列栈中
        StackPush(obj->st1, StackTop(obj->st2));
        StackPop(obj->st2);
    }
    StackPush(obj->st1, x); // 将新元素入栈到入队列栈中
}

// 元素出队
int myQueuePop(MyQueue* obj) {
    while (!StackEmpty(obj->st1)) { // 将入队列栈中的元素全部转移到出队列栈中
        StackPush(obj->st2, StackTop(obj->st1));
        StackPop(obj->st1);
    }
    int peek = StackTop(obj->st2); // 获取队头元素
    StackPop(obj->st2); // 出队操作
    return peek;
}

// 获取队头元素
int myQueuePeek(MyQueue* obj) {
    int peek = myQueuePop(obj); // 获取队头元素
    StackPush(obj->st2, peek); // 将队头元素重新入队
    return peek;
}

// 检测队列是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(obj->st1) && StackEmpty(obj->st2); // 判断两个栈是否均为空
}

// 释放队列结构内存空间
void myQueueFree(MyQueue* obj) {
    StackDestroy(obj->st1); // 销毁入队列栈
    StackDestroy(obj->st2); // 销毁出队列栈
    free(obj->st1); // 释放入队列栈的内存空间
    obj->st1 = NULL;
    free(obj->st2); // 释放出队列栈的内存空间
    obj->st2 = NULL;
    free(obj); // 释放队列结构的内存空间
}

这道题队列的成员可以不用Stack指针(这样的话在使用Stack函数时就需要取地址了)，因为没有涉及到使用其它变量更改原栈变量的情况。

ak截图：

在这里插入图片描述

关键思路：

在这里插入图片描述

代码部分很多都和第一道题相似这里我们不再做过多的叙述。

?总结

本篇博客主要讲到了数据结构中栈和队列的一些知识，并给出了他们的C语言模拟实现，最后以两道OJ题强化了对后入先出、先入先出特性的了解，欢迎小伙伴指出不足和提出宝贵的建议，下面给出本篇博客思维导图，希望本篇博客对你有所帮助。

在这里插入图片描述

文章来源:https://blog.csdn.net/wszhj_/article/details/135325816
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！