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

/* stack.h */

#ifndef _STACK_H_

#define _STACK_H_

typedef struct stackNode {

void *value;

struct stackNode *next;

} stackNode;

typedef struct stack {

stackNode *top;

void (*free)(void *ptr);

unsigned long size;

} stack;

/* Functions implemented as macros */

#define stackTop(s) ((s)->top)

#define stackSize(s) ((s)->size)

#define stackSetFreeMethod(s, m) ((s)->free = (m))

#define stackGetFreeMethod(s) ((s)->free)

stack *stackCreate(void);

stack *stackPush(stack *stack, void *value);

stackNode *stackPop(stack *stack);

void stackClear(stack *stack);

#endif /* _STACK_H_ */

/* stack.c */

#include <stdlib.h>

#include "stack.h"

stack *stackCreate(void)

{

struct stack *stack;

if ((stack = (struct stack *)malloc(sizeof(struct stack))) == NULL)

return NULL;

stack->top = NULL;

stack->free = NULL;

stack->size = 0;

return stack;

}

stack *stackPush(stack *stack, void *value)

{

stackNode *node;

if ((node = (stackNode *)malloc(sizeof(stackNode))) == NULL)

return NULL;

node->value = value;

node->next = (stack->size == 0) ? NULL : stack->top;

stack->top = node;

stack->size++;

return stack;

}

stackNode *stackPop(stack *stack)

{

stackNode *node;

node = stack->top;

if (stack->size != 0) {

stack->top = node->next;

stack->size--;

}

return node;

}

void stackClear(stack *stack)

{

unsigned long size;

stackNode *current, *next;

current = stack->top;

size = stack->size;

while (size--) {

next = current->next;

if (stack->free) stack->free(current->value);

free(current);

current = next;

}

free(stack);

}

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

class Stack(object):

"""A stack encapsulation based on list."""

def __init__(self):

self.items = []

def empty(self):

return self.items == []

def clear(self):

del self.items[:]

@property

def size(self):

return len(self.items)

def push(self, item):

"""Add a new item to the top of the stack."""

self.items.insert(0, item)

def pop(self):

"""Remove the top item from the stack."""

return self.items.pop(0)

def top(self):

"""Return the top item from the stack but not

remove it.

"""

return self.items[0]

def __iter__(self):

return iter(self.items)

def __next__(self):

return self.pop()

1

2

3

4

5

6

7

8

9

10

11

def check_pares(exp):

"""Check if parentheses match in a expression."""

stack = Stack()

pares = {')': '(', ']': '[', '}': '{'}

for x in exp:

if x in '([{':

stack.push(x)

elif x in ')]}':

if stack.empty() or pares[x] != stack.pop():

return False

return True if stack.empty() else False

1

2

3

4

5

6

7

8

9

10

def dec2bin(dec):

"""Converting decimal number to binary string."""

if dec == 0:

return '0'

stack = Stack()

while dec:

r = dec % 2

stack.push(r)

dec = dec // 2

return ''.join(str(digit) for digit in stack)

1

2

3

4

5

6

7

8

9

10

11

12

13

def preorder_traversal(root):

"""

1

/ \

2 3

/ \ \

4 5 6

"""

if not root:

return

print(root.val)

preorder_traversal(root.lchild)

preorder_traversal(root.rchild)

1

2

3

4

5

6

7

8

9

def preorder_traversal(root)

s = Stack()

while s.size or root:

if root:

print(root.val)

s.push(root)

root = root.lchild

else:

root = s.pop().rchild