文章目录

一、栈的概念

栈：是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。栈中的元素遵守后进先出 LIFO（Last in First Out）的原则。

我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

如图所示，我们把堆叠元素的顶部称为 “栈顶”，底部称为 “栈底”。将把元素添加到栈顶的操作叫作 “入栈”（也可以叫 “进栈” 等），删除栈顶元素的操作叫作 “出栈”。这些也是栈的常用操作。

请添加图片描述

二、栈的类型

和线性表类似，栈有两种存储表示方法：「顺序栈」 和 「链式栈」。

1. 顺序栈

「顺序栈」：即用顺序表来实现栈。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 top 指示栈顶元素在顺序栈中的位置。

请添加图片描述

2. 链式栈

「链式栈」：即用单链表来实现栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶 “指针” top 指示栈顶元素，top 永远指向链表的头节点位置。

如果用尾做栈顶，每次出栈入栈必须尾插尾删，需要遍历整个链表，删除数据效率低，否则就要设计成双向链表。

如果用头做栈顶，只需要头插头删，就可以设计成单链表。

请添加图片描述

两种栈的类型，如果非要选一种，顺序栈会稍微好一点。下面我们的代码实现也是用顺序栈来实现的。

三、基础操作及实现

1. 接口函数的声明（Stack.h）

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDataType;
typedef struct Stack {
    STDataType* a;  // 用顺序表来实现
    int top;  // 指向栈顶
    int capacity;  // 栈的容量
}ST;

// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
// 获取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中数据个数
int StackSize(ST* ps);
// 栈的判空
bool StackEmpty(ST* ps);

2. 栈的基础操作实现（Stack.c）

栈的初始化

StackInit：初始化栈结构体，为后续操作准备初始状态。置空动态数组指针，并将栈顶指针 top 和容量 capacity 置零。

void StackInit(ST* ps) {
    assert(ps);
    ps->a = NULL;
    ps->top = 0;  // 也可以初始化为-1
    ps->capacity = 0;
}

注意事项

  1. 通过断言确保传入的结构体指针非空
  2. top 的初始化方式会影响后续操作逻辑：
    • 若 top 初始化为 0，表示指向栈顶元素的下一个位置（即栈顶元素索引为 top-1）
    • 若初始化为 -1，则直接指向当前栈顶元素
    • 两种初始化，放数据和++的顺序有差异

栈的销毁

StackDestroy：有初始化一定要有销毁。释放栈占用的堆内存资源，将结构体恢复至初始状态，避免内存泄漏。

void StackDestroy(ST* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

入栈

StackPush：将元素压入栈顶，若空间不足自动进行动态扩容。

void StackPush(ST* ps, STDataType x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        // 如果栈为空，那么将大小置为 4，不为空，则扩容至原大小的两倍
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        // 开辟一个新的空间，大小为 newcapacity，并将原来的数组a的内容拷贝过来
        STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
        if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
	ps->top++;  // 别忘了top要++
}

出栈

StackPop：移除栈顶元素，仅需修改栈顶指针，不实际删除数据。

void StackPop(ST* ps) {
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

获取栈顶元素

StackTop：返回当前栈顶元素的副本，不修改栈结构。

STDataType StackTop(ST* ps) {
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

注意：如果初始化 top 为 -1 则 return ps->a[ps->top]

获取元素数量

StackSize：返回当前栈内有效元素的数量。

int StackSize(ST* ps) {
    assert(ps);
    return ps->top;
}

注意：如果初始化 top 为 -1 则 return ps->top + 1;

栈判空

StackEmpty：判断栈是否为空。返回值 true 表示空栈，false 表示存在有效数据。

bool StackEmpty(ST* ps){
	assert(ps);

	// if (ps->top == 0) return true;
	// else return false;

	return ps->top == 0;  // 一行搞定
}

3. 操作示例（test.c）

#include "Stack.h"

void TestStack() {
	ST st;
	StackInit(&st);
	StackPush(&st, 1);  // [1]
	StackPush(&st, 2);  // [1,2]-->出栈方向
	StackPush(&st, 3);  // [1, 2, 3]

	printf("Top: %d\n", StackTop(&st));  // 输出 3
	StackPop(&st);                      // 栈：[1, 2]

	while (!StackEmpty(&st)) {
		printf("%d ", StackTop(&st));  // 输出 2 1
		StackPop(&st);
	}
	StackDestroy(&st);
}

int main() {

	TestStack();

	return 0;
}

TestStack() 运行结果：

请添加图片描述

4. 完整代码

// Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDataType;
typedef struct Stack {
    STDataType* a;  // 用顺序表来实现
    int top;  // 指向栈顶
    int capacity;  // 栈的容量
}ST;

// 初始化栈
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
// 获取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中数据个数
int StackSize(ST* ps);
// 栈的判空
bool StackEmpty(ST* ps);

// Stack.c

#include "Stack.h"

void StackInit(ST* ps) {
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	//top初始化数据位0,意味着top指向栈顶数据的下一个
    //初始化为-1，意味着指向栈顶数据
    //两种初始化，放数据和++的顺序也有差异
	ps->capacity = 0;
}

void StackDestroy(ST* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
		if (tmp == NULL) {
			printf("realloc false");
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps){
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

STDataType StackTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	//assert(!StackEmpty(ps));
	return ps->a[ps->top - 1]; //注意初始化 top 为 0，所以要减 1
}

int StackSize(ST* ps) {
	assert(ps);
	return ps->top;
}

bool StackEmpty(ST* ps){
	assert(ps);

	/*if (ps->top == 0) return true;
	else return false;*/

	return ps->top == 0;  //一行搞定
}

// test.c

#include "Stack.h"

void TestStack() {
	ST st;
	StackInit(&st);
	StackPush(&st, 1);  // [1]
	StackPush(&st, 2);  // [1,2]-->出栈方向
	StackPush(&st, 3);  // [1, 2, 3]

	printf("Top: %d\n", StackTop(&st));  // 输出 3
	StackPop(&st);                      // 栈：[1, 2]

	while (!StackEmpty(&st)) {
		printf("%d ", StackTop(&st));  // 输出 2 1
		StackPop(&st);
	}
	StackDestroy(&st);
}

int main() {

	TestStack();

	return 0;
}

5. 练习

leetcode 20. 有效的括号

请添加图片描述

typedef char STDataType;

typedef struct Stack {
    STDataType* a;
    int top;
    int capacity;
}ST;

void StackInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

void StackDestroy(ST* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPop(ST* ps){
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

void StackPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
		if (tmp == NULL) {
			printf("realloc false");
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

STDataType StackTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

bool StackEmpty(ST* ps){
	assert(ps);
	return ps->top == 0;
}

bool isValid(char* s) {
    ST st;
    StackInit(&st);
    while(*s){
        if(*s == '(' || *s == '[' || *s == '{'){
            StackPush(&st, *s);
        }
        else{
            //如果此时栈为空，说明只有右括号，不匹配
            if(StackEmpty(&st)) return false;
            STDataType top = StackTop(&st);
            if((*s == ')' && top != '(') || (*s == ']' && top != '[') || (*s == '}' && top != '{' )){
                return false;
            }
            StackPop(&st);
        }
        ++s;       
    }
    //如果此时栈不为空，那么说明此时栈还有括号未匹配，左右括号的数量都不对，不匹配
    bool result = StackEmpty(&st);
    StackDestroy(&st);
    return result;
}
# 数据结构 # c语言 # visualstudio # leetcode
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

cover

KingbaseES数据库：医疗信创潮涌沅江，国产化信创打造医疗新质生产力

avatar DAMO开发者矩阵
cover

告别迁移焦虑：金仓KDMS V4带你轻松搞定数据库国产化替代

avatar DAMO开发者矩阵
cover

KingbaseES数据库在常德二院全栈国产化信创中产生新质生产力,医疗信创的部署如何实现，如何操作？

avatar DAMO开发者矩阵