【数据结构】详解栈

分类:热门推荐日期:2024-05-10浏览:1评论:0

今天我们主要来了解栈！如果对知识点有模糊，可翻阅以往文章哦！

个人主页：小八哥向前冲~-CSDN博客

所属专栏：数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客

c语言专栏：c语言_小八哥向前冲~的博客-CSDN博客

值得注意的是，如果你十分了解顺序表和链表，今天这期会很轻松哦！

哈哈哈哈！当然，这期也能检测你对顺序表和链表的理解！一起看看吧！

目录

栈的定义

顺序表和链表的比较

栈的实现--顺序表

初始化

栈为空的判定

入栈

出栈

销毁

栈顶数据

数据个数

题目操练：配括号问题

栈的实现--链表

栈为空的判定

入栈

出栈

销毁

栈顶数据

数据个数

码源--栈（顺序表）

码源--栈（链表）

栈的定义

  • 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
  • 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
  • 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

    上图理解一下：

    注意：遵循后进先出的原则！

    知道了这个原则，我们来巩固一下：

    1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出 栈的顺序是（ ）。

    A .12345ABCDE

    B.EDCBA54321

    C.ABCDE12345

    D.54321EDCBA

    2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

    A.1,4,3,2

    B.2,3,4,1

    C.3,1,4,2

    D.3,4,2,1

    显然：1.B      2.C

    相信第一题不难，我们解释一下第二题：看到C选项，1，2，3进栈后，3出栈，而第二次出栈的只能是2或4，不可能是1，所以C错误！

    了解了栈的概念，我们实现这个栈是使用顺序表还是链表呢？

    • 如果是顺序表的话，我们的栈顶应该要在数组末尾！如果在数组头部的话，数据进栈时还需要挪动其余数据以便数据的存入！效率很低！
    • 如果是链表的话，我们的栈顶要在链表的头，入栈时，头插即可！如果栈顶在链表尾部的话，虽然入栈尾插即可，但需要遍历，效率低，那么这时就需要使用双链表！

      综上所述，我们栈使用顺序表较好！(两种都实现看看)

      上图看看它们：

      为了更好透彻了解顺序表和链表，我们将它们比较看看！

      顺序表和链表的比较

      图文更加直观：

      这里的缓存利用率不做过多解释，详情见：https://www.cnblogs.com/yungyu16/p/13054874.html

      栈的实现--顺序表

      既然是要在顺序表基础上实现栈，那么就要实现顺序表和栈的基本框架。

      （单链表若有不懂的知识点，可见：通讯录的实现（顺序表版本）-CSDN博客）

      stack.h文件--包含各种需要的函数

      栈里面的变量：top表示栈顶下标，capacity表示栈空间。

      #include#include#include
#includetypedef int STDateType;
//栈
typedef struct stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);

      接下来我们一一实现！

      初始化

      我们要将栈中各个变量进行初始化。

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

      栈为空的判定

      我们在实现这个函数时，很多人会用 if语句来判断是否为空，但我们仔细一想，可以好好优化一下代码！

      //判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

      入栈

      经过我们刚刚的分析，入栈要在数组尾部！记得每次入栈需要判断空间是否够用哦！

      void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}

      出栈

      入栈要在尾部，出栈也要在尾部，后进先出的原则要时刻记住！

      需要注意的是：当栈为空时，数据出不了栈！所以我们先需要判断是否为空！

      void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}

      销毁

      我们既然用了开辟内存函数，当我们不使用栈时，要将空间释放掉！

      void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}

      栈顶数据

      在访问栈顶数据时，我们也要先判断栈是否为空，否则当栈为空时，访问栈顶数据便会越界访问！

      //栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}

      数据个数

      //栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}

      题目操练：配括号问题

      既然我们已经实现的栈，我们来应用一下吧！

      题目：详情--20. 有效的括号 - 力扣（LeetCode）

      思路：

      遍历数组，当是左括号时（"(","{","】"）时就入栈，当不是左括号时就出栈比较，直到遍历完成！

      这样听是不是很简单呢？当然里面没有栈，我们需要将栈创建一下！

      代码：

      typedef char STDateType;
//栈
typedef struct stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);
//栈的初始化和销毁
void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = 0;
	p->top = 0;
}
void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}
//入栈，出栈
void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}
void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}
//栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}
//栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}
//判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
//左括号入栈
        if(*s=='('||*s=='['||*s=='{')
        {
            STpush(&st,*s);
        }
        else
//不是左括号出栈比较
        {
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            char top=STtop(&st);
            STpop(&st);
            if(top=='('&&*s!=')'
            ||top=='['&&*s!=']'
            ||top=='{'&&*s!='}')
            {
            STDestroy(&st);
            return false;
            }
        }
        s++;
    }
//当栈中没有左括号比较完时，便匹配不成
    bool ret=STEmpty(&st);
    STDestroy(&st);
    return ret;
}

      可能有人说太麻烦了，但c语言中没有栈，只能自己创建哦！这是用目前c语言最简单的方法！

      栈的实现--链表

      和顺序表一样，我们首先要创建栈和链表的基本框架！

      stack.h文件--包含需要的函数

      #include#include#include
#includetypedef int STDataType;
//栈
typedef struct stack
{
	struct stcak* next;
	STDataType data;
}STNode;
//栈的销毁
void STDestroy(STNode* phead);
//入栈
void STpush(STNode** pphead,STDataType x);
//出栈
void STpop(STNode** pphead);
//栈顶数据
STDataType STtop(STNode* phead);
//判空
bool STEmpty(STNode* phead);
//栈数据个数
int STsize(STNode* phead);

      栈为空的判定

      有了顺序表的基础，接下来依葫芦画瓢----最简单不过！

      //判空
bool STEmpty(STNode* phead)
{
	return phead == NULL;
}

      入栈

      我们分析将链表的头部为栈顶，进出都在头！（这种方案最佳！）

      //创建节点
STNode* STBuyNode(STDataType x)
{
	STNode* node = (STNode*)malloc(sizeof(STNode));
	if (node == NULL)
	{
		perror("malloc failed!");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	return node;
}
//入栈
void STpush(STNode** pphead, STDataType x)
{
	STNode* node = STBuyNode(x);
	node->next = *pphead;
	*pphead = node;
}

      出栈

      将头节点指向下一个节点，原来的头节点释放！

      //出栈
void STpop(STNode** pphead)
{
	assert(!STEmpty(*pphead));
	STNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}

      销毁

      同样的，动态开辟了空间，当我们不用栈时，要将开辟的空间释放掉！

      //栈的销毁
void STDestroy(STNode* phead)
{
	STNode* cur = phead;
	while (cur)
	{
		STNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

      栈顶数据

      也是一样的，在访问栈顶数据时，要判断栈是否为空，防止越界访问！

      //栈顶数据
STDataType STtop(STNode* phead)
{
	assert(!STEmpty(phead));
	return phead->data;
}

      数据个数

      遍历链表，将一个一个节点计数起来！

      //栈数据个数
int STsize(STNode* phead)
{
	STNode* cur = phead;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

      码源--栈（顺序表）

      stack.h文件

      #include#include#include
#includetypedef int STDateType;
//栈
typedef struct stack
{
	STDateType* a;
	int top;
	int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* p);
void STDestroy(ST* p);
//入栈，出栈
void STpush(ST* p,STDateType x);
void STpop(ST* p);
//栈顶的数据
STDateType STtop(ST* p);
//栈的数据个数
int STsize(ST* p);
//判空
bool STEmpty(ST* p);

      stack.c文件

      #include"stack.h"
//栈的初始化和销毁
void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = 0;
	p->top = 0;
}
void STDestroy(ST* p)
{
	assert(p);
	free(p->a);
	p->capacity = p->top = 0;
}
//入栈，出栈
void STpush(ST* p, STDateType x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(p->a, newcapacity * sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc failed!");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;
	}
	p->a[p->top++] = x;
}
void STpop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	p->top--;
}
//栈顶的数据
STDateType STtop(ST* p)
{
	assert(p);
	//出栈的话要判断一下空的情况
	assert(!STEmpty(p));
	return p->a[p->top-1];
}
//栈的数据个数
int STsize(ST* p)
{
	assert(p);
	return p->top;
}
//判空
bool STEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}

      码源--栈（链表）

      stack.h文件

      #include#include#include
#includetypedef int STDataType;
//栈
typedef struct stack
{
	struct stcak* next;
	STDataType data;
}STNode;
//栈的销毁
void STDestroy(STNode* phead);
//入栈
void STpush(STNode** pphead,STDataType x);
//出栈
void STpop(STNode** pphead);
//栈顶数据
STDataType STtop(STNode* phead);
//判空
bool STEmpty(STNode* phead);
//栈数据个数
int STsize(STNode* phead);

      stack.c文件

      #include"stack.h"
STNode* STBuyNode(STDataType x)
{
	STNode* node = (STNode*)malloc(sizeof(STNode));
	if (node == NULL)
	{
		perror("malloc failed!");
		return NULL;
	}
	node->data = x;
	node->next = NULL;
	return node;
}
//入栈
void STpush(STNode** pphead, STDataType x)
{
	STNode* node = STBuyNode(x);
	node->next = *pphead;
	*pphead = node;
}
//出栈
void STpop(STNode** pphead)
{
	assert(!STEmpty(*pphead));
	STNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}
//栈顶数据
STDataType STtop(STNode* phead)
{
	assert(!STEmpty(phead));
	return phead->data;
}
//判空
bool STEmpty(STNode* phead)
{
	return phead == NULL;
}
//栈数据个数
int STsize(STNode* phead)
{
	STNode* cur = phead;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
//栈的销毁
void STDestroy(STNode* phead)
{
	STNode* cur = phead;
	while (cur)
	{
		STNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

      是不是觉得今天的比较简单？好了，我们下期见！

相关推荐

关于我们常见问题广告服务免责声明联系我们
Powered By Z-BlogPHP 1.7.3 Theme By 优美主题
Copyright Your WebSite.Some Rights Reserved. 浙ICP备2023018783号