C言語とPythonを使ったスタックと代表的なアプリケーションの実装方法

まえがき

スタックとは何ですか? 先入れ後出しのデータ構造 (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 では、リストの一端のみを操作する場合、実際にはリストをスタックとして直接使用できます。もちろん、単純にカプセル化することもできます:

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

以下では、スタックの典型的なアプリケーションをいくつか紹介します。

括弧の一致

算術式または C コードの一部が与えられた場合、その中の括弧が一致するかどうかを検証するプログラムをどのように作成すればよいでしょうか?スタックを利用すると、これを簡単に実現できます。アルゴリズム フローは次のとおりです:

文字のトラバース:

1. 左括弧の場合、スタックにプッシュします。

2. 右括弧の場合、この時点でスタックが空の場合スタックが空でない場合、ポップ スタックの左括弧と右括弧の型が異なるため、不一致を示します。

スタックが空でない場合。 、不一致を示します。

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

数体系の変換

10 進数から 2 進数への変換を例に挙げます。

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 スタックと典型的なアプリケーションを実装するための内容は、皆様の学習に役立つことを願っています。また、皆様には引き続き PHP 中国語 Web サイトをサポートしていただければ幸いです。

C 言語と Python を使用してスタックと一般的なアプリケーションを実装する方法に関するその他の記事については、PHP 中国語 Web サイトに注目してください。