基础数据结构_栈

发表于2021-10-01更新于2025-11-04阅读次数

顺序栈

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef MY_SEQSTACK_H
#define MY_SEQSTACK_H

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;

#define STACK_INIT_SIZE 100
#define STACKINC 1.5
typedef int SElemType;
typedef struct
{
    SElemType *base;//栈底指针
    SElemType *top;//栈顶指针
    int stacksize;//栈的容量
}SeqStack;

Status InitStack(SeqStack *ps);
void DestroyStack(SeqStack *ps);
void ClearStack(SeqStack *ps);
int StackLength(const SeqStack *ps);
bool StackEmpty(const SeqStack *ps);
bool StackFull(const SeqStack *ps);
Status Push(SeqStack *ps, SElemType val);
Status GetTop(SeqStack *ps, SElemType *pval);
Status Pop(SeqStack *ps, SElemType *pval);


#endif

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//My_SeqStack.cpp
#include<stdlib.h>//malloc free
#include<assert.h>

#include"My_SeqStack.h"
Status InitStack(SeqStack *ps)
{
    assert(ps!=NULL);
    ps->base = (SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);
    if(NULL==ps->base)
    {
        return OVERFLOW;
    }
    ps->top = ps->base;
    ps->stacksize = STACK_INIT_SIZE;
    return OK;
}
void DestroyStack(SeqStack *ps)
{
	assert(ps!=NULL);
    free(ps->base);
    ps->base = NULL;
    ps->top = NULL;
    ps->stacksize = 0;
}
void ClearStack(SeqStack *ps)
{
    assert(ps!=NULL);
    ps->top = ps->base;
}
int StackLength(const SeqStack *ps)
{
    assert(ps!=NULL);
    return ps->top - ps->base;
}
bool StackEmpty(const SeqStack *ps)
{
    assert(ps!=NULL);
    return ps->top == ps->base;
    //return StackLength(ps)==0;
}
bool StackFull(const SeqStack *ps)
{
    assert(ps!=NULL);
    return StackLength(ps)==ps->stacksize;
}
bool IncSize(SeqStack *ps)
{
    assert(ps!=NULL);
    int newsize = ps->stacksize * STACKINC;
    SElemType *newdata = (SElemType*)realloc(ps->base,sizeof(SElemType)*newsize);
    
    if(NULL==newdata)return false;
    ps->base = newdata;
    
    ps->top = ps->base + ps->stacksize;
    
    ps->stacksize = newsize;
    return true;
}
Status Push(SeqStack *ps, SElemType val)
{
    assert(ps!=NULL);
    if(StackFull(ps) && !IncSize(ps))
    {
        return OVERFLOW;
    }
    *(ps->top) = val;
    ps->top += 1;
    return OK;
}
Status GetTop(const SeqStack *ps, SElemType *pval)
{
    assert(ps!=NULL);
    if(StackEmpty(ps))
    {
        return ERROR;
    }
    if(NULL == pval)return NULLPTR;
    *pval = *(ps->top-1);
    return OK;
}
Status Pop(SeqStack *ps, SElemType *pval)
{
    assert(ps !=NULL);
    if(StackEmpty(ps))
    {
        return ERROR;
    }
    if(NULL==pval)return NULLPTR;
    
    ps->top -= 1;
    *pval = *(ps->top);
    return OK;
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//TestStack.cpp
#include<stdio.h>
#include"My_SeqStack.h"
int main()
{
    SeqStack mys;
    InitStack(&mys);
    for (int i = 0;i < 10;++i)
    {
        Push(&mys, i);
    }
    int val;
    while (!StackEmpty(&mys))
    {
        Pop(&mys, &val);
        printf("%d ", val);
    }
    DestroyStack(&mys);
}

链栈

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//LinkStack.h
#ifndef LINKSTACK_H
#define LINKSTACK_H

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULLPTR -3

typedef int Status;

typedef int SElemType;
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*PStackNode;
typedef struct
{
    StackNode *top;
    int cursize;
}LinkStack;

Status InitStack(LinkStack *ps);
void DestroyStack(LinkStack *ps);
void ClearStack(LinkStack *ps);
int StackLength(const LinkStack *ps);
bool StackEmpty(const LinkStack *ps);
bool StackFull(const LinkStack *ps);
Status Push(LinkStack *ps, SElemType val);
Status GetTop(LinkStack *ps, SElemType *pval);
Status Pop(LinkStack *ps, SElemType *pval);
#endif

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//LinkStack.cpp
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include"LinkStack.h"
StackNode* Buynode()
{
    StackNode *newnode = (StackNode*)malloc(sizeof(StackNode));
    if(NULL!=newnode)
    {
        memset(newnode,0,sizeof(StackNode));
    }
    return newnode;
}
Status InitStack(LinkStack *ps)
{
    assert(ps!=NULL);
    ps->top = Buynode();//头结点
    if(NULL == ps->top)return OVERFLOW;
    
    ps->cursize = 0;
    return OK;
}
void DestroyStack(LinkStack *ps)
{
    assert(ps!=NULL);
    ClearStack(ps);
    free(ps->top);
    ps->top = NULL;
    return OK;
}
void ClearStack(LinkStack *ps)
{
    assert(ps!=NULL);
    while(ps->cursize!=0)
    {
        DelFront(ps);
    }
    return OK;
}
int StackLength(const LinkStack *ps)
{
    assert(ps!=NULL);
    return ps->cursize;
}
bool StackEmpty(const LinkStack *ps)
{
    assert(ps!=NULL);
    return ps->cursize == 0;
}
Status Push(LinkStack *ps, SElemType val)
{
    assert(ps!=NULL);
    StackNode *newnode = Buynode();
    if(NULL==newnode)return OVERFLOW;
    
    newnode->next = ps->top->next;
    ps->top->next = newnode;
    
    newnode->data = val;
    
    ps->cursize +=1;
    return OK;
}
Status GetTop(LinkStack *ps, SElemType *pval)
{
    assert(ps!=NULL);
    if(pval==NULL)return NULLPTR;
    if(ps->cursize<=0)return false;
    *pval = ps->top->next->data;
    return OK;
}
Status Pop(LinkStack *ps, SElemType *pval)
{
    assert(ps!=NULL);
    if(pval==NULL)return NULLPTR;
    if(ps->cursize<=0)return ERROR;
    GetTop(ps,pval);
    DelNext(ps);
    return OK;
}
bool DelFront(LinkStack *ps)
{
    assert(ps!=NULL);
    if(ps->cursize<=0)return false;
    StackNode *p = ps->top->next;
    ps->top->next = p->next;
    free(p);
    ps->cursize-=1;
    return true;
}

测试

1

Cpp_函数调用过程

发表于2021-09-30更新于2025-11-04阅读次数

函数调用过程

  1. 参数入栈
  2. 函数栈帧开辟
  3. 返回值返回
  4. 函数栈退出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//4字节入栈
#include<stdio.h>
void fun(int a, int b)
{
    int c;
    c = a + b;
    return c;
}
int main()
{
    int a = 10;
    int b = 20;
    fun(a,b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//8字节入栈
struct Node
{
    int _1;
    int _2;
};
int fun(struct Node a, struct Node b)
{
    int c = 30;
    return c;
}
int main()
{
    struct Node a = {10, 20};
    struct Node b = {30, 40};
    fun(a, b);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//12字节入栈
struct Node
{
    int _1;
    int _2;
    int _3;
};
int fun(struct Node a, struct Node b)
{
    int c = 30;
    return c;
}
int main()
{
    struct Node a = {10, 20, 30};
    struct Node b = {40, 50, 60};
    fun(a, b);
    return 0;
}

image-20211001184239521

寄存器

可以理解为CPU中的变量

如何去标志一个栈？——栈底和栈顶指针。

esp：栈顶寄存器。

ebp：栈底寄存器。

函数调用过程

  1. 参数入栈（C语言）

    1. 4字节参数（dword）入栈

      1. 顺序：从右向左
      2. 方式：使用寄存器push带入

    2. 8字节参数入栈

      1. 顺序：从右向左
      2. 方式：使用寄存器分两次push带入

    3. （>8字节）12字节参数入栈

      image-20211001184251000

      1. 顺序：从右向左
      2. 方式：变了，栈顶先上移，即开辟足够的空间，之后利用寄存器将数据分批次复制进去。

    4. C++中，只要是自定义类型，无论多大字节，都采用先esp上移开辟空间，之后分次赋值的方式（即方式3），即>8字节的情况。

  2. 函数栈帧开辟
    其中，1、2步是为了保存现场。3、4步是开辟新的栈帧。

    1. 函数入参的动作完成后，汇编代码执行call(_fun)语句，esp向上移4位，将调用方函数原来的下一行指令地址存入栈。因为main中调用完成外部函数后，还要回到以前的位置。
      image-20211018205543731
      image-20211018205624299
    2. 将调用方函数的栈底寄存器（ebp）入栈
      image-20211018205322518
    3. 让ebp=esp（让ebp上移到esp的位置）
    4. 让esp=esp-0**h（上移若干空间，开辟此函数的空间）
    5. 将某些寄存器（线程保护）入栈
    6. 将新开辟的栈帧空间中全部赋为0xcccccccc

  3. 函数返回值

    1. 4字节返回值：将返回值先存到eax再赋给接收变量
      image-20211018210146635
      image-20211018210420665

    2. 8字节返回值：将返回值分开放到两个寄存器，再赋给接收变量
      image-20211018210458734

      image-20211018210558730
      image-20211018210607525
      image-20211018210900593

    3. （>8字节）12字节返回值：

      1. 在函数参数入栈之后，入栈一个调用方（如main）栈帧上的地址（靠近栈顶位置）
      2. 在返回值返回的时候，将返回数据分次写入到之前入栈的调用方地址上。
      3. 返回之后，将从该地址（调用方（如main）栈帧上的地址）将数据分次取出（一次4字节）到接收变量中。

      image-20211001213921252

    4. C++中，自定义类型都按照入栈一个调用方地址的方式

  4. 函数栈退出

    1. 进行当前函数栈帧的校验
    2. 将线程保护的寄存器出栈
    3. 让esp=ebp（回缩栈帧）
    4. pop操作（即将pop的位置是esp指向的位置）。
      pop ebp，意为：ebp=pop，esp指向的是原来main的ebp地址，赋给ebp，同时esp下移4字节。则ebp回指到原来的位置。形成现场恢复。
      image-20211018233157527
    5. 将下一行指令的地址还原（ret），实际上，也是一个pop，返回保留的地址值，esp下移4字节。
    6. esp再次下移若干，清除参数和之前入栈的调用方地址。下移之后，则esp和ebp回到了main函数调用外部函数之前的原始位置。函数调用结束。
      image-20211018233852672

说明

当前演示的函数调用规则是依赖于C语言默认的调用约定__cdecl，其他的还有__stdcall/__fastcall。三种差异并不大，只是负责的事情不同，清除参数是调用方执行的，stdcall是被调用方执行的。

1
2
3
4
5
struct Node __cdecl fun(int a, int b)
{
    struct Node c = {10, 20, 30};
    return c;
}