FilesExpand file tree

 master

/

Stack.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

162 lines (146 loc) · 2.8 KB

 master

/

Stack.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

162 lines (146 loc) · 2.8 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

/**************************************************************************************************************

以下为操作栈的算法，该栈为动态栈。

在该栈中，pTop指向的节点中存放该栈的栈顶数据

pBottom指向的节点的上一个节点存放该栈的栈底数据，pBottom指向的节点中不存放有效数据，

这样做的目的是为了在进行入栈和出栈时方便对栈的操作，而用考虑特殊情况

**************************************************************************************************************/

#include<stdio.h>

#include<stdlib.h>

typedef struct Node

{

int data;

struct Node *pNext;

}NODE,*PNODE;

typedef struct Stack

{

PNODE pTop;

PNODE pBottom;

}STACK,*PSTACK;

PSTACK create_stack();

void push_stack(PSTACK,int);

void traverse_stack(PSTACK);

bool pop_stack(PSTACK,int *);

bool is_empty(PSTACK);

void clear_stack(PSTACK);

int main()

{

int data_pop;

//创建一个空的栈，pS指针指向该栈

PSTACK pS = create_stack();

//向该栈中压入数据，遍历该栈并输出栈中的数据

push_stack(pS,2);

push_stack(pS,6);

push_stack(pS,28);

traverse_stack(pS);

//从该栈中推出数据，遍历该栈并输出栈中的数据

if(pop_stack(pS,&data_pop))

printf("pop succeed,the data poped out is:%d\n",data_pop);

else

printf("pop failed\n");

traverse_stack(pS);

//清空栈，遍历该栈并输出栈中的数据

clear_stack(pS);

printf("data cleared!\n");

traverse_stack(pS);

return 0;

}

/*

创建一个空栈,并返回指向该栈的指针

*/

PSTACK create_stack()

{

PSTACK pS = (PSTACK)malloc(sizeof(STACK));

pS->pTop = (PNODE)malloc(sizeof(NODE));

if(NULL==pS || NULL==pS->pTop)

{

printf("malloc failed");

exit(-1);

}

else

{

pS->pBottom = pS->pTop;

pS->pBottom->pNext = NULL;

}

return pS;

}

/*

判断该栈是否为空

*/

bool is_empty(PSTACK pS)

{

if(pS->pTop == pS->pBottom)

return true;

else

return false;

}

/*

向pS指针指向的栈中压入数据val

*/

void push_stack(PSTACK pS,int val)

{

PNODE pNew = (PNODE)malloc(sizeof(NODE));

if(NULL==pNew)

{

printf("malloc failed");

exit(-1);

}

else

{

pNew->data = val;

pNew->pNext = pS->pTop;

pS->pTop = pNew;

}

return ;

}

/*

从栈中推出数据，并将推出的数据保存在pData指针所指向的位置

*/

bool pop_stack(PSTACK pS,int *pData)

{

if(is_empty(pS))

return false;

else

{

PNODE p = pS->pTop;

*pData = p->data;

pS->pTop = p->pNext;

free(p);

p = NULL;

return true;

}

}

/*

遍历栈，并自栈顶向栈底输出栈中的数据

*/

void traverse_stack(PSTACK pS)

{

PNODE pCurrent = pS->pTop;

printf("Now datas int the stack are:\n");

while(pCurrent != pS->pBottom)

{

printf("%d ",pCurrent->data);

pCurrent = pCurrent->pNext;

}

printf("\n");

return ;

}

/*

清空栈，即将其还原为空栈

*/

void clear_stack(PSTACK pS)

{

if(is_empty(pS))

return ;

else

{

PNODE p = pS->pTop;

PNODE r = NULL;

while(p != pS->pBottom)

{

r = p->pNext;

free(p);

p = r;

}

pS->pTop = pS->pBottom;

}

}