目录
1.栈的概念及结构
2.栈的实现
2.1栈的结构体定义
2.2栈的常用接口函数
🐾栈的初始化
🐾插入数据
🐾删除数据
🐾取栈顶元素
🐾判断栈是否为空
🐾计算栈的大小
🐾栈的销毁
2.3完整的代码
3.与栈有关的面试题
1.栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
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<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);
//判断是否为空
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项错误。
括号匹配
原题链接:力扣
文章来源:https://www.toymoban.com/news/detail-519133.html
思路:遍历字符串s中的每个括号,如果是左括号就入栈,如果是右括号就出栈,并且互相比较。文章来源地址https://www.toymoban.com/news/detail-519133.html
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;
}
到了这里,关于【数据结构】栈和队列(栈篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!