【栈】顺序栈知识点-内含基本操作及其说明_pop是出栈还是入栈

目录

一、概念

栈与队列

栈

顺序栈

二、基本操作

定义

栈的初始化

判满

 判空

 扩容函数

入栈操作

出栈

 销毁

完整代码

---

一、概念

栈与队列

• 栈是限定仅在表尾进行插入和删除操作的线性表
• 队列是只允许在一端进行插入操作、而另一端进行删除操作的线性表
• 栈：先进后出
• 队：先进先出

栈

• 我们把允许插入和删除的一端称为栈顶top，另一端称为栈底
• 不含任何数据元素的栈称为空栈
  • 
• 首先栈是一个线性表，因此它具有线性关系，即前驱后继关系
• 栈底是固定的，最先进栈的只能在栈底
• 栈的插入操作push叫做进栈，也叫做入栈、压栈
• 栈的删除操作pop叫做出栈，也叫做弹栈
  • 
• 栈顶：数据插入和删除的一端。栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器来指示。

顺序栈

栈的顺序存储其实就是线性表顺序存储的简化，我们简称为顺序栈

二、基本操作

入栈、出栈、获取栈顶元素、销毁、判空

定义

//栈
#define INITSIZE 10
typedef int ElemType;
typedef struct
{
	ElemType* base;//存放数据的指针
	ElemType* top;//栈顶指针，指向当前可以存放数据的地址
	int stacksize;//当前总容量
}SqStack, * PSqStack;//sizeof=12;12个字节

栈的初始化

栈底：动态创建内存

栈顶初始化=栈底

栈内总容量为INITSIZE

//初始化
void InitStack(PSqStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	ps->base = (ElemType*)malloc(INITSIZE * sizeof(ElemType));
	ps->top = ps->base;
	ps->stacksize = INITSIZE;
}

判满

判满函数属于内部函数，因为外部函数一般都是动态创建内存，不需要判满。

判满条件：数据个数（即当前栈顶位置-栈底0）与容量相等时，栈满。

//判满-内部函数：数据个数和容量相等
static bool IsFull(PSqStack ps)
{
	return (ps->top - ps->base) == ps->stacksize;
//指针相减是俩指针之间的间隔也就是数据个数
}

 判空

//判空：栈顶==栈底
bool IsEmpty(PSqStack ps)
{
	return ps->top == ps->base;
}

 扩容函数

base数组：扩大为原容量*2

realloc:扩容函数

扩容的实质不是在原数组后面再开辟空间，而是重新开辟原数组二倍的空间。

top：需要重新对新数组base进行指向栈顶：栈顶为栈底+原容量base+stacksize的位置

原栈容量*2：satcksize*2

栈空：ps->base==NULL;栈底为空

//扩容:把容量扩大为原来二倍
static void Inc(PSqStack ps)
{	ps->base = (ElemType*)realloc(ps->base, ps->stacksize * 2 * sizeof(ElemType));
	assert(ps->base != NULL);
	if (ps->base == NULL)
		return;
	ps->top = ps->base + ps->stacksize;
	ps->stacksize *= 2;
}

入栈操作

先判满，如果栈满，扩容

入栈操作：元素赋值到栈顶，栈顶++

//入栈
bool Push(PSqStack ps, ElemType val)
{
	if (IsFull(ps))
	{
		Inc(ps);
	}
	*(ps->top) = val;
	ps->top++;
	return true;
}

出栈

函数的设计：bool来判断返回值是否为空，想要把数据带回必须用到指针，因此第二个参数设为指针类型，带回栈顶元素的值。

有两类出栈操作：

//获取栈顶元素的值,但不删除
bool GetTop(PSqStack ps, int* rtval)
{
	if (IsEmpty(ps))
		return false;
	*rtval = *(ps->top - 1);//top是当前元素，要插入的位置，而栈顶元素为top-1
	return true;
}
//获取栈顶元素的值且删除
bool Pop(PSqStack ps, int* rtval)
{
	if (IsEmpty(ps))
		return false;
	*rtval = *(ps->top - 1);//top是当前元素，要插入的位置，而栈顶元素为top-1
	ps->top--;//删除top-1
//上面两步可以合并为：*rtval = *(--ps->top - 1);
	return true;
}

 销毁

//销毁
void Destory(PSqStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	free(ps->base);
	ps->base = NULL;
	ps->top = NULL;
	ps->stacksize = 0;
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
//栈
#define INITSIZE 10
typedef int ElemType;
typedef struct
{
	ElemType* base;//存放数据的指针
	ElemType* top;//栈顶指针，指向当前可以存放数据的地址
	int stacksize;//当前总容量
}SqStack, * PSqStack;//sizeof=12;12个字节
 
//初始化
void InitStack(PSqStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	ps->base = (ElemType*)malloc(INITSIZE * sizeof(ElemType));
	ps->top = ps->base;
	ps->stacksize = INITSIZE;
}
//判满-内部函数：数据个数和容量相等
static bool IsFull(PSqStack ps)
{
	return (ps->top - ps->base) == ps->stacksize;
}
//扩容:把容量扩大为原来二倍
static void Inc(PSqStack ps)
{//扩容-realloc函数：改变所指内存区域的大小
	ps->base = (ElemType*)realloc(ps->base, ps->stacksize * 2 * sizeof(ElemType));
	assert(ps->base != NULL);
	if (ps->base == NULL)
		return;
	ps->top = ps->base + ps->stacksize;
	ps->stacksize *= 2;
}
//入栈
bool Push(PSqStack ps, ElemType val)
{
	if (IsFull(ps))
	{
		Inc(ps);
	}
	*(ps->top) = val;
	ps->top++;
	return true;
}
//判空
bool IsEmpty(PSqStack ps)
{
	return ps->top == ps->base;
}
 
//获取栈顶元素的值,但不删除
bool GetTop(PSqStack ps, int* rtval)
{
	if (IsEmpty(ps))
		return false;
	*rtval = *(ps->top - 1);//top是当前元素，要插入的位置，而栈顶元素为top-1
	return true;
}
 
//获取栈顶元素的值且删除
bool Pop(PSqStack ps, int* rtval)
{
	if (IsEmpty(ps))
		return false;
	*rtval = *(ps->top - 1);//top是当前元素，要插入的位置，而栈顶元素为top-1
	ps->top--;//删除top-1
	//上面两步可以合并为：*rtval = *(--ps->top - 1);
	return true;
}
//销毁
void Destory(PSqStack ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	free(ps->base);
	ps->base = NULL;
	ps->top = NULL;
	ps->stacksize = 0;
}
 
int main()
{
	SqStack sta;
	InitStack(&sta);
	for (int i = 0; i < 30; i++)
	{
		Push(&sta, i);//入栈
	}
	int val;
	while (!IsEmpty(&sta))
	{
		Pop(&sta, &val);//出栈
		printf("%d\n", val);
	}
	Destory(&sta);
 
}
 

测试：