数据结构之栈

发布于:2025-07-31 ⋅ 阅读:(31) ⋅ 点赞:(0)

1.栈的概念

  • 栈:仅在表尾进行插入和删除操作的线性表,栈的数据遵守后进先出LIFO(Last In Firist Out)原则.
  • 栈顶:允许插入和删除的一端
  • 栈底:另一端
  • 栈的插入操作:叫做进栈,也称做压栈,入栈
  • 栈的删除操作:叫做出栈
  • 特殊点:限制了线性表的插入和删除位置,始终只在栈顶进行,栈底是固定的,最先进栈的只能在栈底

小思考:最先进栈的是不是只能最后出栈?

不一定
例:要求,1、2、3要按顺序进栈,那么会有几种出栈次序呢?

1.1进 1出,2进 2出,3进 3出 顺序 1 2 3

2.1进 1出, 2进 3进 3出 2出 1 3 2

3.1进 2进 2出 1出,3进 3出 2 1 3

4.1进 2进 2出 3进 3出 1出 2 3 1

5.1进 2进 3进 3出 2出 1出 3 2 1

那么可能是 3 1 2吗

不可能

why:既然3都进栈了,且其他两个数没有出栈,那么2一定在1之前出栈

2.顺序栈

与顺序表相似

//Test.c

#pragma one

#include"Stack.h"

int main()
{
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d  ",STTop(&st));
		STPop(&st);
	}

	STDestroty(&st);

	return 0;
}
//Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;

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

void STInit(ST*ps); 
void STDestroty(ST* ps);

void STPush(ST* ps,STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);

//Stack.c

#include"Stack.h"

void STInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0;			//代表top是栈顶元素的下一个位置
	//ps->top = -1;			//代表top是栈顶元素
}

void STDestroty(ST* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;

}

void STPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity *= 2;

	}
	ps->a[ps->top] = x;
	ps->top++;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	ps->top--;
}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];
}

小思考:既然有了用数组或者顺序表、链表直接来实现功能,为什么还要引入栈呢?

答:栈这一数据结构的引入,极大地简化了程序设计工作。它巧妙地划分出不同的关注层次,让开发者能够从复杂的问题情境中抽离出来,将思考范围精准聚焦于问题解决的核心部分,从而更高效地攻克难题。

本文部分内容总结自《大话数据结构》


网站公告

今日签到

点亮在社区的每一天
去签到