So implementieren Sie Stack- und typische Anwendungen mit der Sprache C und Python

Vorwort

Was ist ein Stapel? Sie können ihn als eine First-In-Last-Out-Datenstruktur (First In Last Out) verstehen, eine lineare Tabelle mit begrenzten Operationen...

C-Implementierung

Mit Hilfe von Void-Zeigern und Funktionszeigern in der C-Sprache können wir einen verketteten Universalstapel implementieren:

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

Die Implementierung hier ist mit einem Hauptknoten verbunden, der hauptsächlich zum Registrieren von Funktionen im Zusammenhang mit Stapelknotenoperationen verwendet wird. Wir speichern auch die Informationen zur Stapelgröße, sodass wir die aktuelle Stapelgröße in O(1)-Zeit erhalten können!

Python-Implementierung

In Python kann die Liste tatsächlich direkt als Stapel verwendet werden, wenn Sie nur an einem Ende davon arbeiten. Natürlich können wir es auch einfach kapseln:

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

Anwendung

Im Folgenden werden einige typische Anwendungen des Stapels vorgestellt.

Klammerabgleich

Wie schreibe ich bei einem gegebenen arithmetischen Ausdruck oder einem Teil des C-Codes ein Programm, um zu überprüfen, ob die darin enthaltenen Klammern übereinstimmen? Mit Hilfe des Stapels lässt sich dies leicht erreichen. Der Algorithmusablauf ist wie folgt:

Zeichen durchqueren:

1. Wenn es sich um eine linke Klammer handelt, schieben Sie sie auf den Stapel; 2 Wenn es sich um eine rechte Klammer handelt, bedeutet dies, dass eine Nichtübereinstimmung vorliegt. Wenn der Stapel nicht leer ist und die geöffnete linke Klammer und die rechte Klammer unterschiedlicher Art sind, liegt eine Nichtübereinstimmung vor ;

Wenn der Stapel nach Abschluss des Durchlaufs nicht leer ist, bedeutet dies, dass keine Übereinstimmung vorliegt.

Zahlensystemkonvertierung

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

Nehmen Sie die Konvertierung von Dezimalzahlen in Binärzahlen als Beispiel:

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)

Simulierte Rekursion

Das Durchlaufen eines Binärbaums ist eine klassische rekursive Anwendung. Nehmen wir als Beispiel die Vorbestellungsdurchquerung. Die rekursive Version des Codes ist einfach zu schreiben:

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)

Das Folgende ist die nicht rekursive Version:

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

Zusammenfassung

Das Obige dreht sich alles um die Verwendung von C-Sprache und Python zur Implementierung von Stapeln und typischen Anwendungen. Ich hoffe, dass es für das Lernen aller hilfreich sein wird, und ich hoffe, dass alle fortfahren zur Unterstützung der chinesischen PHP-Website.

Weitere Artikel zur Verwendung der C-Sprache und Python zur Implementierung von Stacks und typischen Anwendungen finden Sie auf der chinesischen PHP-Website!