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

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

1年前作者：夏微凉.分类：Toy博客阅读(10)违法举报

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

目录

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日
    浏览(7)
  • 【数据结构】—手把手带你用C语言实现栈和队列（超详细！）

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

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

    2024年02月14日
    浏览(205)

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

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

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

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

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

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

    [数据结构】栈和队列

    目录 1.栈 1.1概念 1.2 栈的使用 1.3.栈的模拟实现 2.队列 2.1概念 2.2队列的使用 2.3队列的模拟实现 2.4 循环队列 2.5双端队列   栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素

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

    数据结构--栈和队列

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

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

    数据结构——栈和队列

    目录  一.前言 二.前文回顾 三.栈 3.1 栈的概念及结构 3.2 栈的实现 3.2.1 初始化函数 3.2.2 销毁函数 3.2.3 入栈函数 3.2.4 出栈函数 3.2.5 计算大小函数 3.2.6 空栈函数 3.2.7 获取栈顶函数  3.2.8 小测试 3.3 全部代码 四.栈的练习 4.1 有效的括号 五.队列 5.1队列的概念及结构 5.2 队列的实

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

    数据结构：栈和队列

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

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

    数据结构【栈和队列】

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

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

    数据结构 | 栈和队列

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

    2024年01月23日
    浏览(15)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包