主页 分类 关于

数据结构 栈和堆

数据结构学习笔记

栈的类型定义

  • 也称为堆栈, 是一种先进后岀, 删除和插入都在栈顶操作的线性表

    • 堆是指重新运行时的动态内存
    • 栈是指使用堆的方法

  • 栈的特性: 先进后出, 后进先出 (最先放入栈的內容最后被拿岀来, 最后放入栈的内容最先被拿出来)


栈的插入


push()  // 在栈顶插入元素

栈的删除


pop()  // 在栈顶移除一个元素, 并将栈数 -1

栈的基本操作

InitStack (&S) [构造空栈]

  • 操作结果: 构造一个空栈S


void Init(SqStack s)
{
s.base=( int *)malloc(size*sizeof( int ));
s.top=s.base;
s.stacksize=size;
}

Push (&S, e) [插入元素]

  • 初始条件: 栈S已存在

  • 操作结果: 插入元素e为新的栈顶元素


void Push(SqStack s, int e)
{
if(s.top-s.base>s.stacksize)
{
s.base=( int *)malloc(size*sizeof( int ));
s.top=s.base;
s.stacksize=size;
}
*s.top++=e;
}

Pop (&S, &e) [删除元素]

  • 初始条件: 栈S已存在且非空

  • 操作结果: 删除S的栈顶元素, 并用e返回其值


void Push(SqStack s, int e)
{
if(s.top-s.base>s.stacksize)
{
s.base=( int *)malloc(size*sizeof( int ));
s.top=s.base;
s.stacksize=size;
}
*s.top++=e;
}

  • 初始条件: 栈S已存在且非空

  • 操作结果: 删除S的栈顶元素, 并用e返回其值


void Print(SqStack *s)
{
int * temp;
temp = s -> top;
while ( temp != s -> base)
{
temp--;
printf("%d",*temp);
}
}

栈的递归调用

  • 递归函数: 一个直接调用直接或通过一系列的调用语句间接地调用自己的函数


# include <stdio.h>
int f ( int m )
{
if ( m==1 )
return 1;
else
{
printd("m=%d\n",m);
return f ( m - 1 );
}

int main()
{
int n;
int f ( int m);
printf("请输入一个大于1的数: ");
scanf("%d",&n);
printf("%d\n",f(n));
return 0;
}


}

栈类型的实现

顺序栈

  • 构造一个最大空机为 maxsize 的空顺序栈 S


# define STACK_INIT_SIZE 100

typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;

Status InitStack ( SqStack &S, int maxsize )
{
S.base = new ElemType[maxsize];
// 储存分配失败
if ( !S.base ) exit ( OVERFLOW );
S.top = S.base;
S.stacksize = Maxsize;
return OK;
}

// 栈的插入
Status Push ( SqStack &S, SElemType e )
{
// 若栈不满, 则将 e 插入栈顶
// 栈满
if ( S.top - S.base >= S.stacksize )
return OVERFLOW;
*S.top++ = e;
return OK;
}

// 栈的删除
Status Pop ( SqStack &S, SElemType &e )
{
// 若栈不空, 则删除 S 的栈顶元素
// 用 额返回其值, 并返回OK 否则返回 ERROR
if ( S.top == S.base ) return ERROR;
e = *--S.top;
return OK;
}

链栈

  • 线性表有顺序存储结构和链式存储结构, 栈属于线性表的一种, 也具有顺序存储结构和链式存储结构











作者: 我叫史迪奇
本文来自于: https://sdq3.link/DataStructure-Stack-Heap.html博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议