Blog of LeanderPeng

Welcome

0%

Link Stack

Posted on Edited on In
Symbols count in article: 2.7k Reading time ≈ 2 mins.

栈（链表实现）

队列概念

栈是一种特殊的线性表，特殊在栈的一端是封闭的，数据的插入与删除只能在栈的另一端进行，也就是栈遵循“后进先出”的原则。也被成为“LIFO”结构，意思是“last input first output”。

闭合的一端被称为栈底（Stack Bottom），允许数据的插入与删除的一端被称为栈顶（Stack Top），不包含任何元素的栈被称为空栈

队列的结构

  • 结构图

入栈（PUSH）

出栈（POP）

  • 代码描述
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
//linkStack.h

#ifndef LINK_STACK_H
#define LINK_STACK_H

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

#define DataType int
 
#define POPERROR  -2147483648         // 出栈错误返回值
#define GETTOPERROR  -2147483648      // 获取栈顶元素错误返回值

typedef struct node                   // 结点结构体
{
    DataType data;
    struct node *next;
}StackNode;

typedef struct stack                  // 栈结构体
{
    int size;
    StackNode *top;
}LinkStack;

LinkStack *Inti_LinkStack(void); // 初始化链栈
int Stack_IsEmpty(LinkStack *stack); // 判空

int Push(LinkStack *stack, DataType data); // 入栈
int Stack_IsEmpty(LinkStack *stack); //判空
DataType Pop(LinkStack *stack); // 出栈
DataType Get_top(LinkStack *stack); // 获取栈顶元素
void Destory_LinkStack(LinkStack *stack); // 摧毁栈
void Display_Linkstack(LinkStack *stack); // 展示栈
 

#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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// linkSatck.c

#include"linkStack.h"

// 创建新结点
static StackNode *NewNode(DataType data)
{
    StackNode *node = (StackNode*)malloc(sizeof(StackNode));
    if(node != NULL)
    {
        node->data = data;
        node->next = NULL;
    }
    return node;
}

// 初始化栈
LinkStack *Inti_LinkStack(void)
{
    LinkStack *stack = (LinkStack*)malloc(sizeof(LinkStack));
    if (stack != NULL)
    {
        stack->top = NULL;
        stack->size = 0;
    }

    return stack;
}

//判空
int Stack_IsEmpty(LinkStack *stack)
{
    return stack->size == 0;
}

// 头插法插入节点
static int HeadInsert_node(LinkStack *stack ,StackNode *node)
{
    if(stack == NULL || node == NULL)
        return 0;
    
    node->next = stack->top;
    stack->top = node;
    stack->size++;

    return 1;
}

//入栈
int Push(LinkStack *stack, DataType data)
{
    return HeadInsert_node(stack,NewNode(data));
}

// 出栈
DataType Pop(LinkStack *stack)
{
    if (stack == NULL || Stack_IsEmpty(stack))
        return POPERROR;
    
    StackNode *p = stack->top;
    DataType top_data = p->data;
    stack->top = stack->top->next;
    free(p);

    return top_data;
}

// 获取栈顶元素
DataType Get_top(LinkStack *stack)
{
    if(stack == NULL || Stack_IsEmpty(stack))
        return GETTOPERROR;

    return stack->top->data;
}

// 摧毁栈
void Destory_LinkStack(LinkStack *stack)
{
    StackNode *p = stack->top;
    StackNode *q;
    while(p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    free(stack);
}

// 展示栈
void Display_Linkstack(LinkStack *stack)
{
    if(stack == NULL || Stack_IsEmpty(stack))
    {
        printf("stack can not diaplay\n");
        return;
    }
        
    printf("(stack top)\n");
    StackNode *p = stack->top;
    while (p != NULL)
    {
        printf("   %d\n",p->data);
        p = p->next; 
    }
    printf("(stack bottom)\n");
    
}