머리말
스택이란 무엇입니까? 선입후출(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 중국어 웹사이트에 주목하세요!