数据结构--顺序栈【C语言描述】


一.相关概念:

1.栈和队列是操作受限的线性表,是限定性的数据结构;
2.栈分为顺序栈和链式栈
3.栈只能在一端进行操作(插入,删除);
4.栈是限定仅在表尾进行插入或删除操作的线性表.因此,对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom).
5.不含元素地空表称为空栈.


二.顺序栈的结构:

typedef struct Stack{	
        int* base;//指向动态内存;	
        int top;//栈顶指针,实际上是下标,其实就是可以放数据的下标
	int stacksize;//栈的总大小
}Stack,*PStack;


三.顺序栈的实现

//初始化
static bool IsFull(PStack ps)
{
	return ps->top == ps->stacksize;
}

static  void  Inc(PStack ps)
{
	ps->stacksize *= 2;
	ps->base = (int*)realloc(ps->base, ps->stacksize * sizeof(int));
	assert(ps->base != NULL);
	//ps->top不处理
}

//往栈中入数据(入栈操作)
bool  Push(PStack ps, int val)//O(1)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	if (IsFull(ps))
	{
		Inc(ps);
	}
	//在表尾插入,即入栈
	ps->base[ps->top++] = val;
	//ps->top++;
	return true;
}

//获取栈顶元素的值,但是不删除
//输出参数
bool  GetTop(PStack ps,int *rtval)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}

	if (IsEmpty(ps))
	{
		return   false;
	}
	*rtval=ps->base[ps->top - 1];
	return true;	
}

//获取栈顶元素的值,但是删除
bool   Pop(PStack ps,int *rtval)
{
	assert(ps != NULL);
	if (ps == NULL)
	{
		return false;
	}

	if (IsEmpty(ps))
	{
		return   false;
	}
	//*rtval = ps->base[ps->top - 1];//OK
	//ps->top--;//OK
	*rtval = ps->base[--ps->top];
	return true;
}

//判空
bool IsEmpty(PStack ps)
{
	return ps->top == 0;
}

//获取栈中有效元素的个数
int  GetLength(PStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return  -1;

	return ps->top;//top为有效数据的个数
}

//清空所有的数据
void Clear(PStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;

	ps->top = 0;
}

//销毁
void Destroy(PStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;

	free(ps->base);
	ps->base = NULL;
	ps->top = 0;
	ps->stacksize = 0;
}

四.顺序栈的总结:
 

1.栈的特点:后进先出,后来的反而需要先服务(访问受限的线性表)
2.栈又分为顺序栈和链式栈 3.上面顺序栈是不定长的顺序栈,能自动扩容
4.栈只能在一端进行插入和删除,插入和删除的这一端称之为栈顶,另一端称之为栈底; 5.顺序栈的栈顶在尾部,因为入栈和出栈的时间复杂度为O(1)


本篇完!

相关推荐

  1. 算法与数据结构 顺序C++)

    2024-04-02 14:12:03       4 阅读
  2. 数据结构——顺序表(C语言版)

    2024-04-02 14:12:03       7 阅读
  3. 数据结构——顺序表(C语言

    2024-04-02 14:12:03       8 阅读

最近更新

  1. npm常用命令详解

    2024-04-02 14:12:03       0 阅读
  2. 生活无趣感的成因与破解之道

    2024-04-02 14:12:03       0 阅读
  3. 大数据集群中部署Hive

    2024-04-02 14:12:03       0 阅读
  4. CMake

    CMake

    2024-04-02 14:12:03      0 阅读
  5. Hive进阶Day06

    2024-04-02 14:12:03       0 阅读

热门阅读

  1. ES6中的Map与Set

    2024-04-02 14:12:03       4 阅读
  2. C语言中向函数中传递函数指针的方法

    2024-04-02 14:12:03       6 阅读
  3. 简单设计模式讲解

    2024-04-02 14:12:03       5 阅读
  4. C++命名空间详解

    2024-04-02 14:12:03       8 阅读
  5. 【Ubuntu】可配置环境变量位置

    2024-04-02 14:12:03       6 阅读
  6. 洛谷 1803.凌乱的yyy

    2024-04-02 14:12:03       5 阅读