前言
栈是什么，你可以理解为一种先入后出的数据结构（first in last out），一种操作受限的线性表...
c实现
借助与c语言中的void指针及函数指针，我们可以实现一个链式通用栈：
/* 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);
}
这里的实现附设了一个头节点，主要用于注册与栈节点操作相关的函数。我们把栈的大小信息也存了进去，这样就可以在o(1)的时间内获取当前栈大小了！
python实现
在python中，list其实可以直接作为栈使用，如果你只在它的一端进行操作的话。当然我们也可以简单封装一下：
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出栈的左括号与右括号类型不一样，说明不匹配；
遍历结束后，如果栈不为空，说明不匹配。
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
数制转换
以十进制转二进制为例：
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)
模拟递归
遍历二叉树算是经典的递归应用了。我们以先序遍历为例，递归版本的代码很容易写：
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)
下面是非递归的版本：
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实现栈及典型应用的全部内容，希望对大家的学习有所帮助，也希望大家继续支持。
更多如何用c语言、python实现栈及典型应用。