如何用C語言、Python實現棧及典型應用

更新時間：2016年08月05日 15:26:53 投稿：daisy

本文先通過實例分別介紹了如何用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);
}

這里的實現附設了一個頭節(jié)點，主要用于注冊與棧節(jié)點操作相關的函數。我們把棧的大小信息也存了進去，這樣就可以在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入棧；

2. 如果是右括號，這時候如果棧為空，說明不匹配，如果棧不為空并且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

總結

以上就是如何用C語言和Python實現棧及典型應用的全部內容，希望對大家的學習有所幫助，也希望大家繼續(xù)支持腳本之家。

您可能感興趣的文章: