• 欢迎访问BruceOu的博客,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本章吧

《数据结构与算法》第3章 栈(C语言)

数据结构与算法 BruceOu 2个月前 (06-11) 45次浏览 0个评论

24QYG9.md.png

3.1 栈的概述

同顺序表和链表一样,栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构。

24Qt2R.png

栈存储结构与之前所学的线性存储结构有所差异,这缘于栈对数据 “存” 和 “取” 的过程有特殊的要求:

1.栈只能从表的一端存取数据,另一端是封闭的;

2.在栈中,无论是存数据还是取数据,都必须遵循”先进后出”的原则,即最先进栈的元素最后出栈。拿图 1 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据”先进后出”的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。

因此,我们可以给栈下一个定义,即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。

通常,栈的开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指的就是距离栈顶最近的元素,拿下图 来说,栈顶元素为元素 4;同理,栈底元素指的是位于栈最底部的元素,下图中的栈底元素为元素 1。

24QWsP.png

基于栈结构的特点,在实际应用中,通常只会对栈执行以下两种操作:

  • 向栈中添加元素,此过程被称为”进栈”(入栈或压栈);
  • 从栈中提取出指定元素,此过程被称为”出栈”(或弹栈);

栈是一种 “特殊” 的线性存储结构,因此栈的具体实现有以下两种方式:

1.顺序栈:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构;

2.链栈:采用链式存储结构实现栈结构;

两种实现方式的区别,仅限于数据元素在实际物理空间上存放的相对位置,顺序栈底层采用的是数组,链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。

栈的应用

基于栈结构对数据存取采用 “先进后出” 原则的特点,它可以用于实现很多功能。

例如,我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A,然后关闭了页面 A 跳转到页面 B,随后又关闭页面 B 跳转到了页面 C。而此时,我们如果想重新回到页面 A,有两个选择:

  • 重新搜索找到页面 A;
  • 使用浏览器的”回退”功能。浏览器会先回退到页面 B,而后再回退到页面 A。

浏览器 “回退” 功能的实现,底层使用的就是栈存储结构。当你关闭页面 A 时,浏览器会将页面 A 入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是栈中数据依次出栈的效果。

不仅如此,栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号(小括号、中括号和大括号),括号的错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误的功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构。

同时,栈结构还可以实现数值的进制转换功能。例如,编写程序实现从十进制数自动转换成二进制数,就可以使用栈存储结构来实现。

3.2 顺序栈

3.2.1顺序栈概述

顺序栈,即用顺序表实现栈存储结构。通过前面的学习我们知道,使用栈存储结构操作数据元素必须遵守 “先进后出” 的原则,本节就给大家做详细介绍。

如果你仔细观察顺序表(底层实现是数组)和栈结构就会发现,它们存储数据的方式高度相似,只不过栈对数据的存取过程有特殊的限制,而顺序表没有。

例如,我们先使用顺序表存储 {1,2,3,4},存储状态如图所示:

24Q4Z8.png

同样,使用栈存储结构存储 {1,2,3,4},其存储状态如下图所示:

24Q5dS.png

通过前面两图的对比不难看出,使用顺序表模拟栈结构很简单,只需要将数据从 a 数组下标为 0 的位置依次存储即可。

从数组下标为 0 的模拟栈存储数据是常用的方法,从其他数组下标处存储数据也完全可以,这里只是为了方便初学者理解。

了解了顺序表模拟栈存储数据后,接下来看如何模拟栈中元素出栈的操作。由于栈对存储元素出栈的次序有”先进后出”的要求,如果想将图中存储的元素 1 从栈中取出,需先将元素 4、元素 3 和元素 2 依次从栈中取出。

3.2.2顺序栈实现

顺序栈存储结构实现

栈是顺序表的一种,具有顺序表同样的存储结构,由数组定义,配合用数组下表表示的栈顶指针top(相对指针)完成各种操作。

#define MAX 100
typedef int data_t;  //定义栈中数据元素的数据类型
typedef struct
{
    data_t data[MAX];
    int top;  //指向栈顶位置(数组下标)的变量
}seqstack_t;  //顺序栈类型定义

【注】顺序栈也可以通过指针实现。

顺序栈的基本操作

(1) 顺序栈的初始化

顺序栈初始化很简单,只需要将栈顶设置为-1即可。

seqstack_t *CreateEmptyStack()
{
    seqstack_t *stack;
    stack = (seqstack_t *)malloc(sizeof(seqstack_t));
    stack->top = -1;

    return stack;
}

(2) 清空顺序栈

清空顺序栈是将栈顶设置-1。

void ClearStack(seqstack_t *stack)
{
    if(stack != NULL)
        stack->top = -1;
}

(3) 判断顺序栈是否为空

判断顺序栈是否为空是看栈顶是否为-1。

int EmptyStack(seqstack_t *stack)
{
    if(stack == NULL)
        return -1;
    return(stack->top == -1 ? 1 : 0);
}

(4) 判断顺序栈是否为满

判断顺序栈是否为满是看栈顶是否为MAX-1。

int FullStack(seqstack_t *stack)
{
    if(stack == NULL)
        return -1;
    return(stack->top == MAX-1 ? 1 : 0);
}

(5) 顺序栈入栈

对于顺序栈的进栈操作,首先判断栈为满,将新的数据元素存入栈内,然后将记录栈内元素个数的top+1即可。同时要保证底层数组的长度可以容纳新的数据元素。

24laWj.png

代码如下所示:

int PushStack(seqstack_t *stack ,data_t x)
{
    if(FullStack(stack))
        return -1;
    else
    {
        stack->top++;
        stack->data[stack->top] = x;
    }
    return 0;
}

(6) 顺序栈出栈

对于顺序栈的进栈操作,首先判断是否栈为空,让记录栈内元素个数的top-1。

24l7TO.png

int PopStack(seqstack_t *stack,data_t *x)
{
    if(EmptyStack(stack))
        return -1;
    else
    {
        *x = stack->data[stack->top];
        stack->top--;
    }

    return 0;
}

(7) 获取顺序栈栈顶元素

int GetTop(seqstack_t *stack,data_t *x)
{
    if(EmptyStack(stack))
        return -1;
    else
        *x = stack->data[stack->top];

    return 0;
}

(8) 释放顺序栈

void DestroyStack(seqstack_t *stack)
{
    if(stack != NULL)
    {
        free(stack);
    }
}

【完整代码参考3.1 seqstack】

3.3 链栈

3.3.1链栈概述

链栈,即用链表实现栈存储结构。

链栈的实现思路同顺序栈类似,顺序栈是将数顺序表(数组)的一端作为栈底,另一端为栈顶;链栈也如此,通常我们将链表的头部作为栈顶,尾部作为栈底,如图所示:

24lbkD.png

将链表头部作为栈顶的一端,可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶,意味着:

  • 在实现数据”入栈”操作时,需要将数据从链表的头部插入;
  • 在实现数据”出栈”操作时,需要删除链表头部的首元节点;

因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表。

3.3.2链栈实现

链栈存储结构实现

链栈和单链表的存储结构是相同的,只是链栈和单链表的实现不同罢了。

typedef int datatype;

typedef struct _node_
{
    datatype data;
    struct _node_ *next;
} linkstack;

链栈的基本操作

(1) 链栈的初始化

linkstack *CreateEmptyLinkstack()
{
    linkstack *s;

    s = (linkstack *)malloc(sizeof(linkstack));
    if(s == NULL)
    {
        return NULL;
    }
    s->next = NULL;

    return s;
}

(2) 判断链栈是否为空

判断链栈是否为空很简单,只需要判断stack->next是否为NULL即可。

int EmptyLinkstack(linkstack *s)
{
    if(s == NULL)
    {
        return -1;
    }
    return (NULL == s->next);
}

(3) 链栈入栈

链栈入栈将各元素采用头插法依次添加到链表中,例如,将元素 1、2、3、4 依次入栈,每个数据元素的添加过程如图所示:

24lqte.png

int PushLinkstack(linkstack *s, datatype x)
{
    if(s == NULL)
    {
        return -1;
    }
    linkstack *p;

    p = (linkstack *)malloc(sizeof(linkstack));
    if(p == NULL)
    {
        return -1;
    }
    else
    {
        p->data = x;
        p->next = s->next;
        s->next = p;
    }
    return 0;
}

(4) 链栈出栈

根据”先进后出”的原则,假设将元素 1、2、3、4 依次已经入栈,要先将元素 4 出栈,也就是从链表中摘除,然后元素 3 才能出栈,整个操作过程如图所示:

24lLfH.png

datatype PopLinkstack(linkstack *s)
{
    if(s == NULL)
    {
        return -1;
    }
    linkstack *p;
    datatype x;

    p = s->next;
    x = p->data;
    //方法一
    //s->next = p->next;
    //方法二
    s->next = s->next->next;
    free(p);

    return x;
}

(5) 清除链栈

void ClearLinkstack(linkstack *s)
{
    if(s == NULL)
    {
        return ;
    }
    linkstack *p;
    linkstack *temp = s->next;

#if 0
    while(temp != NULL)
    {
        p = temp->next;
        free(temp);
        temp = p;
    }

#else
    while (s->next != NULL)
    {
        p = s->next;
        //方法一
        //s->next = p->next;
        //方法二
        s->next = s->next->next;
        free(p);
    }
#endif

    s->next = NULL;

    return;
}

(6) 获取链栈栈顶元素

datatype GetTopLinkstack(linkstack *s)
{
    if(s == NULL)
    {
        return -1;
    }
    return (s->next->data);
}

(7) 释放链栈

void Destroylinkstack(linkstack *s)
{
    if(s != NULL)
    {
        if(EmptyLinkstack(s) != 1)
        {
            ClearLinkstack(s);
        }
        if(s->next != NULL)
            free(s->next);
        free(s);
    }
}

【完整代码参考3.2 linkstack】



代码获取方法

1.长按下面二维码,关注公众号[嵌入式实验楼]
2.在公众号回复关键词[Data Structures and Algorithms]获取资料
在这里插入图片描述


BrueceOu , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:《数据结构与算法》第3章 栈(C语言)
喜欢 (0)
[支付宝]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址