栈的深度解析：顺序栈与链栈的实现

平凡之路.

发布于 2024-10-09 15:08:33

1030

发布于 2024-10-09 15:08:33

文章被收录于专栏：学习

引言

栈是一种重要的线性数据结构，遵循“后进先出”（LIFO）的原则。栈的应用非常广泛，如表达式求值、括号匹配、递归实现等。在本文中，我们将深入探讨栈的概念，并通过顺序栈和链栈两种实现方式进行对比分析。

一、基本概念

1.1 定义

栈（Stack）是一种只能在一端进行插入和删除操作的集合，遵循“后进先出”（LIFO）原则。即最后加入的元素最先被移除

1.2 基本操作

入栈（Push）：将新元素添加到栈顶。
出栈（Pop）：移除并返回栈顶元素。
查看栈顶元素（Peek）：返回栈顶元素，但不删除它。
判断是否为空（isEmpty）：检查栈是否没有元素。
统计栈的大小（Size）：获取栈中有效元素个数。

1.3 特点

操作限制：只能在栈顶进行元素的添加（入栈）和移除（出栈）。 栈顶元素：栈顶是当前可以访问和操作的元素。空栈：栈为空时，无法进行出栈操作。

二、栈的实现

2.1 顺序栈

使用数组实现栈时，我们可以将数组的尾部作为栈顶。

入栈与出栈操作分别对应在数组尾部。添加元素与删除元素，时间复杂度都为 𝑂(1) 。

2.1.1 基本结构

typedef struct Stack
{
	DataType* arr;//数组实现
	int top;//栈顶
	int capacity;//记录容量
}ST;

2.1.2 功能实现

1).初始化栈

//初始化栈
void StackInit(ST* p)
{
	assert(p);
	p->arr = NULL;
	p->top = p->capacity = 0;
}

2).销毁栈

//销毁栈
void StackDestory(ST* p)
{
	assert(p);
	if (p->arr)
	{
		free(p->arr);
	}
	p->arr = NULL;
	p->top = p->capacity = 0;
}

3).入栈

//入栈
void StackPush(ST* p,DataType x)
{
	assert(p);
	checkcapacity(p);
	p->arr[p->top++] = x;
}

4).判空

//判断栈顶是否为空
bool StackEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

5).出栈

//出栈
void StackPop(ST* p)
{
	assert(p);
	assert(!StackEmpty(p));//栈顶不为空才能删除
	--p->top;
}

6).取栈顶元素

//取栈顶元素
DataType StackTop(ST* p)
{
	assert(p);
	assert(!StackEmpty(p));
	return p->arr[p->top - 1];
}

7).栈长度

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

2.2 链式栈

使用链表实现栈时，我们可以将链表的头节点视为栈顶，尾节点视为栈底。

对于入栈操作，我们只需将元素插入链表头部，这种节点插入方法被称为“头插法”。而对于

出栈操作，只需将头节点从链表中删除即可。

2.2.1 基本结构

//定义节点结构
typedef struct Node {
	DataType data;//数据域
	struct Node *next;//指针域
}Node;
// 定义链栈结构
typedef struct Stack{
	Node* top;            // 栈顶指针
	int size;             // 栈中有效元素个数
} ST;

2.2.2 功能实现

1).初始化栈

//初始化栈
void StackInit(ST* p)
{
	assert(p);
	p->top = NULL;
	p->size = 0;
}

2).销毁栈

//销毁栈
void StackDestory(ST* p) {
	Node* pcur = p->top; // 从栈顶开始
	Node* temp;

	while (pcur != NULL) {
		temp = pcur;         // 记录当前节点
		pcur = pcur->next; // 移动到下一个节点
		free(temp);             // 释放当前节点的内存
	}

	p->top = NULL;          // 将栈顶指针设置为 NULL
	p->size = 0;            // 重置栈的大小
}

3).入栈

//创建节点
//Node* CreateNode(DataType x)
//{
//	Node* newnode = (Node*)malloc(sizeof(Node));
//	if (newnode == NULL) {
//		perror("malloc fail");
//		exit(1);
//	}
//	newnode->data = x;
//	newnode->next = NULL;
//	return newnode;
//}

//入栈
void StackPush(ST* p,DataType x)
{
	assert(p);
	Node* newnode = CreateNode(x);
	newnode->next = p->top->next;
	p->top->next = newnode;
	++p->size;
}

4).判空

//判断栈顶是否为空
bool StackEmpty(ST* p)
{
	assert(p);
	return p->top->next==NULL;//p->top->next是栈顶元素
}

5).出栈

//出栈
void StackPop(ST* p)
{
	assert(p);
	assert(!StackEmpty(p));//栈顶不为空才能删除
	Node* temp = p->top->next;
	p->top->next = p->top->next->next;
	free(temp);
	temp = NULL;
	--p->size;
}

6).取栈顶元素

//取栈顶元素
DataType StackTop(ST* p)
{
	assert(p);
	return p->top->next->data;
}

7).栈长度

//获取栈中有效元素个数
int StackSize(ST* p)
{
	assert(p);
	return p->size;
}

2.3 对比

特点	顺序栈	链式栈
存储结构	基于数组	基于链表
内存管理	静态分配(也可动态扩容)	动态分配
空间效率	容量固定(也可动态扩容)	动态扩展
访问速度	O(1)时间复杂度	O(1)时间复杂度
栈溢出	容易发生	不易发生

三、完整代码

3.1 顺序栈

Stack.h

该部分主要包括函数的声明、以及头文件的引用

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
typedef struct Stack
{
	DataType* arr;//数组实现
	int top;//栈顶
	int capacity;//记录容量
}ST;
//初始化栈
void StackInit(ST* p);
//销毁栈
void StackDestory(ST* p);
//入栈
void StackPush(ST* p, DataType x);
//出栈
void StackPop(ST* p);
//取栈顶元素
DataType StackTop(ST* p);
//获取栈中有效元素个数
int StackSize(ST* p);

Stack.c

该部分主要包括函数的定义

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
//初始化栈
void StackInit(ST* p)
{
	assert(p);
	p->arr = NULL;
	p->top = p->capacity = 0;
}
//销毁栈
void StackDestory(ST* p)
{
	assert(p);
	if (p->arr)
	{
		free(p->arr);
	}
	p->arr = NULL;
	p->top = p->capacity = 0;
}
//判断扩容
void checkcapacity(ST* p)
{
	assert(p);
	if (p->capacity == p->top)
	{
		int NewCap = p->capacity == 0 ? 4 : 2 * p->capacity;
		DataType* tmp = (DataType*)realloc(p->arr, NewCap * sizeof(DataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		p->arr = tmp;
		p->capacity = NewCap;
	}
}
//入栈
void StackPush(ST* p,DataType x)
{
	assert(p);
	checkcapacity(p);
	p->arr[p->top++] = x;
}
//判断栈顶是否为空
bool StackEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}
//出栈
void StackPop(ST* p)
{
	assert(p);
	assert(!StackEmpty(p));//栈顶不为空才能删除
	--p->top;
}
//取栈顶元素
DataType StackTop(ST* p)
{
	assert(p);
	assert(!StackEmpty(p));
	return p->arr[p->top - 1];
}
//获取栈中有效元素个数
int StackSize(ST* p)
{
	assert(p);
	return p->top;
}

main.c

该部分用来测试，即函数的使用

#define _CRT_SECURE_NO_WARNINGS
#include"Stack.h"
void test01()
{
	ST st;
	StackInit (&st);
	StackPush (&st,1);
	StackPush (&st,3);
	StackPush (&st,5);
	StackPush (&st,7);
	while (!StackEmpty(&st))//栈顶元素依次出栈
	{
		DataType  data = StackTop(&st);
		printf("%d ", data);
		StackPop(&st);//出栈
	}
}
int main()
{
	test01();
	return 0;
}

3.2 链式栈