栈

Mark Walen大约 7 分钟数据结构

栈

顺序栈

定义

栈 仅限定在表尾进行插入或删除操作的线性表，是一种后进先出的数据结构

栈
栈

存储结构

我们通过移动栈顶指针(top)进行相关的数据操作，用线性结构(如数组、链表等)存储栈的元素

顺序栈的表示：

#define MAXSIZE 100			//顺序栈存储空间的初始分配量

typedef int ElemType;
typedef struct
{
    ElemType *base;			//存储栈元素
    int top;				//栈顶指针
}

严蔚敏书中的定义：

#define MAXSIZE 100				//顺序栈存储空间的初始分配量

typedef int SElemType;
typedef struct
{
    ElemType *base;				//存储栈元素
    ElemType *top;				//栈顶指针
    int stacksize;				//栈可用的最大容量
}

说明1

  1. 栈底指针base始终指向栈底的位置，若base的值为NULL，表明栈结构不存在
  2. top为栈顶指针，其初值指向栈底，即top = base
    1. 向栈顶插入新的元素时，指针top增1（前提：栈未满）
    2. 删除栈顶元素时，指针top减1（前提：栈不为空）

基本操作

⚠️ 栈只能在栈顶进行一系列操作。

入栈push_back(插入操作)、出栈pop_back(删除操作)、栈空的判断(isEmpty)、取栈顶元素(getTop)

初始化

定义 为顺序栈动态分配一个预定义大小的数组空间。

动画

InitStack

实现 点击 ➡️，查看。

入栈

定义 入栈操作是指在栈顶插入一个新的元素

动画

insert-stack
insert-stack

实现 点击 ➡️，查看。

出栈

定义 将栈顶元素删除

动画

pop-back
pop-back

实现 点击 ➡️，查看。

用数组模拟栈

动态数组模拟栈

动态数组：动态数组的内存空间是从堆动态分配的。是通过执行代码(关键字：malloc, calloc, realloc)而为其分配存储空间。详情open in new window

#define MAXSIZE 100

typedef int ElemType;
int top;	//栈顶指针
ElemType * InitStack();							//初始化栈
void PushBack(ElemType *stack, ElemType data);	//入栈
ElemType PopBack(ElemType *stack);				//出栈
ElemType GetTop(ElemType *stack);				//取栈顶元素
int isEmpty();									//判断栈为空

ElemType* InitStack()
{
	ElemType *stack = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    top = 0;
    return stack;
}

void PushBack(ElemType *stack, ElemType data)
{
    if (top == MAXSIZE) return;		//栈满则不能插入
    stack[top++] = data;
}

ElemType PopBack(ElemType *stack)
{
    if (top == 0) return -1;		//栈为空
    return stack[--top];
}

ElemType GetTop(ElemType *stack)
{
    return stack[top-1];
}

int isEmpty()
{
    //初始化栈
    return top == 0;
}

int main()
{
    //初始化栈1;
    ElemType *stack = InitStack();
    //初始化栈2;
    //ElemType *stack = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    //top = 0;
    free(stack);	//动态分配的空间记得释放。
    return 0;
}

小结

  1. 用数组实现栈比较方便，容易实现。
  2. 可以使用静态数组模拟栈(实现见附录)
    1. 定义初始化一个静态数组，并定义一个下标(top = 0)模拟栈顶指针;
    2. 向栈中插入元素top++，删除元素--top；
    3. 栈为空即top=0 栈满top值等于初始化时数组的长度。
  3. 用数组模拟栈，进行删除操作时，其实需要删除的元素(设下标为del )并未删除，当我们去遍历整个数组（即栈区: [0, top] + 非栈区：[top+1, stackSize]）时依然可以看见stack[del]. 当我们再次插入元素(top = del)时，下标del处的值会被覆盖重写。

用结构体实现

本文用上述存储结构中第一种定义的结构体实现。

Tips 当然也可以根据自己的需求定义相应栈的结构体。

相关头文件

stack.h

#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#define MAXSTACKSIZE 100
typedef int ElemType;

typedef struct
{
    ElemType *base;				//用于存储数据
    int top;					//栈顶指针，栈尾指针默认为下标0
}SeqStack;

void InitStack(SeqStack *stack);                 //初始化栈
void Destroy(SeqStack *stack);                   //销毁栈
void ClearStack(SeqStack *stack);                //清空栈
int Empty(SeqStack stack);                      //判断栈是否为空
int length(SeqStack stack);                     //获取栈元素的个数
ElemType GetTop(SeqStack stack);                //获取栈顶元素
void PushBack(SeqStack *stack, ElemType data);    //栈顶插入元素
ElemType PopBack(SeqStack *stack);                //删除栈顶元素，并返回
void Traverse(SeqStack stack);                   //遍历栈


#endif // STACK_H_INCLUDED

初始化栈

void InitStack(SeqStack *stack)
{
    stack->base = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);		//为栈申请空间
    if(!stack->base) return;	//分配失败，终止。当然我们也可以修改函数的返回类型，了解分配情况。
    stack->top = 0;
}

//返回SeqStack *类型
SeqStack *InitStack()
{
    SeqStack *stack;
    stack->base = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);		//为栈申请空间
    if(!stack->base) return;	//分配失败，终止。当然我们也可以修改函数的返回类型，了解分配情况。
    stack->top = 0;
    return stack;
}

说明1

对于严蔚敏书中的实现：

  1. 由于c语言中不能使用引用类型(&)作为函数形式参数使用，所以改用指针。但在调用函数传递实参时可以使用（C语言中是取地址符），因为传入的是变量的地址。

    以初始化栈函数为例：SeqStack stack; InitStack(&stack);

  2. 栈顶指针：*top | 栈尾指针：*base。

    top初始化为base：stack->top = stack->base表示栈为空。

    ：

入栈

void PushBack(SeqStack *stack, ElemType data)
{
	//判断栈是否已满
    if(stack->top < MAXSTACKSIZE)
    {
        stack->base[stack->top++] = data;
    }
    else
    {
        printf("stack overflow!!!\n");
    }
}

说明2

对于严蔚敏书中的实现：

  1. 函数定义Status Push(SqStack *stack, SElemType e);

  2. 元素入栈:

    1. *(stack->top) = e;stack->top++;

      ：

    2. 不能这样赋值：stack->top = &e;。

      ：这样会把e的地址值赋给stack->top。stack->top与stack->base指向的不是同一个数组，即stack->top - stack->base不能用来判断栈空或栈满。

出栈

ElemType PopBack(SeqStack *stack)
{
	//判断栈是否为空
    if(!Empty(*stack))	//? stack->top = 0
    {
        //可以简化为 return stack->base[--stack->top];
        ElemType data = stack->base[--stack->top];
        return data;
    }
    else
    {
        printf("stack is empty!!!\n");
    }
    return -1;
}

说明3

对于严蔚敏书中的实现：

  1. 函数定义 ①Status Pop(SqStack *stack, ElemType *e);或②ElemType Pop(SqStack *stack)

  2. 函数出栈

    1. ①：e = --stack->top;

      ：将--s->top(栈顶)的地址值赋给e。

    2. ②：return *(--stack->top);

取栈顶元素

ElemType GetTop(SeqStack *stack)
{
    if (stack->top != 0) return *(stack->top - 1);
    return -1;	//栈为空，返回-1;
}

写在最后 栈的基本操作已实现，对于stack.h中未实现的函数，可以自己尝试去实现，感谢你的阅读。

附录

静态数组模拟栈

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

int main()
{
    int stack[stackSize];	//stackSize：栈的长度，请自行定义并初始化。
    int top = 0;
    
    //k in [1, stackSize]
    for (int i = 0; i < k; i++)
    {
        stack[top++] = i*i + 3;		//插入元素
    }
    printf("删除的元素：%d\n", stack[--top]);
    printf("栈顶元素：%d\n", stack[top-1]);
	return 0;
}

思考 当删除元素时，一定是--top吗？

回答：其实--top 与 top--两者皆可。top的含义：栈顶指针以及栈中元素的个数。数组的下标是从0开始的，所以栈顶元素的值：stack[top-1]。我们知道删除元素是删除栈顶元素（设下标为del = top-1），当我们需要使用这个元素时（如作为返回值、输出或其它用途）推荐使用--top(top = del)，当然使用 top--也可以(① top--;stack[top]; 或 ②stack[top-1]; top--；)

练习

  1. 有效的括号open in new window

  2. 逆波兰表达式求值open in new window

  3. 验证栈序列open in new window

默认页脚
Copyright © 2024 Mark Walen