【数据结构】「栈」（顺序栈、共享栈、链栈）

发布于：2025-07-17 ⋅ 阅读:(26) ⋅ 点赞:(0)

- 第 110 篇 -
Date: 2025 - 07 - 16
Author: 郑龙浩（仟墨）

文章目录


Author: 郑龙浩

Date: 2025.07.16

栈 (Stack)

1 顺序栈介绍

1.1 定义

栈也是一种线性表，是只允许在一端进行插入或删除操作的线性表

和其他的线性表结构是相同的，只是只能在一端操作

1.2 规则

只允许在一端口进行插入和删除的操作 –> 后进先出 LIFO（Last In First Out）

栈就像一摞盘子

**重要术语: ** 栈顶、栈底、空栈

  • 栈顶（栈顶元素）： 允许插入和删除的一端（最顶端盘子）
  • 栈底（栈底元素）： 不允许插入行和删除的一端（最低端的盘子）
  • 空栈： 没有任何元素的栈（没有盘子）

1.3基本操作

  • 创建、销毁：InisStack(SqStack* s)、DestroyStack(SqStack* s)
  • 进栈、出栈：Push(SqStack* s, ElemType x)、Pop(SqStack* s, ElemType x)（增、删）
  • 读取栈顶元素：GetTop(SqStack* s, x)（查）
  • 判断是否为空、满：IsStackEmpty(SqStack* s)、IsStackFull(SqStack* s)

2 顺序栈 - top指向栈顶元素

top 的范围是 -1 到 MaxSize - 1

  • 空栈的时候 top 指向 -1
  • 只有一个元素时，top 指向 0
  • 满栈的时候 top 指向栈顶元素

test.c 文件

#include "SqStack.h"
#include <stdio.h>

void Test1() {
    SqStack S;
    ElemType x;

    // 1. 初始化测试
    InitStack(&S);
    printf("初始化后栈是否为空？%s\n", IsStackEmpty(&S) ? "是" : "否"); 

    // 2. 入栈测试
    printf("\n入栈顺序：");
    for (int i = 1; i <= MaxSize; i++) {
        if (StackPush(&S, i * 10)) {
            printf("%d ", i * 10);
        }
        else {
            printf("\n第%d次入栈失败（栈满）\n", i);
        }
    }
    printf("\n栈是否已满？%s\n", IsStackFull(&S) ? "是" : "否"); 

    // 3. 栈顶读取测试
    if (StackGetTop(&S, &x)) {
        printf("\n当前栈顶元素：%d\n", x); 
    }

    // 边界测试：满栈入栈
    if (!StackPush(&S, 110)) {
        printf("\n已经满栈，入栈失败\n");
    }

    // 4. 出栈测试
    printf("\n出栈顺序：");
    while (!IsStackEmpty(&S)) {
        if (StackPop(&S, &x)) {
            printf("%d ", x); 
        }
    }
    printf("\n出栈后栈是否为空？%s\n", IsStackEmpty(&S) ? "是" : "否"); 

    // 5. 边界测试：空栈出栈
    if (!StackPop(&S, &x)) {
        printf("\n现在是空栈，出栈操作失败\n");
    }

    // 6. 销毁栈测试
    DestroyStack(&S);
    printf("\n销毁栈后top值：%d\n", S.top); 
}

int main() {
    Test1();
    return 0;
}

运行结果

初始化后栈是否为空？是

入栈顺序：10 20 30 40 50 60 70 80 90 100
栈是否已满？是

当前栈顶元素：100

已经满栈，入栈失败

出栈顺序：100 90 80 70 60 50 40 30 20 10
出栈后栈是否为空？是

现在是空栈，出栈操作失败

销毁栈后top值：-1

SqStack.c 文件

#include "SqStack.h"
#include "stdio.h"

// 初始化
void InitStack(SqStack* S) {
	S->top = -1; // 默认空栈 top 指向-1
}

// 销毁
void DestroyStack(SqStack* S) {
	S->top = -1;
}

// 进栈
int StackPush(SqStack* S, ElemType x) {
	// x 是要入栈的元素
	if (S->top == MaxSize - 1)
		return 0; // 如果满栈，不能入栈，返回0
	S->data[++S->top] = x;
	return 1; // 返回1，表示进栈成功
}

// 出栈
int StackPop(SqStack* S, ElemType *x) {
	if (S->top == -1)
		return 0; // 如果空栈，不能出栈，返回0
	*x = S->data[S->top--]; // x 带回栈顶元素
	return 1;
}

// 读取栈顶
int StackGetTop(SqStack* S, ElemType *x) {
	if (S->top == -1)
		return 0; // 如果空栈，则读取不出来元素，返回0
	*x = S->data[S->top];
	return 1; // 返回1，表示进栈成功
}

// 判断栈空
int IsStackEmpty(SqStack* S) {
	if (S->top == -1) // 空1，非空0
		return 1;
	else
		return 0;
}

// 判断栈满
int IsStackFull(SqStack* S) {
	if (S->top == MaxSize - 1)
		return 1;
	else
		return 0;
}

SqStack.h 文件

#pragma once
#define MaxSize 10
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize]; // 存储元素
	int top; // 指向栈顶元素
}SqStack;

// 初始化
void InitStack(SqStack* S);

// 销毁
void DestroyStack(SqStack* S);

// 进栈
int StackPush(SqStack* S, ElemType x);

// 出栈
int StackPop(SqStack* S, ElemType *x);

// 读取栈顶
int StackGetTop(SqStack* S, ElemType *x);

// 判断栈空
int IsStackEmpty(SqStack* S);

// 判断栈满
int IsStackFull(SqStack* S);

3 顺序栈 - top指向栈顶元素后面

top 的范围是 0 到 MaxSize

  • 空栈的时候 top 指向 0
  • 只有一个元素时，top 指向 1
  • 满栈的时候 top 指向栈顶元素后边

test.c 文件

#include "SqStack.h"
#include <stdio.h>

void Test1() {
    SqStack S;
    ElemType x;

    // 1. 初始化测试
    InitStack(&S);
    printf("初始化后栈是否为空？%s\n", IsStackEmpty(&S) ? "是" : "否"); 

    // 2. 入栈测试
    printf("\n入栈顺序：");
    for (int i = 1; i <= MaxSize; i++) {
        if (StackPush(&S, i * 10)) {
            printf("%d ", i * 10);
        }
        else {
            printf("\n第%d次入栈失败（栈满）\n", i);
        }
    }
    printf("\n栈是否已满？%s\n", IsStackFull(&S) ? "是" : "否"); 

    // 3. 栈顶读取测试
    if (StackGetTop(&S, &x)) {
        printf("\n当前栈顶元素：%d\n", x); 
    }

    // 边界测试：满栈入栈
    if (!StackPush(&S, 110)) {
        printf("\n已经满栈，入栈失败\n");
    }

    // 4. 出栈测试
    printf("\n出栈顺序：");
    while (!IsStackEmpty(&S)) {
        if (StackPop(&S, &x)) {
            printf("%d ", x); 
        }
    }
    printf("\n出栈后栈是否为空？%s\n", IsStackEmpty(&S) ? "是" : "否"); 

    // 5. 边界测试：空栈出栈
    if (!StackPop(&S, &x)) {
        printf("\n现在是空栈，出栈操作失败\n");
    }

    // 6. 销毁栈测试
    DestroyStack(&S);
    printf("\n销毁栈后top值：%d\n", S.top); 
}

int main() {
    Test1();
    return 0;
}

运行结果

初始化后栈是否为空？是

入栈顺序：10 20 30 40 50 60 70 80 90 100
栈是否已满？是

当前栈顶元素：100

已经满栈，入栈失败

出栈顺序：100 90 80 70 60 50 40 30 20 10
出栈后栈是否为空？是

现在是空栈，出栈操作失败

销毁栈后top值：0

SqStack.c 文件

#include "SqStack.h"
#include "stdio.h"

// 初始化
void InitStack(SqStack* S) {
	S->top = 0; // 默认空栈 top 指向0
}

// 销毁
void DestroyStack(SqStack* S) {
	S->top = 0;
}

// 进栈
int StackPush(SqStack* S, ElemType x) {
	// x 是要入栈的元素
	if (S->top == MaxSize)
		return 0; // 如果满栈，不能入栈，返回0
	S->data[S->top++] = x;
	return 1; // 返回1，表示进栈成功
}

// 出栈
int StackPop(SqStack* S, ElemType* x) {
	if (S->top == 0)
		return 0; // 如果空栈，不能出栈，返回0
	*x = S->data[--S->top]; // x 带回栈顶元素
	return 1;
}

// 读取栈顶
int StackGetTop(SqStack* S, ElemType* x) {
	if (S->top == 0)
		return 0; // 如果空栈，则读取不出来元素，返回0
	*x = S->data[S->top - 1];
	return 1; // 返回1，表示进栈成功
}

// 判断栈空
int IsStackEmpty(SqStack* S) {
	if (S->top == 0) // 空1，非空0
		return 1;
	else
		return 0;
}

// 判断栈满
int IsStackFull(SqStack* S) {
	if (S->top == MaxSize)
		return 1;
	else
		return 0;
}

SqStack.h 文件

#pragma once
#define MaxSize 10
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize]; // 存储元素
	int top; // 指向栈顶元素
}SqStack;

// 初始化
void InitStack(SqStack* S);

// 销毁
void DestroyStack(SqStack* S);

// 进栈
int StackPush(SqStack* S, ElemType x);

// 出栈
int StackPop(SqStack* S, ElemType *x);

// 读取栈顶
int StackGetTop(SqStack* S, ElemType *x);

// 判断栈空
int IsStackEmpty(SqStack* S);

// 判断栈满
int IsStackFull(SqStack* S);

5 顺序栈 top指向不同的区别

操作 top 指向栈顶元素和后边 top 指向栈顶元素
初始化 S->top = 0 S->top = -1
栈空条件 top == 0 top == -1
栈满条件 top == MaxSize top == MaxSize - 1
进栈操作 S->data[S->top++] = x S->data[++S->top] = x
出栈操作 *x = S->data[--S->top] *x = S->data[S->top--]
栈顶元素位置 data[top - 1] data[top]
首个元素位置 data[0] data[0]
top指向？ top指向下一个入栈的元素位置（栈顶元素后边） top直接指向当前栈顶元素

4 共享栈（别名: 双向栈、双端栈）

基本介绍

是一种将两个栈共享同一块连续内存空间的数据结构。

  • 两个栈共享同一个数组空间
  • 栈0：一个栈从数组的起始位置（通常称为"下端"或"栈0"）开始生长，top0指向这个栈的栈顶元素
  • 栈1：一个栈从数组的末尾位置（通常称为"上端"或"栈1"）开始生长，top1指向这个栈的栈顶元素
  • 栈0：向数组末尾方向（向MaxSize-1）增长（下标递增）；栈1：向数组起始方向（向0）增长（下标递减）
  • 栈满：当两个栈的栈顶相遇（top0 > top1）时，表示栈空间已满

test.c

#include "stdio.h"
#include "ShStack.h"

int main() {
    ShStack S;
    ElemType x;

    // 初始化测试
    InitStack(&S);
    printf("初始化测试: %s\n", IsStackEmpty(&S) ? "正确" : "错误");

    // 栈0入栈测试
    printf("栈0入栈: %s\n", StackPush(&S, 0, 10) ? "正确" : "错误");
    printf("栈0非空: %s\n", !IsStack0Empty(&S) ? "正确" : "错误");

    // 栈1入栈测试
    printf("栈1入栈: %s\n", StackPush(&S, 1, 20) ? "正确" : "错误");
    printf("栈1非空: %s\n", !IsStack1Empty(&S) ? "正确" : "错误");

    // 栈顶读取测试
    printf("栈0栈顶: %s\n", StackGetTop(&S, 0, &x) && x == 10 ? "正确" : "错误");
    printf("栈1栈顶: %s\n", StackGetTop(&S, 1, &x) && x == 20 ? "正确" : "错误");

    // 出栈测试
    printf("栈0出栈: %s\n", StackPop(&S, 0, &x) && x == 10 ? "正确" : "错误");
    printf("栈1出栈: %s\n", StackPop(&S, 1, &x) && x == 20 ? "正确" : "错误");

    // 栈空测试
    printf("栈0空栈: %s\n", IsStack0Empty(&S) ? "正确" : "错误");
    printf("栈1空栈: %s\n", IsStack1Empty(&S) ? "正确" : "错误");

    // 栈满测试
    for (int i = 0; i < MaxSize / 2; i++) StackPush(&S, 0, i);
    for (int i = 0; i < MaxSize / 2; i++) StackPush(&S, 1, i);
    printf("栈满测试: %s\n", IsStackFull(&S) ? "正确" : "错误");

    // 销毁测试
    DestroyStack(&S);
    printf("销毁测试: %s\n", IsStackEmpty(&S) ? "正确" : "错误");

    return 0;
}

运行结果

初始化测试: 正确
栈0入栈: 正确
栈0非空: 正确
栈1入栈: 正确
栈1非空: 正确
栈0栈顶: 正确
栈1栈顶: 正确
栈0出栈: 正确
栈1出栈: 正确
栈0空栈: 正确
栈1空栈: 正确
栈满测试: 正确
销毁测试: 正确

ShStack.h

#pragma once
#define MaxSize 10
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize]; // 存储元素
	int top0; // 栈0 的栈顶指针
	int top1; // 栈1 的栈顶指针
}ShStack;

// 初始化
void InitStack(ShStack* S);

// 销毁
void DestroyStack(ShStack* S);

// 进栈
int StackPush(ShStack* S, int StackNum, ElemType x);

// 出栈
int StackPop(ShStack* S, int StackNum, ElemType* x);

// 读取栈顶
int StackGetTop(ShStack* S, int StackNum, ElemType* x);

// 判断栈空
int IsStackEmpty(ShStack* S);

// 判断栈0空
int IsStack0Empty(ShStack* S);

// 判断栈1空
int IsStack1Empty(ShStack* S);

// 判断栈满
int IsStackFull(ShStack* S);

ShStack.c

#include "stdio.h"
#include "ShStack.h"

// 初始化
void InitStack(ShStack* S) {
	S->top0 = -1;
	S->top1 = MaxSize - 1;
}

// 销毁
void DestroyStack(ShStack* S) {
	S->top0 = -1;
	S->top1 = MaxSize - 1;
}

// 进栈
int StackPush(ShStack* S, int StackNum, ElemType x) {
	if (S->top0+1 ==  S->top1) // 如果满栈则无法入栈，返回0
		return 0;
	// 栈0 入栈
	if (StackNum == 0) {
		S->data[++S->top0] = x;
		return 1; // 成功入栈
	}

	// 栈1 入栈
	if (StackNum == 1) {
		S->data[--S->top1] = x;
		return 1; // 成功入栈
	}
	return 0; // 输入参数错误，也会返回0
}

// 出栈
int StackPop(ShStack* S, int StackNum, ElemType* x) {
	if (StackNum == 0) { 
		if (S->top0 == -1) return 0; // 若栈0空栈，则需返回0
		*x = S->data[S->top0--];
		return 1;
	}
	if (StackNum == 1) {
		if (S->top1 == MaxSize - 1) return 0; // 若栈1空栈，则需返回0
		*x = S->data[S->top1++];
		return 1;
	}
	return 0; // 输入参数错误，也会返回0
}

// 读取栈顶
int StackGetTop(ShStack* S, int StackNum, ElemType* x) {
	if (StackNum == 0) {
		if (S->top0 == -1) return 0; // 若栈0空栈，则需返回0
		*x = S->data[S->top0];
		return 1;
	}
	if (StackNum == 1) {
		if (S->top1 == MaxSize - 1) return 0; // 若栈1空栈，则需返回0
		*x = S->data[S->top1];
		return 1;
	}
	return 0; // 输入参数错误，也会返回0
}

// 判断栈空
int IsStackEmpty(ShStack* S) {
	if (S->top0 == -1 && S->top1 == MaxSize - 1)
		return 1;
	else
		return 0;
}

// 判断栈0空
int IsStack0Empty(ShStack* S) {
	if (S->top0 == -1) return 1;
	else return 0;
}

// 判断栈1空
int IsStack1Empty(ShStack* S) {
	if (S->top1 == MaxSize - 1) return 1;
	else return 0;
}

// 判断栈满 （双栈为空）
int IsStackFull(ShStack* S) {
	if (S->top0 + 1 == S->top1)
		return 1;
	else
		return 0;
}

5 链栈介绍

5.1 基本介绍

  • 链栈就是用链式存储实现的栈，和单链表结构相同
  • 但是链栈多了约束条件：只能在一端进行操作（比如在头结点）
  • 有两种版本：
    • 1 单向带头结点不循环
    • 2 单向无头结点不循环（推荐）

5.2 基本操作

  • 初始化

void InitLStack(LinkLStack *S)

  • 销毁

void DestroyLStack(LinkLStack *S)

  • 清空

void ClearLStack(LinkLStack *S)

  • 进栈

bool PushLStack(LinkLStack *S, ElemType value)

  • 出栈

bool PopLStack(LinkLStack *S, ElemType *value)

  • 获取栈顶元素

bool GetTopLStack(LinkLStack *S, ElemType *value)

  • 判断栈空

bool IsEmptyLStack(LinkLStack *S)

  • 获取栈的大小

int GetLStackLength(LinkLStack *S)

  • 遍历打印

void PrintLStack(LinkLStack *S)

6 链栈_无头结点（推荐，因为教材上是这个版本）

test.c

#include "linked_stack_no_head.h"
#include <stdio.h>

void Test1() {
    LinkStack S;
    ElemType x;

    // 1. 初始化测试
    InitLStack(&S);
    printf("初始化后栈是否为空？%s\n", IsEmptyLStack(&S) ? "是" : "否");

    // 2. 入栈测试
    printf("\n入栈顺序：");
    for (int i = 1; i <= 5; i++) {
        if (PushLStack(&S, i * 10)) {
            printf("%d ", i * 10);
        }
    }

    printf("\n\n实际存储：\n"); PrintLStack(&S); // 遍历链栈
    printf("\n当前栈长度：%d\n", GetLengthLStack(&S));

    // 3. 栈顶读取测试
    if (GetTopLStack(&S, &x)) {
        printf("\n当前栈顶元素：%d\n", x);
    }

    // 4. 出栈测试
    printf("\n出栈顺序：");
    while (!IsEmptyLStack(&S)) {
        if (PopLStack(&S, &x)) {
            printf("%d ", x);
        }
    }
    printf("\n出栈后栈是否为空？%s\n", IsEmptyLStack(&S) ? "是" : "否");
    printf("\n实际存储，如果不打印则表示正确：\n"); PrintLStack(&S); // 如果不打印则表示正确

    // 5. 边界测试：空栈出栈
    if (!PopLStack(&S, &x)) {
        printf("\n现在是空栈，出栈操作失败\n");
    }

    // 6. 销毁栈测试
    DestroyLStack(&S);
    printf("\n销毁栈后top指针：%p\n", S.top);

    // 7. 再次初始化后，栈的宽度是否为空
    InitLStack(&S);
    printf("\n再次初始化后，栈的宽度是否为空: %s", IsEmptyLStack(&S) ? "是" : "否");
}

int main() {
    Test1();
    return 0;
}

运行结果

初始化后栈是否为空？是

入栈顺序：10 20 30 40 50

实际存储：
栈顶 -> 50 -> 40 -> 30 -> 20 -> 10 -> 栈底

当前栈长度：5

当前栈顶元素：50

出栈顺序：50 40 30 20 10
出栈后栈是否为空？是

实际存储，如果不打印则表示正确：

现在是空栈，出栈操作失败

销毁栈后top指针：0000000000000000

再次初始化后，栈的宽度是否为空: 是

linked_stack_no_head.h

#pragma once
#include "stdio.h"
#include <stdbool.h>

typedef int ElemType;
// 结点结构
typedef struct LinkNode{
	ElemType data; // 数据域
	struct LinkNode* next; // 指针域
}LinkNode;
// 链栈结构
typedef struct {
	LinkNode* top; // 栈顶元素
	int length; // 链栈长度
}LinkStack;

// 初始化
void InitLStack(LinkStack* S);
// 销毁栈
void DestroyLStack(LinkStack* S);

// 清空
void ClearLStack(LinkStack* S);

// 进栈
bool PushLStack(LinkStack* S, ElemType x);

// 出栈
bool PopLStack(LinkStack* S, ElemType* x);

// 获取栈顶元素
bool GetTopLStack(LinkStack* S, ElemType* x);

// 判断栈空
bool IsEmptyLStack(LinkStack* S);

// 获取栈的大小
int GetLengthLStack(LinkStack* S);

// 遍历打印
void PrintLStack(LinkStack* S);

linked_stack_no_head.c

#include "linked_stack_no_head.h"
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
// 初始化
void InitLStack(LinkStack* S) {
	S->top = NULL; // 空栈的情况下，top指向空
	S->length = 0; // 空栈的情况下，链栈宽为0
}

// 如果没有头结点，那么销毁栈和清空栈是等同的效果
// 销毁栈
void DestroyLStack(LinkStack* S) {
	ClearLStack(S);
}

// 清空
void ClearLStack(LinkStack* S) {
	LinkNode* cur = S->top; // 存储第一个结点的地址
	while (cur != NULL) {
		LinkNode* next = cur->next;
		free(cur);
		cur = next;
	}
	S->top = NULL; // 栈顶指针置空
	S->length = 0; // 链栈宽为0
}
// 进栈(无头结点)
bool PushLStack(LinkStack* S, ElemType x) {
	LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
	if (!NewNode)	return false; // 内存分配失败
	NewNode->data = x;
	NewNode->next = S->top; // 新节点指向 原来的栈顶
	S->top = NewNode; // 让栈顶指针一直指向新的 “第一个结点”
	S->length++; // 长度++
	return true;
}

// 出栈
bool PopLStack(LinkStack* S, ElemType* x) {
	if (IsEmptyLStack(S)) return false; // 如果是空栈，返回false
	LinkNode* OldTop = S->top; // 存储栈顶元素地址，以防栈顶元素地址丢失
	*x = OldTop->data;
	S->top = OldTop->next; // 将栈顶指针指向 原栈的倒数第二个结点，此时会丢失原栈顶元素的地址，
	// 所以想要释放原栈顶元素，就得用提前存到OldTop的栈顶元素地址
	free(OldTop);
	S->length--; // 长度--
	return true;
}

// 获取栈顶元素
bool GetTopLStack(LinkStack* S, ElemType* x) {
	if (IsEmptyLStack(S)) return false; // 空栈，返回false
	*x = S->top->data;
	return true;
}

// 判断栈空
bool IsEmptyLStack(LinkStack* S) {
	return S->top == NULL; // 如果栈顶指针指向NULL，则表示为栈空
}

// 获取栈的大小
int GetLengthLStack(LinkStack* S) {
	return S->length;
}

// 遍历打印
void PrintLStack(LinkStack* S) {
	if (IsEmptyLStack(S)) return;
	LinkNode* cur = S->top; // 从第一个结点开始
	printf("栈顶 -> ");
	while (cur != NULL) {
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("栈底\n");
}

7 链栈_带头结点

test.c

#include "linked_stack_with_head.h"
#include <stdio.h>

void Test1() {
    LinkStack S;
    ElemType x;

    // 1. 初始化测试
    InitLStack(&S);
    printf("初始化后栈是否为空？%s\n", IsEmptyLStack(&S) ? "是" : "否");

    // 2. 入栈测试
    printf("\n入栈顺序：");
    for (int i = 1; i <= 5; i++) {
        if (PushLStack(&S, i * 10)) {
            printf("%d ", i * 10);
        }
    }

    printf("\n\n实际存储：\n"); PrintLStack(&S); // 遍历链栈
    printf("\n当前栈长度：%d\n", GetLengthLStack(&S));

    // 3. 栈顶读取测试
    if (GetTopLStack(&S, &x)) {
        printf("\n当前栈顶元素：%d\n", x);
    }

    // 4. 出栈测试
    printf("\n出栈顺序：");
    while (!IsEmptyLStack(&S)) {
        if (PopLStack(&S, &x)) {
            printf("%d ", x);
        }
    }
    printf("\n出栈后栈是否为空？%s\n", IsEmptyLStack(&S) ? "是" : "否");
    printf("\n实际存储，如果不打印则表示正确：\n"); PrintLStack(&S); // 如果不打印则表示正确

    // 5. 边界测试：空栈出栈
    if (!PopLStack(&S, &x)) {
        printf("\n现在是空栈，出栈操作失败\n");
    }

    // 6. 销毁栈测试
    DestroyLStack(&S);
    printf("\n销毁栈后top指针：%p\n", S.top);

    // 7. 再次初始化后，栈的宽度是否为空
    InitLStack(&S);
    printf("\n再次初始化后，栈的宽度是否为空: %s", IsEmptyLStack(&S) ? "是" : "否");
}

int main() {
    Test1();
    return 0;
}

运行结果

初始化后栈是否为空？是

入栈顺序：10 20 30 40 50

实际存储：
栈顶(头结点) -> 50 -> 40 -> 30 -> 20 -> 10 -> 栈底

当前栈长度：5

当前栈顶元素：50

出栈顺序：50 40 30 20 10
出栈后栈是否为空？是

实际存储，如果不打印则表示正确：
空栈

现在是空栈，出栈操作失败

销毁栈后top指针：0000000000000000

再次初始化后，栈的宽度是否为空: 是

linked_stack_with_head.h

#pragma once
#include "stdio.h"
#include <stdbool.h>

typedef int ElemType;
// 结点结构
typedef struct LinkNode {
	ElemType data; // 数据域
	struct LinkNode* next; // 指针域
}LinkNode;
// 链栈结构
typedef struct {
	LinkNode* top; // 栈顶元素
	int length; // 链栈长度
}LinkStack;

// 初始化
void InitLStack(LinkStack* S);
// 销毁栈
void DestroyLStack(LinkStack* S);

// 清空
void ClearLStack(LinkStack* S);

// 进栈
bool PushLStack(LinkStack* S, ElemType x);

// 出栈
bool PopLStack(LinkStack* S, ElemType* x);

// 获取栈顶元素
bool GetTopLStack(LinkStack* S, ElemType* x);

// 判断栈空
bool IsEmptyLStack(LinkStack* S);

// 获取栈的大小
int GetLengthLStack(LinkStack* S);

// 遍历打印
void PrintLStack(LinkStack* S);

linked_stack_with_head.c

#include "linked_stack_with_head.h"
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
// 初始化（带头结点）
void InitLStack(LinkStack* S) {
	// 创建头结点
	S->top = (LinkNode*)malloc(sizeof(LinkNode));
	if (!S->top) return;

	// 创建空栈 --> 即第一个有效结点指针为空，栈宽0
	S->top->next = NULL; // 空栈的情况下，top指向空
	S->length = 0; // 空栈的情况下，链栈宽为0
}

// 销毁栈
void DestroyLStack(LinkStack* S) {
	ClearLStack(S);
	// 在清空栈的基础之上，做释放栈顶指针的操作
	free(S->top); // 释放头结点
	S->top = NULL; // 栈顶指针置空
	S->length = 0; // 栈宽0
}

// 清空
void ClearLStack(LinkStack* S) {
	LinkNode* cur = S->top->next; // 存储第一个有效结点的地址
	// 从第一个结点开始一直到最后一个结点一直释放空间
	while (cur != NULL) {
		LinkNode* next = cur->next;
		free(cur);
		cur = next;
	}
	S->top->next = NULL; // 第一个有效结点的指针置空
	S->length = 0; // 链栈宽为0
}
// 进栈(有头结点)
bool PushLStack(LinkStack* S, ElemType x) {
	LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
	if (!NewNode)	return false; // 内存分配失败
	// 将新的结点插入到头结点和第1个有效结点之间
	NewNode->data = x;
	NewNode->next = S->top->next;
	S->top->next = NewNode;
	S->length++; // 长度++
	return true;
}

// 出栈（带头结点）
bool PopLStack(LinkStack* S, ElemType* x) {
	if (IsEmptyLStack(S)) return false; // 如果是空栈，返回false
	LinkNode* OldTop = S->top->next; // 将第一个有效结点地址保护下来
	*x = OldTop->data;
	S->top->next = OldTop->next; // 将头结点后继指向原第2个结点
	free(OldTop); // 释放原来的第一个结点
	S->length--; // 长度--
	return true;
}

// 获取栈顶元素
bool GetTopLStack(LinkStack* S, ElemType* x) {
	if (IsEmptyLStack(S)) return false; // 空栈，返回false
	*x = S->top->next->data; // 头结点后继结点是第一个结点
	return true;
}

// 判断栈空
bool IsEmptyLStack(LinkStack* S) {
	return S->top->next == NULL; // 如果头结点的后继结点指向NULL，则表示为栈空
}

// 获取栈的大小
int GetLengthLStack(LinkStack* S) {
	return S->length;
}

// 遍历打印
void PrintLStack(LinkStack* S) {
	if (IsEmptyLStack(S)) {
		printf("空栈\n");
		return;
	}
	LinkNode* cur = S->top->next; // 从第一个有效结点开始
	printf("栈顶(头结点) -> ");
	while (cur != NULL) { // 如果是NULL，表示当前位置是最后结点的后继，则停止循环
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("栈底\n");
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布