1. AI技术聚合首页
  2. IT

【数据结构】栈和队列（栈篇）

xiaoxingxing • • IT • 阅读 40

目录

🐾

🐾

🐾

🐾

🐾

🐾

🐾

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项错误。

 括号匹配

原题链接：力扣

 思路：遍历字符串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;
}

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月14日
下一篇 2023年12月14日

相关推荐