欢迎光临
【数据结构】栈和队列(栈篇)
   

【数据结构】栈和队列(栈篇)

目录

1.栈的概念及结构

2.栈的实现

2.1栈的结构体定义

2.2栈的常用接口函数

🐾栈的初始化

🐾插入数据

🐾删除数据

🐾取栈顶元素

🐾判断栈是否为空

🐾计算栈的大小

🐾栈的销毁

2.3完整的代码

 3.与栈有关的面试题


1.栈的概念及结构

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

【数据结构】栈和队列(栈篇),第1张

【数据结构】栈和队列(栈篇),第2张

 

2.栈的实现

栈和顺序表比较相似,学习了顺序表后,你会发现栈其实非常简单。下面就让我们一起来学习吧!

2.1栈的结构体定义

下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈

typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType a[N];
 int top; // 栈顶
}ST;

支持动态增长的栈

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

这里的top表示栈顶元素的位置,capacity表示栈的容量,a是一个指针,用于接收动态内存开辟数组的地址。

2.2栈的常用接口函数

下面是栈常用到的一些接口函数的声明。

//初始化
void StackInit(ST* ps);
//销毁
void StackDestroy(ST* ps);
//插入数据
void StackPush(ST* ps, STDataType x);
//删除数据
void StackPop(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//判断是否为空
bool StackEmpty(ST* ps);
//计算大小
int StackSize(ST* ps);

栈的初始化

使用断言(assert)确认传入的指针不为空。,然后将数组指针(a)设置为NULL,栈顶元素位置(top)设置为0,栈的容量(capacity)设置为0,完成栈的初始化操作。

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

 在定义完SL型结构体后,就要调用这个函数对栈进行初始化。

插入数据

这里的插入数据指的是压栈,如果栈已满(即栈顶位置等于栈的容量),则重新分配内存空间来扩大栈的容量。新容量的计算为原容量的两倍,如果原容量为0则设置为4。

//插入数据
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果栈已满,则重新分配内存空间,扩大容量
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//将数据x插入到栈顶,并更新栈顶位置
	ps->a[ps->top] = x;
	ps->top++;
}

删除数据

这步操作较为简单,将栈顶位置(ps->top)减1即可,表示删除栈顶元素。

//删除数据
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;  // 将栈顶位置减1,表示删除栈顶元素
}

取栈顶元素

注意栈顶元素数组编号是 top-1,然后返回该数组元素即可。

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

判断栈是否为空

如果top等于0,表示数组还没有存元素,栈就是空的。

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

计算栈的大小

因为top就是栈中元素的个数,所以直接返回top即可。

//计算大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

栈的销毁

使用free函数释放栈的数组内存空间(ps->a)。然后,将数组指针(ps->a)置为NULL,表示不再指向有效的内存空间。最后,将栈的顶部位置(ps->top)和容量(ps->capacity)都置为0,完成栈的销毁操作。

//销毁
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a); // 释放栈的数组内存空间
	ps->a = NULL; // 将数组指针置为NULL
	ps->top = ps->capacity = 0; // 将栈的顶部位置和容量都置为0
}

 在不再需要使用栈时,可以调用StackDestroy函数进行栈的销毁,以释放栈所占用的内存空间。

2.3完整的代码

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestSatck()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPush(&st, 6);
	
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");
	StackDestroy(&st);
}
int main()
{
	TestSatck();
	return 0;
}

 Stack.h文件

#pragma once
#include
#include
#include
#include
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);
//判断是否为空
bool StackEmpty(ST* ps);
//计算大小
int StackSize(ST* ps);

Stack.c文件

#include"Stack.h"
//初始化
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; // 将数组指针置为NULL
	ps->top = ps->capacity = 0; // 将栈的顶部位置和容量都置为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 = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//将数据x插入到栈顶,并更新栈顶位置
	ps->a[ps->top] = x;
	ps->top++;
}
//删除数据
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;  // 将栈顶位置减1,表示删除栈顶元素
}
//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
//判断是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//计算大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

 3.与栈有关的面试题

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

A. 12345ABCDE

B. EDCBA54321

C. ABCDE12345

D. 54321EDCBA

栈的特点是先进后出,根据给定的操作,将元素依次入栈,然后再依次出栈,元素出栈的顺序应该是如下所示:

EDCBA54321

根据出栈的顺序可知,最后入栈的元素E最先出栈,然后是D、C、B、A、5、4、3、2、1。因此,元素出栈的顺序是EDCBA54321。选项B)符合题目描述的操作结果。

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

根据排除法可以发现C项是不可能的,要想3先出栈,则1,2,3必须都先入栈,然后将3进行出栈,但是C项中第2个出栈的元素是1,而2必须在1之前出栈,因此C项错误。

 括号匹配

原题链接:力扣

【数据结构】栈和队列(栈篇),第3张

【数据结构】栈和队列(栈篇),第4张

 思路:遍历字符串s中的每个括号,如果是左括号就入栈,如果是右括号就出栈,并且互相比较。

typedef char 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);
//判断是否为空
bool StackEmpty(ST* ps);
//计算大小
//初始化
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->top = ps->capacity = 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 = (STDataType*)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++;
}
//删除数据
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
//判断是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//计算大小
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            STDataType top =StackTop(&st);
            StackPop(&st);
            if((top=='{'&&*s=='}')
            ||(top=='['&&*s==']')
            ||(top=='('&&*s==')'))
            {
                ++s;
            }
            else
            { 
               
                StackDestroy(&st);
                return false;
            }
        }
    }
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}
 
 灌木丛的英文  洛克菲勒名言  小飞蓬草图片  如歌的行板  义乌市鲜花店  华娱之别样人生 
打赏
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《【数据结构】栈和队列(栈篇)》
文章链接:https://goodmancom.com/wl/175673.html