C++容器：stack与queue的应用场景与实现

# 1. 简介
## 1.1 C 容器的概念
## 1.2 stack 的概念和特点
## 1.3 queue 的概念和特点

在这一章节中，我们将介绍 C 容器的概念以及其中的两个常用数据结构：栈（stack）和队列（queue）。栈和队列是常用的数据结构，它们分别具有特定的操作规则和特点。在很多编程场景中，栈和队列能够提供高效的解决方案。

## 1.1 C 容器的概念

在 C 语言中，容器是一种用于存储和操作数据元素的对象。C 提供了多种容器，包括数组、链表、栈、队列等。每种容器都具有不同的特点和适用场景。

## 1.2 stack 的概念和特点

栈是一种特殊的线性数据结构，它具有后进先出（Last In First Out，LIFO）的特点。在栈中，元素的插入和删除操作只能在栈顶进行，其他位置的元素不可访问。栈可以通过数组或链表实现。

## 1.3 queue 的概念和特点

队列是一种线性数据结构，它具有先进先出（First In First Out，FIFO）的特点。在队列中，元素的插入操作在队尾进行，删除操作在队头进行。队列也可以通过数组或链表实现。

在接下来的章节中，我们将详细介绍栈和队列的应用场景、实现方式和操作方法。
## 2. stack 的应用场景

### 2.1 数据结构：栈的应用

栈作为一种常见的数据结构，被广泛应用于各种算法和程序设计中。下面是一些栈的常见应用场景。

- **逆序输出**：栈可以将输入的数据按照逆序输出。例如，我们可以将一个字符串逆序输出，只需将字符串的每个字符依次入栈，然后再依次出栈。

import java.util.Stack;

public class ReverseString {
    public static void main(String[] args) {
        String str = "Hello, world!";
        Stack<Character> stack = new Stack<>();
        
        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));
        }
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }
}

运行结果为：`!dlrow ,olleH`

- **括号匹配**：栈可以用于检查括号是否匹配。例如，我们可以用栈来判断一个字符串中的括号是否合法闭合。

def is_valid_parentheses(s):
    stack = []
    pairs = {
        '(': ')',
        '[': ']',
        '{': '}'
    }
    
    for c in s:
        if c in pairs:
            stack.append(c)
        elif c in pairs.values():
            if stack and pairs[stack[-1]] == c:
                stack.pop()
            else:
                return False
    
    return len(stack) == 0

s1 = "(){}[]"
s2 = "({[}])"

print(is_valid_parentheses(s1))  # True
print(is_valid_parentheses(s2))  # False

运行结果为：

True
False

- **计算后缀表达式**：后缀表达式也称为逆波兰表达式，它可以通过栈来计算。对于一个给定的后缀表达式，我们可以使用栈实现一个简单的计算器。

package main

import (
	"fmt"
	"strconv"
	"strings"
)

type Stack struct {
	data []int
}

func (s *Stack) Push(n int) {
	s.data = append(s.data, n)
}

func (s *Stack) Pop() int {
	length := len(s.data)
	if length == 0 {
		panic("Stack is empty")
	}

	num := s.data[length-1]
	s.data = s.data[:length-1]
	return num
}

func isOperator(str string) bool {
	operators := []string{"+", "-", "*", "/"}
	for _, operator := range operators {
		if operator == str {
			return true
		}
	}
	return false
}

func calculate(expression string) int {
	stack := Stack{}
	tokens := strings.Split(expression, " ")

	for _, token := range tokens {
		if isOperator(token) {
			// Pop the top two numbers from the stack
			num2 := stack.Pop()
			num1 := stack.Pop()
			switch token {
			case "+":
				stack.Push(num1 + num2)
			case "-":
				stack.Push(num1 - num2)
			case "*":
				stack.Push(num1 * num2)
			case "/":
				stack.Push(num1 / num2)
			}
		} else {
			// Parse the number and push it onto the stack
			num, _ := strconv.Atoi(token)
			stack.Push(num)
		}
	}

	return stack.Pop()
}

func main() {
	expression := "5 3 4 * + 6 -"
	result := calculate(expression)
	fmt.Println(result) // Output: 17
}

运行结果为：

17

### 2.2 函数调用：函数调用栈的应用

栈在函数调用过程中起到了重要的作用。当程序调用一个函数时，会将函数返回地址、局部变量、参数等信息存放在栈中，逐层压栈。函数执行完毕后，会从栈中逐层弹栈，返回到调用函数的位置。

下面是一个简单的代码示例，展示了函数调用过程中栈的应用。在这个示例中，函数 `b` 调用了函数 `c`，并返回了结果。

function a() {
    console.log('Inside function a');
}

function b() {
    console.log('Inside function b, calling function c');
    c();
}

function