Comment implémenter une pile et des applications typiques en utilisant le langage C et Python

Avant-propos

Qu'est-ce qu'une pile ? Vous pouvez la comprendre comme une structure de données premier entré, dernier sorti (First In Last Out), une table linéaire avec des opérations limitées...

Implémentation C

À l'aide de pointeurs vides et de pointeurs de fonction en langage C, nous pouvons implémenter une pile universelle chaînée :

/* 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);
}

L'implémentation ici est attachée à un nœud principal, qui est principalement utilisé pour enregistrer les fonctions liées aux opérations du nœud de pile. Nous stockons également les informations sur la taille de la pile, afin que nous puissions obtenir la taille actuelle de la pile en un temps O(1) !

Implémentation Python

En Python, la liste peut en fait être utilisée directement comme une pile, si vous n'opèrez que sur une extrémité de celle-ci. Bien sûr, nous pouvons aussi simplement l'encapsuler :

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

Application

Ce qui suit présente plusieurs applications typiques de la pile.

Correspondance des crochets

Étant donné une expression arithmétique ou un morceau de code C, comment écrire un programme pour vérifier si les parenthèses qu'il contient correspondent ? Avec l’aide de la pile, cela peut être facilement réalisé. Le déroulement de l'algorithme est le suivant :

Traverser les caractères :

1. S'il s'agit d'un crochet gauche, poussez-le sur la pile

2. . S'il s'agit d'un crochet droit, cela signifie que la pile est vide et qu'il y a une incompatibilité. Si la pile n'est pas vide et que le crochet gauche et le crochet droit sont de types différents, cela signifie qu'il y a une incompatibilité. ;

Une fois le parcours terminé, si la pile n'est pas vide, cela signifie qu'il n'y a pas de correspondance.

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

Conversion du système numérique

Prenons la conversion décimale en binaire comme exemple :

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)

Récursion simulée

La traversée d'un arbre binaire est une application récursive classique. Prenons l'exemple du parcours de précommande. La version récursive du code est facile à écrire :

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)

Ce qui suit est la version non récursive :

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

Résumé

Ce qui précède concerne la façon d'utiliser le langage C et Python pour implémenter des piles et des applications typiques. J'espère que cela sera utile à l'apprentissage de chacun, et j'espère que tout le monde continuera. pour prendre en charge le site Web PHP chinois.

Pour plus d'articles sur la façon d'utiliser le langage C et Python pour implémenter des piles et des applications typiques, veuillez faire attention au site Web PHP chinois !