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진수를 이진수로 변환하는 예:

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를 지원해 주시길 바랍니다. 중국사이트.

C 언어와 Python을 사용하여 스택과 일반적인 애플리케이션을 구현하는 방법에 대한 더 많은 기사를 보려면 PHP 중국어 웹사이트에 주목하세요!