前言
棧是什麼，你可以理解為一種先入後出的數據結構（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中，list其實可以直接當作堆疊使用，如果你只在它的一端進行操作的話。當然我們也可以簡單封裝一下：
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()
應用
下面介紹幾個堆疊的典型應用。
括號符合
給你一個算術表達式或一段C程式碼，如何寫一個程式驗證它其中的括號是否符合？借助棧，可以很容易實現。演算法流程如下：
遍歷字元：
1.如果是左括號，push入棧；
棧pop出棧的左括號與右括號類型不一樣，表示不符；
遍歷結束後，若堆疊不為空，則表示不符。
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數制轉換
以十進制轉二進制為例：
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
總結
以上就是如何用典型的全部語言和Python實作內容，希望對大家的學習有幫助，也希望大家繼續支持PHP中文網。
更多如何用C語言、Python實作堆疊及典型應用相關文章請關注PHP中文網！
