【栈】顺序栈知识点

【栈】顺序栈知识点

目录

一、概念

栈与队列

栈

顺序栈

二、基本操作

定义

栈的初始化

判满

 判空

 扩容函数

入栈操作

出栈

 销毁

完整代码

---

一、概念

栈与队列

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

栈

• 我们把允许插入和删除的一端称为栈顶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-1return true;
}
//获取栈顶元素的值且删除
bool Pop(PSqStack ps, int* rtval)
{if (IsEmpty(ps))return false;*rtval = *(ps->top - 1);//top是当前元素，要插入的位置，而栈顶元素为top-1ps->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-1return true;
}//获取栈顶元素的值且删除
bool Pop(PSqStack ps, int* rtval)
{if (IsEmpty(ps))return false;*rtval = *(ps->top - 1);//top是当前元素，要插入的位置，而栈顶元素为top-1ps->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("%dn", val);}Destory(&sta);}

测试：