数据结构(四):栈

一、栈的定义

栈是只能在一端进行插入和删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的位置是动态的,由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。

当栈中没有元素时,称为空栈。栈的插入操作通常称为入栈或者进栈,栈的删除操作一般称作出栈或者退栈。

栈的主要特点是 ”后进先出“ ,即后进栈的元素先出栈。每次进栈的元素都放在原来栈顶元素之前,成为新的栈顶元素,每次出栈的元素都是当前栈顶元素。所以栈也被称为后进先出表。

栈的抽象数据类型定义如下:

ADT List
{
    数据对象:
        D={a(i)|1=<i<=n, a(i)是 ElemType类型}
    数据关系:
        R={<a(i), a(i+1)>|a(i),a(i+1)属于 D, i=1,2,3,···,n-1}
    基本运算:
        InitStack(&s): 初始化栈,构建一个空栈 s
        ClearStack(&s): 销毁栈:释放栈 s所占的内存空间
        StackLength(s): 求栈的长度: 返回栈 s中的元素个数
        StackEmpty(s): 判断栈是否为空:若栈 s为空则返回真,否则返回假
        Push(&s, e): 进栈:将元素 e添加到栈顶
        Pop(&s, &e): 出栈:将栈顶元素赋值给 e并从栈顶删除
        GetTop(s, &e): 取栈顶元素:将当前栈顶元素的值赋值给 e
        DispStack(s):显示栈中所有元素的值:按照从栈顶到栈底的顺序显示栈中所有元素的值
}

二、栈的顺序存储结构与基本运算

使用顺序存储结构存储栈时,我们会分配一块连续的内存空间来存放栈中的元素,并用一个变量指向当前的栈顶。采用顺序存储结构的栈称为顺序栈。

定义顺序栈的结合体时,我们假设栈能够存储的最大元素数量为 MaxSize,指向栈顶的变量为 STop(在顺序存储结构中 STop是一个整数,表示当前栈顶元素的下标),存放栈中元素的数组 data。

所以我们可以定义栈的结构体为:

#define MaxSize 100

typedef char ElemType;
typedef struct Stack{
    int STop;
    ElemType data[MaxSize];
}Stack;

这里栈的最大大小我们通过宏来定义,在实现时也可以使用其他的方法定义,比如在栈中再加一个 MaxSize,data改为一个 ElemType[] 类型的指针,在初始化栈时,通过 malloc函数读取 MaxSize来为 data分配内存。

1、栈的初始化

void InitStack(Stack* &s) {
    s = (Stack*)malloc(sizeof(Stack));
    s->STop = -1;
 }//InitStack

在初始化函数里我我们把 s->STop赋值为 -1,以此来标记栈 s是空栈。

也可以把 STop赋值为 0,这与 -1区别不大,只是当初始化为 -1时 STop总是指向栈顶元素,而初始化为 0时 STop总是指向栈顶元素的前一位。

2、销毁栈

void ClearStack(Stack* &s) {
    free(s);
    s = NULL;
}//ClearStack

3、求栈的长度

int StackLength(Stack* s) {
    return s->STop + 1;
}//StackLengt

这里我们返回 STop+1是因为 STop总是指向栈顶元素,而栈顶元素的下标就是数组元素个数减一。

当 STop初始化为 0时我们就可以直接返回 STop。

4、判断栈是否为空

bool StackEmpty(Stack* s) {
    if (s->STop < 0) {
        return true;
    }
    else{
        return false;
    }
}//StackEmpty

5、进栈

void Push(Stack* &s, ElemType e) {
    s->STop++;
    
    if (s->STop > MaxSize || s->STop < 0) {
        throw;
    }
    else{
        s->data[s->STop] = e;
    }
}//Push

6、出栈

void Pop(Stack* &s, ElemType &e) {
    if (!StackEmpty(s)) {
        e = s->data[s->STop];
        s->STop--;
    }
    else {
        throw;
    }
}//Pop

7、取栈顶元素

void GetTop(Stack* s, ElemType &e) {
    if (!StackEmpty(s)) {
        e = s->data[s->STop];
    }
    else {
        throw;
    }
}//GetTop

8、打印栈

void DispStack(Stack* s) {
    if (StackEmpty(s)) {
        printf("stack is empty.\n");
    }
    else {
        int top = s->STop;
        while (top >= 0) {
            printf("index: %d, value: %c\n", top, s->data[top]);
            top--;
        }
    }
}//DispStack

三、栈的链式存储结构与基本运算

栈的链式存储结构叫做链栈,通常用单链表实现。链栈的有点是不用考虑满栈的情况,操作也很方便,我们只要在头节点处操作就行。最靠近头节点的节点是栈顶节点,而链表中与头节点相对的一端则是栈底。

链栈中节点的结构定义如下:

typedef char ElemType;
typedef struct LinkStack {
    ElemType data;
    struct LinkStack* next;
}LinkStack;

1、链栈的初始化

void InitStack(LinkStack* &s) {
    s = (LinkStack*)malloc(sizeof(LinkStack));
    s->next = NULL;
}

2、销毁链栈

void ClearStack(LinkStack* &s) {
    while(s->next != NULL) {
        LinkStack* temp = s->next->next;
        free(s->next);
        s->next = temp;
    }
    free(s);
    s = NULL;
}

3、求链栈的长度

int StackLength(LinkStack* s) {
    int i = 0;
    while (s->next != NULL) {
        i++;
        s->next = s->next->next;
    }
    return i;
}

4、判断链栈是否为空

bool StackEmpty(LinkStack* s) {
    return s->next == NULL;
}

5、进栈

void Push(LinkStack* &s, ElemType e) {
    LinkStack* new_node = (LinkStack*)malloc(sizeof(LinkStack));
    if (new_node == NULL) {
        throw;
    }

    new_node->data = e;
    new_node->next = s->next;
    s->next = new_node;
}

链栈进栈与单链表添加节点很相似,只是链栈进栈时我们只在头节点后面添加节点,而单链表则可以在链表的任意位置添加节点。

6、出栈

void Pop(LinkStack* &s, ElemType &e) {
    if (StackEmpty(s)) {
        throw;
    }

    LinkStack* temp = s->next;
    e = temp->data;
    s->next = temp->next;
    free(temp);
}

7、取栈顶元素

void GetTop(LinkStack* s, ElemType &e) {
    if (StackEmpty(s)) {
        throw;
    }

    e = s->next->data;
}

8、打印栈

void DispLStack(LinkStack* s) {
    LinkStack* temp = (LinkStack*)malloc(sizeof(LinkStack));
    *temp = *s;

    int i = 0;
    while (temp->next != NULL) {
        i++;
        printf("index: %d, value: %c\n", i, temp->next->data);
        temp->next = temp->next->next;
    }
}

这里使用一个 temp作为中间变量是为了避免直接修改 s所指向的内存。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day27 Java容器类详解(九)LinkedList详解

  这次介绍一下List接口的另一个践行者——LinkedList,这是一位集诸多技能于一身的List接口践行者,可谓十八般武艺,样样精通,栈、队列、双端队列、...

9830
来自专栏拭心的安卓进阶之路

Java 常用工具类 Collections 源码分析

文章出处 文章出自:安卓进阶学习指南 作者:shixinzhang 完稿日期:2017.10.25 Collections 和 Arrays 是 JDK...

36170
来自专栏xiaoxi666的专栏

链表回文判断(C++)

11520
来自专栏老马说编程

(48) 剖析ArrayDeque / 计算机程序的思维逻辑

查看历史文章,请点击上方链接关注公众号。 前面我们介绍了队列Queue的两个实现类LinkedList和PriorityQueue,LinkedList还实现了...

22590
来自专栏自学笔记

Data Structure_数组_栈_队列_链表_霍夫曼数组栈队列链表哈夫曼

这就表示一个数组,这个数组有八个元素存放。对于元素的获取,主要就是通过下标获取,所以索引对于数组是很重要的,这个索引可以是有意义的,也可以是没有意义的。比如ar...

8220
来自专栏从流域到海域

《数据结构》 栈代码操作集合

栈的基本操作代码,来自《数据结构-用C语言描述》(第二版)高教社 栈的数据结构相当于受限制(只能从栈顶取元素,先进后出LIFO)的顺序表或单链表,可以...

19360
来自专栏趣学算法

数据结构 第6讲 链栈

进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。顺序栈和链栈图解:

10010
来自专栏LeetCode

简单算法杂例

第一:如果B栈为空,那么将A中的所有元素依次弹出后放入B栈中(负负为正,FILO顺序颠倒,再颠倒依次就为原始的顺序),此时B栈中已经有了元素,弹出的方式见“第二...

13240
来自专栏码生

ios OC swift run-time isa 指针

10230
来自专栏专注研发

JAVA中Sql时间格式与util时间格式转换

  pst.setDate(1, ;//这里的Date是sql中的::得到的是日期

30350

扫码关注云+社区

领取腾讯云代金券