【数据结构】栈和队列(栈的基本操作和基础知识)

简介: 【数据结构】栈和队列(栈的基本操作和基础知识)

栈的概念和结构

image.png

栈的实现

栈有数组栈和链式栈。数据结构没有规定栈的实现要用数组还是链式,根据自身需要选择即可。

在数组栈中,左边是栈底,右边是栈顶。因为数组尾插尾删方便,也符合栈顶元素先出。

在用单链表实现时,栈顶只能是左边。因为单链表的头插头删方便。

image.png

数组栈的实现

总的声明

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


typedef int STDataType;

typedef struct Stack
{
   
   
    int* a;
    int top;   //标识栈的位置
    int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

//栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

初始化


void STInit(ST* pst)
{
   
   
    assert(pst);

    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;
    //pst->top = -1;
}

上方代码中,pst->top可以初始化为0,也可以为-1。不过两种方法需要区分:

第一种
image.png
top指向栈顶元素,当top初始化为0时,会产生歧义,即当有一个数据或者为空时,top都等于0。

下面是解决方法:
image.png
分析:当它为空时,top==0。当有一个数据时,top==1,即top是指向栈顶元素的下一个位置。

如果我们想用这种方式实现数组栈,尾插时,就直接把x赋给top位置,然后再让top指向下一位置。

第二种:
image.png
分析:我们初始化top为-1,此时为空。当有一个数据时,top==0,刚好指向栈顶元素。尾插时,需要先让top指向下一位置,再插入元素。

两种方法都可以使用,这里我们使用初始化top为0的方法。 注意:使用不同的方法,其他操作的实现会略微不同。

插入


void STPush(ST* pst, STDataType x)
{
   
   
    assert(pst);
    if (pst->top == pst->capacity)
    {
   
   
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
   
   
            perror("realloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
    pst->a[pst->top] = x;
    pst->top++;
}

删除


void STPop(ST* pst)
{
   
   
    assert(pst);
    assert(pst->top > 0);
    pst->top--;
}

取栈顶元素


STDataType STTop(ST* pst)
{
   
   
    assert(pst);
    assert(pst->top > 0);
    return    pst->a[pst->top - 1];
}

销毁



void STDestroy(ST* pst)
{
   
   
    free(pst->a);
    pst->a = NULL;
    pst->capacity = pst->top = 0;

}

判断是否为空


bool STEmpty(ST* pst)
{
   
   
    assert(pst);
    //if (pst->top == 0)
    //{
   
   
    //    return true;
    //}
    //else
    //{
   
   
    //    return    false;
    //}
    return pst->top == 0;
}

返回栈的大小


int STSize(ST* pst)
{
   
   
    assert(pst);
    return pst->top;
}

栈的一对多关系

image.png
如上图,我们的入栈顺序是123456,出栈顺序是346521。可知入栈顺序和出栈顺序是一对多的关系。入栈顺序只有一种,但出栈的顺序是多样的,不过出栈顺序也要符合先出栈顶元素,不是想出啥就出啥 。

不同的栈

image.png
栈有两种,一种是数据结构的栈,一种是内存区域的栈。我们这里的栈是数据结构的栈。而我们所说的栈溢出是指内存区域的栈,在递归中,返回条件出现问题时,容易出现栈溢出。

目录
相关文章
|
存储 算法
数据结构(严蔚敏版)第三章——栈和队列(二)【栈的表示和操作的实现】
3.3、栈的表示和操作的实现 3.3.1、栈的类型定义 3.3.2、顺序栈的表示和实现 1、顺序栈的初始化 2、判断顺序栈是否为空 3、求顺序栈长度 4、清空顺序栈 5、销毁顺序栈 6、顺序栈的入栈 7、顺序栈的出栈 8、取栈顶元素 3.3.3、链栈的表示和实现 1、链栈的初始化 2、判断链栈是否为空 3、链栈的入栈 4、链栈的出栈 5、取栈顶元素
393 0
|
9月前
【数据结构】栈和队列(队列的基本操作和基础知识)
【数据结构】栈和队列(队列的基本操作和基础知识)
67 1
|
测试技术
[数据结构]栈的基本操作
顺序栈 1.1顺序栈的定义 /* 顺序栈基本操作 */ #include #include //定义栈中最大元素的个数.
731 0
了解数据结构的栈和线性表基本操作的对比
栈(stack):是只允许在一端进行插入或者删除操作的线性表
130 0
|
9月前
|
存储 缓存 索引
数据结构——顺序表的概念和基本操作(超全超详细)
数据结构——顺序表的概念和基本操作(超全超详细)
|
存储 算法 C++
数据结构入门:栈
数据结构入门:栈
58 0
数据结构入门 — 栈
栈(Stack)是一种特殊的线性数据结构,它的特点是仅允许在一端进行插入和删除操作。这一端被称为栈顶(Top),另一端称为栈底(Bottom)。栈的操作模式为后进先出(Last In First Out,LIFO),是一种简单的“先进后出”的顺序结构。 栈通常可以用数组或链表实现,常用的操作包括入栈(Push)和出栈(Pop)。入栈操作是将新的元素插入到栈顶,出栈操作是将栈顶的元素删除并返回。
97 0
|
缓存
【数据结构入门】-栈和队列
【数据结构入门】-栈和队列
105 0
|
9月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
154 0
|
缓存
初阶数据结构 栈
初阶数据结构 栈
80 0
初阶数据结构 栈

热门文章

最新文章