如何用C语言、Python实现栈及典型应用

什么是栈

在计算机科学中，栈是一种实现了一端插入与删除、后进先出（LIFO）操作的有序集合。它就像是一个被限定了插入和删除操作的列表，在这里，插入操作称为推入操作，而删除操作则被称为弹出操作。只有最后插入的数据才能被弹出，想象一下备胎储备仓库或者图书馆书籍储藏室，可以帮助我们更好地理解栈数据结构的本质。

如何实现栈

C语言实现栈

在C语言中，可以使用数组和指针来实现栈。以下是一个简单的栈数据结构示例，代码注释中有详细的解释：

#include <stdio.h>
#define MAXSIZE 10

// 初始化栈
struct stack
{
    int item[MAXSIZE];
    int top;
};

void initStack(struct stack *s)
{
    s->top = -1;
}

// 创建一个栈
struct stack* createStack()
{
    struct stack *s = (struct stack*)malloc(sizeof(struct stack));
    initStack(s);
    return s;
}

// 判断栈是否为空
int isEmpty(struct stack *s)
{
    if (s->top == -1)
        return 1;
    else
        return 0;
}

//判断栈是否为满
int isFull(struct stack *s)
{
    if (s->top == MAXSIZE - 1)
        return 1;
    else
        return 0;
}

// 向栈中压入数据
void push(struct stack *s, int element)
{
    if (isFull(s))
        printf("栈已满，无法继续插入元素！\n");
    else
        s->item[++s->top] = element;
}

// 从栈中弹出数据
int pop(struct stack *s)
{
    if (isEmpty(s))
    {
        printf("栈已经为空，无法继续弹出元素！\n");
        return -1;
    }
    else
        return s->item[s->top--];
}

// 获取栈顶元素
int peek(struct stack *s)
{
    if (isEmpty(s))
    {
        printf("栈已经为空，无法继续获取栈顶元素！\n");
        return -1;
    }
    else
        return s->item[s->top];
}

int main()
{
    struct stack *s = createStack();

    push(s, 1);
    push(s, 2);
    push(s, 3);

    printf("栈中第1个元素:%d\n", peek(s));
    printf("弹出了一个元素：%d\n", pop(s));
    printf("弹出了一个元素：%d\n", pop(s));
    printf("弹出了一个元素：%d\n", pop(s));

    getchar();

    return 0;
}

Python实现栈

在Python中，可以使用list列表来实现栈。以下是一个简单栈数据结构示例，代码注释中有详细的说明：

class Stack:
    # 初始化栈
    def __init__(self):
        self.items = []

    # 判断栈是否为空
    def is_empty(self):
        return self.items == []

    # 向栈中压入数据
    def push(self, item):
        self.items.append(item)

    # 从栈中弹出数据
    def pop(self):
        return self.items.pop()

    # 获取栈顶元素
    def peek(self):
        return self.items[-1]

    # 获取栈的大小
    def size(self):
        return len(self.items)

# 创建一个栈
s = Stack()

s.push(1)
s.push(2)
s.push(3)

print("栈中第1个元素：", s.peek())
print("弹出了一个元素：", s.pop())
print("弹出了一个元素：", s.pop())
print("弹出了一个元素：", s.pop())

input("按下回车退出程序...")

栈的典型应用

栈是一种非常实用的数据结构，主要应用在以下方面：

1.函数调用

当函数被调用时，所有的参数和局部变量的值被保存在一个栈内存空间中。当函数完成时，这些变量的值就从栈内存空间中弹出，并且内存空间被释放。

2.括号匹配

栈可以用于检查输入的字符串中的括号（包括圆括号、方括号、大括号）是否匹配。当我们遇到左括号时，就将其压入栈中，当我们遇到右括号时，就从栈顶弹出一个左括号，如果这个左括号能够与右括号匹配，那么就说明我们已经找到了一对匹配的括号对。

以下是一个Python实现的括号匹配示例：

def brackets_match(str):
    # 定义一个栈
    s = Stack()

    # 定义字典，用于存储左括号和右括号的对应关系
    dict = {")": "(", "]": "[", "}": "{"}

    # 遍历输入的字符串
    for char in str:
        # 判断当前字符是否是左括号
        if char in "([{":
            # 如果是左括号，就将其压入栈中
            s.push(char)
        # 判断当前字符是否是右括号
        elif char in ")]}":
            # 如果是右括号，就从栈顶弹出一个元素
            popped_char = s.pop()
            # 检查弹出的左括号与当前右括号是否匹配
            if dict[char] != popped_char:
                return False

    # 遍历结束后，如果栈不为空，则说明输入的字符串中左右括号不匹配
    if not s.is_empty():
        return False

    return True

# 上述方法使用示例
str = "[{()}]"
result = brackets_match(str)
if result:
    print("输入的字符串中的左右括号匹配！")
else:
    print("输入的字符串中的左右括号不匹配！")

以上是用C语言、Python实现栈及典型应用的完整攻略，其中包含相应代码示例，可以对栈数据结构的理解和运用有更深入的认识。