前言

栈是什么，你可以理解为一种先入后出的数据结构（First In Last Out），一种操作受限的线性表...

C实现

借助与C语言中的void指针及函数指针，我们可以实现一个链式通用栈：

? 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 #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; #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 #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); }

这里的实现附设了一个头节点，主要用于注册与栈节点操作相关的函数。我们把栈的大小信息也存了进去，这样就可以在O(1)的时间内获取当前栈大小了！

Python实现

在Python中，list其实可以直接作为栈使用，如果你只在它的一端进行操作的话。当然我们也可以简单封装一下：

? 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()

应用

下面介绍几个栈的典型应用。

括号匹配

给你一个算术表达式或者一段C代码，如何写一个程序验证它其中的括号是否匹配？借助栈，可以很容易实现。算法流程如下：

遍历字符：

1.如果是左括号，push入栈；

2. 如果是右括号，这时候如果栈为空，说明不匹配，如果栈不为空并且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

总结

以上就是如何用C语言和Python实现栈及典型应用的全部内容，希望对大家的学习有所帮助，也希望大家继续支持服务器之家。