数据结构与算法---栈_栈为什么只表示逻辑结构

栈

基本概念

栈是一种逻辑结构，是特殊的线性表。特殊在：

• 只能在固定的一端操作

只要满足上述条件，那么这种特殊的线性表就会呈现一种“后进先出”的逻辑，这种逻辑就被称为栈。

由于约定了只能在线性表固定的一端进行操作，于是给栈这种特殊的线性表的插入删除，起个特殊的名称：

• 栈顶(top of stack)：可以进行插入删除的一端
• 栈底：栈顶的对立端
• 入栈：将节点插入栈顶之上，也称为压栈，函数名通常为push()
• 出栈：将节点从栈顶剔除，也称为弹栈，函数名通常为pop()
• 取栈顶：取得栈顶元素，但不出栈，函数名通常为top()

由于这种固定一端操作的简单约定，栈获得了“后进先出”的基本特性，如下图所示，最后一个放入的元素，最先被拿出来：

存储形式

栈只是一种数据逻辑，如何将数据存储于内存则是另一回事。一般而言，可以采用顺序存储形成顺序栈，或采用链式存储形成链式栈。

• 顺序栈

顺序存储意味着开辟一块连续的内存来存储数据节点，一般而言，管理栈数据除了需要一块连续的内存之外，还需要记录栈的总容量、当前栈的元素个数、当前栈顶元素位置，如果有多线程还需要配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体之中：

struct seqStack
{
    datatype *stack; // 顺序栈入口
    int size;       // 顺序栈总容量
    int top;        // 顺序栈栈顶元素下标
};
1
2
3
4
5
6

顺序栈的构造:

①栈构造管理结构体

②栈的节点的类型设计

普通类型(char int short long float …) 结构体类型

③初始化空栈

主要是初始化栈管理结构体 + 事先申请一大段size字节的连续空间作为栈元素存放空间

• 链式栈

链式栈的组织形式与链表无异，只不过插入删除被约束在固定的一端。为了便于操作，通常也会创建所谓管理结构体，用来存储栈顶指针、栈元素个数等信息：

// 链式栈节点
typedef struct node
{
    datatype data;
    struct node *next;
}node;

// 链式栈管理结构体
struct linkStack
{
    node *top; // 链式栈栈顶指针
    int  size; // 链式栈当前元素个数
};
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 基本操作

不管是顺序栈，链式栈，栈的操作逻辑都是一样的，但由于存储形式不同，代码的实现是不同的。下面分别将顺序栈和链式栈的基本核心操作罗列出来：

顺序栈通用模板

#ifndef DATATYPE 
#define DATATYPE int
#endif

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

typedef DATATYPE datatype;

typedef struct
{
    datatype *data;
    int size;
    int top;
}Seqstack;

/**
 * @description: 初始化栈
 * @param {int} size栈的容量大小
 * @return {*}
 */
static Seqstack *initStack(int size)
{
    Seqstack *seq = (Seqstack*)malloc(sizeof(Seqstack));
    if(NULL == seq)
        return NULL;
    
    seq->data = (datatype*)malloc(sizeof(datatype)*size);
    if(seq->data == NULL)
    {
        free(seq);
        return NULL;
    }
    seq->size = size;
    seq->top = -1;

    return seq;
}

/**
 * @description: 判断栈是否已满
 * @param {Seqstack*} 
 * @return {*}
 */
static bool isFull(Seqstack *seq)
{
    return seq->top == seq->size-1;
}

/**
 * @description: 判断栈是否为空
 * @param {Seqstack} 
 * @return {*}
 */
static bool isEmpty(Seqstack *seq)
{
    return seq->top == -1;
}

/**
 * @description: 入栈
 * @param {Seqstack} *seq 
 * @param {datatype} 
 * @return {*}
 */
static bool push(Seqstack *seq,datatype data)
{
    if(isFull(seq))
        return false;
    
    seq->data[++(seq->top)] = data;
    return true;
}

/**
 * @description: 取栈顶元素
 * @param {Seqstack} *seq
 * @param {datatype} *pm
 * @return {*}
 */
static bool top(Seqstack *seq,datatype *pm)
{
    if(isEmpty(seq))
        return false;
    
    *pm = (seq->data)[seq->top];

    return true;
}

/**
 * @description: 出栈
 * @param {Seqstack} *seq
 * @param {datatype} *pm
 * @return {*}
 */
static bool pop(Seqstack *seq,datatype *pm)
{
    if(top(seq,pm) == false)
        return false;

    (seq->top)--;
    return true;
}

/**
 * @description: 遍历栈
 * @param {Seqstack} *seq
 * @param {datatype} data
 * @return {*}
 */
static bool stack_brow(Seqstack *seq,void (* func)(datatype data))
{
    if(isEmpty(seq))
        return false;
    
    int i = seq->top;
    for(;i >= 0;i--)
        func((seq->data)[i]);

    printf("\n");
    
    return true;
}
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

链式栈通用模板：

#ifndef LINKSTACK
#define LINKSTACK  int
#endif

typedef LINKSTACK stackdata;

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


//链式栈结点
typedef struct node
{
    stackdata data;
    struct node *next;
}Node;

//链式栈管理结构体
typedef struct linkstack
{
    Node* top;
    int size;
}LinkStack;

/**
 * @description: 初始化栈
 * @param {*}
 * @return {*}
 */
static LinkStack *initStack(void)
{
    LinkStack *s = (LinkStack*)malloc(sizeof(LinkStack));

    if(s == NULL)
        return NULL;
    s->top = NULL;
    s->size = 0;

    return s;
}

/**
 * @description: 判断是否为空栈
 * @param {LinkStack} *s
 * @return {*}
 */
static bool isEmpty(LinkStack *s)
{
    return s->size == 0;
}

/**
 * @description:入栈
 * @param {LinkStack} *s
 * @param {stackdata} data
 * @return {*}
 */
static bool push(LinkStack *s,stackdata data)
{
    Node *NewNode = (Node*)malloc(sizeof(Node));

    if(NewNode == NULL)
        return false;
    
    NewNode->data = data;
    NewNode->next = s->top;
    s->top = NewNode;

    s->size++;
    return true;
}

/**
 * @description:取栈顶元素
 * @param {LinkStack} *s
 * @param {stackdata} *pm
 * @return {*}
 */
static bool top(LinkStack *s,stackdata *pm)
{
    if(isEmpty(s))
        return false;
    
    *pm = s->top->data;
    return true;
}

/**
 * @description: 出栈
 * @param {LinkStack} *s
 * @param {stackdata} *pm
 * @return {*}
 */
static bool pop(LinkStack *s,stackdata *pm)
{
    if(isEmpty(s))
        return false;
    
    top(s,pm);
    Node* p = s->top;
    s->top = p->next;

    free(p);
    s->size--;

    return true;  
}

/**
 * @description: 遍历栈
 * @param {LinkStack} *s
 * @param {stackdata} data
 * @return {*}
 */
static bool stack_brow(LinkStack *s,void (* func)(stackdata data))
{
    if(isEmpty(s))
        return false;
    
    Node *p = s->top;
    while(p != NULL)
    {
        func(p->data);
        p = p->next;
    }

    printf("\n");
    return true;
}
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129