1. Toy模板网首页
  2. > Toy博客

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

7月前 作者：夏微凉. 分类：Toy博客 阅读(27) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】栈和队列（栈篇）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

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

 括号匹配

原题链接：力扣

【数据结构】栈和队列（栈篇）,数据结构,数据结构,开发语言

【数据结构】栈和队列（栈篇）,数据结构,数据结构,开发语言

 思路：遍历字符串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模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构入门（C语言版）栈和队列之队列的介绍及实现

    数据结构入门（C语言版）栈和队列之队列的介绍及实现

    什么是队列呢？我们先看下面的图： 我们可以理解成高速公路上的隧道，根据这个图的描述 我们把需入队的元素看作一辆车，把队列看作隧道，由此我们可以看出 队列的特点是 只允许从一端进入，从另一端离开。 队列就是只允许在一端进行插入数据操作，在另一端进行删

    2023年04月15日
    浏览(29)
  • 【数据结构】—手把手带你用C语言实现栈和队列（超详细！）

    【数据结构】—手把手带你用C语言实现栈和队列（超详细！）

                                       食用指南：本文在有C基础的情况下食用更佳                                     🔥 这就不得不推荐此专栏了：C语言                                   ♈️ 今日夜电波：Tell me —milet                    

    2024年02月14日
    浏览(35)

  • 数据结构（C语言实现）——栈和队列的介绍及基本操作的实现（动态顺序栈+链队）

    今天我们来学习另外两个线性结构——栈和队列，栈和队列是操作受限的线性表，因此，可称为限定性的数据结构。 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守

    2023年04月19日
    浏览(29)
  • 【数据结构】栈和队列(队列篇）

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

    上期我们已经学习了数据结构中的栈，这期我们开始学习队列。 目录 1.队列的概念及结构 2.队列的实现 队列结构体定义 常用接口函数 初始化队列 队尾入队列 队头出队列 获取队列头部元素、 获取队列队尾元素 获取队列中有效元素个数 检测队列是否为空 销毁队列 3.循环队

    2024年02月13日
    浏览(31)
  • 栈和队列【数据结构】

    栈和队列【数据结构】

    2024年02月16日
    浏览(27)
  • 数据结构--栈和队列

    数据结构--栈和队列

    栈是一种常见的数据结构，它遵循 后进先出LIFO （Last In First Out）的原则。 进行数据插入和操作的一端称为栈顶，另一端称为栈底 。 压栈 ：栈的插入操作被称为压栈/进栈/入栈，入数据在栈顶。 出栈 ：栈的删除操作。出数据也在栈顶； 栈可以用 数组 或者是 链表 来实现；

    2024年02月09日
    浏览(28)
  • 数据结构 | 栈和队列

    数据结构 | 栈和队列

    … 📘📖📃本文已收录至：数据结构 | C语言 更多知识尽在此专栏中! 栈（Stack） 又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。 队列（Queue） 也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的

    2024年01月23日
    浏览(30)
  • 数据结构：栈和队列

    数据结构：栈和队列

    朋友们、伙计们，我们又见面了，本期来给大家解读一下栈和队列方面的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！ C 语 言 专 栏：C语言：从入门到精通 数据结构专栏：数据结构 个 人 主 页 ：  stackY、 目录 前言：  1.栈 1.1栈的

    2024年02月06日
    浏览(26)
  • 数据结构【栈和队列】

    数据结构【栈和队列】

    一、栈 1.定义：只允许一端进行插入和删除的线性表，结构与手枪的弹夹差不多，可以作为实现递归函数（调用和返回都是后进先出）调用的一种数据结构； 栈顶：允许插入删除的那端； 栈底：固定的，不允许插入或删除； 空栈：不含元素； 2.特点：后进先出； 3.操作：入

    2024年02月15日
    浏览(28)

  • 数据结构---栈和队列

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

    2024年01月18日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包