登录  /  注册

如何用C语言、Python实现栈及典型应用

高洛峰
发布: 2017-02-07 12:59:56
原创
1058人浏览过

前言

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

如何用C语言、Python实现栈及典型应用

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 = {&#39;)&#39;: &#39;(&#39;, &#39;]&#39;: &#39;[&#39;, &#39;}&#39;: &#39;{&#39;}
 for x in exp:
 if x in &#39;([{&#39;:
 stack.push(x)
 elif x in &#39;)]}&#39;:
 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 &#39;0&#39;
 stack = Stack()
 while dec:
 r = dec % 2
 stack.push(r)
 dec = dec // 2
 return &#39;&#39;.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实现栈及典型应用的全部内容,希望对大家的学习有所帮助,也希望大家继续支持PHP中文网。

更多如何用C语言、Python实现栈及典型应用相关文章请关注PHP中文网!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号