12-栈（基于链表的链式栈）_链表栈

1.基本概念

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

链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底。

链式栈是通过单链表来实现的。每次入栈一个元素，向链表中添加一个节点，出栈一个元素，释放一个节点。因为栈具有“后进先出”的特点，如果每次在链表的尾部进行插入和删除，就要遍历整个链表来找到尾节点。而在头部进行插入和删除时，只需根据头指针即可找到链表的首元素结点。而无需遍历链表。所以链式栈的出，入栈通过对链表进行头删和头插来实现。

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

链表的头部作为栈顶，意味着：

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

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

2. 代码实现

2.1 链栈元素入栈

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

2.2 链栈元素出栈

例如，上图 e) 所示的链栈中，若要将元素 3 出栈，根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图 所示：

//linkstack.h 文件

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__
#include <stdbool.h>

typedef int LinkStackType;
//定义链栈的节点结构
typedef struct LinkStackNode
{
    LinkStackType data;
    struct LinkStackNode* next;
}LinkStackNode;


LinkStackNode* LinkStackPush(LinkStackNode* pstack,LinkStackType value);
LinkStackNode* LinkStackPop(LinkStackNode* pstack);
bool LinkStackTop(LinkStackNode* pstack,LinkStackType* value);
bool LinkStackDetory(LinkStackNode* pstack);

#endif // !__LINKSTACK_H__
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//LinkStack.c 功能函数文件

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

/**
 * @brief Create a Node object
 * 
 * @param value 链表结点元素值
 * @return ** LinkStackNode* 
 */
static LinkStackNode* CreateNode(LinkStackType value)
{
    LinkStackNode* new_node = (LinkStackNode*)malloc(sizeof(LinkStackNode));
    new_node->data = value; 
    new_node->next = NULL;
    return new_node; 
}   
/**
 * @brief 头插入栈
 * 
 * @param pstack 
 * @param value 
 * @return LinkStackNode* 
 */
LinkStackNode* LinkStackPush(LinkStackNode* pstack,LinkStackType value)
{  
    //创建节点
    LinkStackNode* new_node = CreateNode(value);
   //将新节点的next指向原来的首原节点来做为新的首原节点
    new_node->next = pstack;
    //使头指针指向新的首原节点
    pstack = new_node;
    return pstack;
}
/**
 * @brief 销毁节点
 * 
 * @param node 
 */
static void DestoryNode(LinkStackNode* node)
{
    free(node);
}   
/**
 * @brief 头删出栈
 * 
 * @param pstack 
 * @return LinkStackNode* 
 */
LinkStackNode* LinkStackPop(LinkStackNode* pstack)
{
    if(pstack == NULL)
    {
        //空链栈
        return pstack;
    }   
    //保存要删除的首原节点
    LinkStackNode* to_delete = pstack;
    //使头指针指向第二个节点 
    pstack = pstack->next;
    //释放要删除的节点
    DestoryNode(to_delete);
    return pstack;
}
/**
 * @brief 取栈顶元素
 * 
 * @param stack 
 * @param value 
 * @return true 
 * @return false 
 */
bool LinkStackTop(LinkStackNode* pstack,LinkStackType* value)
{
    if(pstack == NULL)
    {
        //空链表
        return false;
    }
    *value = pstack->data;
    return true;
}
/**
 * @brief 销毁链式栈
 * 
 * @param stack 
 * @return true 
 * @return false 
 */
bool LinkStackDetory(LinkStackNode* pstack)
{
    if(pstack == NULL)
    {   
        //非法输入
        return false;
    }   
    //遍历链表各节点对其进行释放
    LinkStackNode* to_delete = pstack;
    while(to_delete != NULL)
    {   
        LinkStackNode* next_node = to_delete->next;
        free(to_delete);
        to_delete = next_node;
    }   
    //将头指针置空
    pstack = NULL;
    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

//测试文件 
void displayLinkStack(LinkStackNode * pstack)
{
    LinkStackNode* temp = pstack;
    
    printf("LinkStack: ");
    while (temp->next) 
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("%d ",temp->data);
    printf("\n");
}

void test(void)
{
    LinkStackType topValue = 0;
    bool ret = false;
    LinkStackNode * stack = NULL;

    stack = LinkStackPush(stack, 1); //1
    stack = LinkStackPush(stack, 2); // 1 2
    stack = LinkStackPush(stack, 3); // 1 2 3   
    stack = LinkStackPush(stack, 4); // 1 2 3 4
    stack = LinkStackPush(stack, 5); // 1 2 3 4 5

    displayLinkStack(stack);
    
    ret = LinkStackTop(stack,&topValue);
    if(ret == true)
    {
        printf("topValue = %d \r\n",topValue);
    }
    
    stack = LinkStackPop(stack); // 1 2 3 4
    stack = LinkStackPop(stack); // 1 2 3
    stack = LinkStackPop(stack); // 1 2
    stack = LinkStackPop(stack); // 1
    
    displayLinkStack(stack);

    ret = LinkStackTop(stack,&topValue);
    if(ret == true)
    {
        printf("topValue = %d \r\n",topValue);
    }
    else
    {
        printf("empty linkStack!\r\n");
    }

    stack =LinkStackPop(stack);  // null
    ret = LinkStackTop(stack,&topValue);
    if(ret == true)
    {
        printf("topValue = %d \r\n",topValue);
    }
    else
    {
        printf("empty linkStack!\r\n");
    }
}

 /**
 * @brief 测试函数
 * 
 * @return int 
 */
int main(void)
{
	test();
	system("pause");
	return  0;
}
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

3.实验结果