How to implement stack and typical applications using C language and Python

Preface

What is a stack? You can understand it as a first-in-last-out data structure (First In Last Out), a linear table with limited operations...

C implementation

With the help of void pointers and function pointers in C language, we can implement a chained universal stack:

/* 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 
#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);
}

Here The implementation is attached with a head node, which is mainly used to register functions related to stack node operations. We also store the stack size information, so that we can get the current stack size in O(1) time!

Python implementation

In Python, list can actually be used directly as a stack, if you only operate on one end of it. Of course, we can also simply encapsulate it:

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

Here are some typical applications of the stack.

Bracket matching

Given an arithmetic expression or a piece of C code, how to write a program to verify whether the brackets in it match? With the help of the stack, this can be easily achieved. The algorithm flow is as follows:

Traverse characters:

1. If it is a left bracket, push it onto the stack;

2. If it is a right bracket, this If the stack is empty at this time, it means there is a mismatch. If the stack is not empty and the left bracket and the right bracket that are popped are of different types, it means there is a mismatch;

After the traversal is completed, if the stack is not Empty means no match.

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

Number system conversion

Take decimal to binary conversion as an example:

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)

Simulated recursion

Traversing a binary tree is a classic recursive application. Let's take preorder traversal as an example. The recursive version of the code is easy to write:

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)

The following is the non-recursive version:

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

Summary

The above is all about how to use C language and Python to implement stacks and typical applications. I hope it will be helpful to everyone's learning, and I hope everyone will continue to support the PHP Chinese website.

For more articles on how to use C language and Python to implement stacks and typical applications, please pay attention to the PHP Chinese website!