C++ STL中的栈与队列：核心原理与实战应用指南

在C++标准模板库（STL）中，stack（栈）和queue（队列）是两个重要的容器适配器，它们通过封装底层容器（默认使用deque）实现了特定的数据操作逻辑。本文将深入探讨它们的设计原理、常用操作及典型应用场景，帮助开发者快速掌握其核心用法。

一、栈（stack）：后进先出的数据管理
核心特性与初始化

栈遵循后进先出（LIFO）原则，仅允许在栈顶进行插入和删除操作。其底层通常基于deque或list容器实现。

include <stack>

std::stack<int> s;  // 默认基于deque的整型栈

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x压入栈顶 s.push(10);
pop() 移除栈顶元素（不返回值） s.pop();
top() 返回栈顶元素的引用（需非空检查） int val = s.top();
empty() 判断栈是否为空（返回布尔值） if (s.empty()) {...}
size() 返回栈中元素数量 int cnt = s.size();

操作示例：遍历栈并输出所有元素

std::stack<int> s;
s.push(1); s.push(2); s.push(3);
while (!s.empty()) {
    std::cout << s.top() << " ";  // 输出：3 2 1
    s.pop();

典型应用场景

括号匹配：通过栈结构检测表达式中的括号嵌套是否正确

深度优先搜索（DFS）：递归算法中隐式使用栈管理访问路径

撤销操作：文本编辑器中按顺序记录操作步骤

二、队列（queue）：先进先出的任务调度
核心特性与初始化

队列遵循先进先出（FIFO）原则，元素在队尾插入，队首删除。底层同样基于deque或list实现。

include <queue>

std::queue<std::string> q;  // 字符串队列

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x插入队尾 q.push("task1");
pop() 移除队首元素（不返回值） q.pop();
front() 返回队首元素的引用（需非空检查） auto task = q.front();
back() 返回队尾元素的引用 auto last = q.back();
empty() 判断队列是否空 if (q.empty()) {...}
size() 返回队列元素数量 int len = q.size();

操作示例：处理任务队列

std::queue<int> q;
q.push(10); q.push(20); q.push(30);
while (!q.empty()) {
    std::cout << q.front() << " ";  // 输出：10 20 30
    q.pop();

典型应用场景

广度优先搜索（BFS）：按层次遍历树或图结构

消息队列：异步处理系统中的任务缓冲

打印任务调度：保证文档按提交顺序打印

三、进阶扩展：优先队列（priority_queue）
优先队列是队列的变种，元素按优先级排序（默认最大堆）。常用于任务调度系统：
include

// 小顶堆示例
std::priority_queue<int, std::vector, std::greater> pq;
pq.push(3); pq.push(1); pq.push(4);
pq.top(); // 返回1（当前最小元素）

在C语言中，原子量（Atomic）用于实现多线程环境下的无锁同步操作，确保对共享变量的操作是不可分割的（即原子性）。C11标准引入了 <stdatomic.h> 头文件，提供了对原子操作的支持。
互斥量用于保护多行代码块，原子量可以保护一行代码（对原子变量的操作）。以下是原子量的核心用法和注意事项：

1. 原子类型声明

使用 _Atomic 修饰符声明原子变量：

#include <stdatomic.h>

_Atomic int counter = ATOMIC_VAR_INIT(0); // 声明并初始化为0

或简写：

atomic_int counter = 0; // 等效于 _Atomic int

2. 基本原子操作

加载（Load）和存储（Store）

int value;
value = atomic_load(&counter);        // 原子读取
atomic_store(&counter, 42);          // 原子写入

交换（Exchange）

int old = atomic_exchange(&counter, 100); // 将counter设为100，返回旧值

比较并交换（CAS, Compare-And-Swap）

int expected = 10;
int desired = 20;
if (atomic_compare_exchange_strong(&counter, &expected, desired)) {
    // 成功：counter原值为expected，被更新为desired
} else {
    // 失败：counter当前值 != expected，expected被更新为实际值
}

3. 原子算术/位运算

atomic_fetch_add(&counter, 5);    // 原子加5，返回旧值
atomic_fetch_sub(&counter, 3);    // 原子减3
atomic_fetch_or(&counter, 0x1);   // 原子按位或
atomic_fetch_and(&counter, ~0x1); // 原子按位与

4. 内存顺序（Memory Order）

指定原子操作的内存同步行为，控制指令重排和可见性：

atomic_store_explicit(&counter, 42, memory_order_release); // 写入释放
int val = atomic_load_explicit(&counter, memory_order_acquire); // 读取获取

常用选项：
• memory_order_relaxed：仅保证原子性，无同步/顺序约束。
• memory_order_acquire：本操作前的所有读写不会被重排到它之后。
• memory_order_release：本操作后的所有读写不会被重排到它之前。
• memory_order_seq_cst：严格顺序一致性（默认）。

5. 示例：线程安全的计数器

#include <stdatomic.h>
#include <stdio.h>
#include <threads.h>

atomic_int counter = 0;

int thread_func(void *arg) {
    for (int i = 0; i < 10000; i++) {
        atomic_fetch_add(&counter, 1);
    }
    return 0;
}

int main() {
    thrd_t t1, t2;
    thrd_create(&t1, thread_func, NULL);
    thrd_create(&t2, thread_func, NULL);
    thrd_join(t1, NULL);
    thrd_join(t2, NULL);
    printf("Counter: %d\n", counter); // 正确输出20000
    return 0;
}

6. 注意事项

1. 性能：原子操作比普通操作慢，仅在必要时使用。
2. 适用场景：简单共享变量（如标志、计数器），复杂逻辑仍需互斥锁。
3. 兼容性：需C11及以上编译器（如GCC -std=c11）。
4. 避免ABA问题：CAS操作需注意值被其他线程多次修改的情况。

7. 扩展知识

• 无锁编程：原子量是实现无锁数据结构的基础（如队列、栈）。
• 编译器屏障：atomic_signal_fence() 用于线程与信号处理函数间的同步。

通过合理使用原子量，可以高效解决多线程竞争问题，但需谨慎设计以避免逻辑错误。

UNIX 98伪终端核心系统调用及实践实现

1. UNIX 98伪终端核心系统调用

以下为伪终端的工作模式，伪终端即伪终端对，分为伪终端主设备与伪终端从设备。主设备向用户显示信息或读取输入，从设备与作业进程交互。
驱动程序介于两者之间，维护有输入队列(主设备->从设备)与输出队列(从设备->主设备)。回显指的是将输入队列的数据添加至输出队列，这里的行缓冲（不同于stdio库的行缓冲）指输入队列出现换行符才将输入队列的内容发给从设备供前台进程组读取。

1.1 posix_openpt

功能描述

打开伪终端主设备（PTY Master），返回主设备文件描述符。

函数声明

#include <stdlib.h>
#include <fcntl.h>

int posix_openpt(int flags);

参数详解

• flags：打开模式标志位（按位或组合）：

  • O_RDWR：必须指定的读写模式
  • O_NOCTTY：防止成为控制终端
  • O_CLOEXEC：设置close-on-exec标志

返回值

• 成功：返回主设备文件描述符（≥3）

• 失败：返回-1，设置errno：

  • ENOMEM：内核内存不足
  • ENOSPC：伪终端资源耗尽
  • EMFILE：进程文件描述符达上限

1.2 grantpt

功能描述

设置从设备（PTY Slave）的权限为可访问。

函数声明

#include <stdlib.h>

int grantpt(int master_fd);

参数详解

• master_fd：由posix_openpt返回的主设备描述符

返回值

• 成功：返回0

• 失败：返回-1，设置errno：

  • EINVAL：无效文件描述符
  • EACCES：权限不足

1.3 unlockpt

功能描述

解除主设备的访问锁，允许从设备被打开。

函数声明

#include <stdlib.h>

int unlockpt(int master_fd);

参数详解

• master_fd：已通过grantpt授权的主设备描述符

返回值

• 成功：返回0

• 失败：返回-1，设置errno：

  • EINVAL：无效文件描述符

1.4 ptsname

功能描述

获取伪终端从设备路径名。

函数声明

#include <stdlib.h>

char *ptsname(int master_fd);

参数详解

• master_fd：已解锁的主设备描述符

返回值

• 成功：返回从设备路径字符串指针（如/dev/pts/5）

• 失败：返回NULL，设置errno：

  • EINVAL：无效文件描述符

2. ptyMasterOpen函数实现

功能目标

打开伪终端主设备并完成初始化配置，返回从设备路径。

函数原型

#include <fcntl.h>
#include <string.h>
#include <errno.h>

int ptyMasterOpen(char *slaveName, size_t snLen) {
    int master_fd;
    char *slave_path;
    
    master_fd = posix_openpt(O_RDWR | O_NOCTTY);
    if (master_fd == -1) return -1;

    if (grantpt(master_fd) == -1) {
        close(master_fd);
        return -1;
    }

    if (unlockpt(master_fd) == -1) {
        close(master_fd);
        return -1;
    }

    slave_path = ptsname(master_fd);
    if (slave_path == NULL) {
        close(master_fd);
        errno = EINVAL;
        return -1;
    }

    if (strlen(slave_path) >= snLen) {
        close(master_fd);
        errno = EOVERFLOW;
        return -1;
    }

    strncpy(slaveName, slave_path, snLen);
    return master_fd;
}

关键处理逻辑

• 缓冲区验证：通过strlen校验目标缓冲区容量
• 错误处理链：确保资源泄露防护
• 标志位组合：O_RDWR|O_NOCTTY保证基本功能

3. ptyFork函数实现

3.1 核心数据结构

termios结构体（终端属性）

struct termios {
    tcflag_t c_iflag;  // 输入模式标志
    tcflag_t c_oflag;  // 输出模式标志
    tcflag_t c_cflag;  // 控制模式标志
    tcflag_t c_lflag;  // 本地模式标志
    cc_t c_cc[NCCS];   // 控制字符数组
};

winsize结构体（窗口尺寸）

struct winsize {
    unsigned short ws_row;    // 行数
    unsigned short ws_col;    // 列数
    unsigned short ws_xpixel; // 水平像素
    unsigned short ws_ypixel; // 垂直像素
};

3.2 函数实现

#include <unistd.h>
#include <sys/ioctl.h>

pid_t ptyFork(int *masterFd, char *slaveName, size_t snLen,
              const struct termios *slaveTermios,
              const struct winsize *slaveWS) {
    int mfd, saved_errno;
    pid_t childPid;

    mfd = ptyMasterOpen(slaveName, snLen);
    if (mfd == -1) return -1;

    childPid = fork();
    if (childPid == -1) {
        saved_errno = errno;
        close(mfd);
        errno = saved_errno;
        return -1;
    }

    if (childPid != 0) {  // 父进程
        *masterFd = mfd;
        return childPid;
    }

    // 子进程执行流
    if (setsid() == -1) _exit(EXIT_FAILURE);

    close(mfd);

    int slave_fd = open(slaveName, O_RDWR);
    if (slave_fd == -1) _exit(EXIT_FAILURE);

#ifdef TIOCSCTTY
    if (ioctl(slave_fd, TIOCSCTTY, 0) == -1)
        _exit(EXIT_FAILURE);
#endif

    if (slaveTermios && tcsetattr(slave_fd, TCSANOW, slaveTermios) == -1)
        _exit(EXIT_FAILURE);

    if (slaveWS && ioctl(slave_fd, TIOCSWINSZ, slaveWS) == -1)
        _exit(EXIT_FAILURE);

    dup2(slave_fd, STDIN_FILENO);
    dup2(slave_fd, STDOUT_FILENO);
    dup2(slave_fd, STDERR_FILENO);

    if (slave_fd > STDERR_FILENO)
        close(slave_fd);

    return 0;
}

3.3 关键操作说明

1. 会话控制：

   • setsid()：创建新会话，脱离原终端控制
   • TIOCSCTTY：显式获取控制终端（BSD兼容）

2. 描述符重定向：

   • dup2三步操作：实现标准流全重定向

3. 属性继承：

   • tcsetattr：精确复制原终端行为特征
   • TIOCSWINSZ：保持窗口尺寸一致性

4. 系统调用关系图谱

graph TD
    A[posix_openpt] --> B[grantpt]
    B --> C[unlockpt]
    C --> D[ptsname]
    D --> E[ptyMasterOpen]
    E --> F[fork]
    F --> G[setsid]
    G --> H[ioctl-TIOCSCTTY]
    H --> I[tcsetattr]
    I --> J[dup2]

通过系统调用的组合使用，可构建完整的伪终端通信通道，为高级终端应用开发奠定基础。

Linux信号处理深度解析：从基础到高级应用

1. 信号发送机制

1.1 kill系统调用

功能：向指定进程或进程组发送信号
函数声明：

#include <sys/types.h>
#include <signal.h>

int kill(pid_t pid, int sig);

参数说明：
• pid：目标进程/进程组标识符
• >0：发送给特定进程
• =0：发送给调用进程所属进程组
• =-1：广播发送给所有有权进程
• <-1：发送给进程组ID为|pid|的组
• sig：信号编号（如SIGTERM=15）

返回值：
• 成功返回0，失败返回-1并设置errno（EPERM/ESRCH/EINVAL）

1.2 killpg系统调用

功能：向指定进程组发送信号
函数声明：

#include <signal.h>

int killpg(pid_t pgrp, int sig);

参数说明：
• pgrp：目标进程组ID（0表示当前进程组）
• sig：同kill系统调用

返回值：
• 同kill系统调用

1.3 raise函数

功能：向当前进程发送信号
函数声明：

#include <signal.h>

int raise(int sig);

参数说明：
• sig：待发送信号编号

返回值：
• 成功返回0，失败返回非0值

2. 信号处理机制

2.1 signal函数

功能：注册标准信号处理函数
函数声明：

#include <signal.h>

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);

参数说明：
• signum：待捕获信号编号（如SIGINT）
• handler：处理函数指针，可取值：
• SIG_IGN：忽略信号
• SIG_DFL：默认处理
• 自定义函数指针

返回值：
• 成功返回原处理函数指针，失败返回SIG_ERR

2.2 sigaction系统调用

功能：支持实时信号处理的增强型注册接口
函数声明：

#include <signal.h>

int sigaction(int signum, 
             const struct sigaction *act,
             struct sigaction *oldact);

struct sigaction {
    void     (*sa_handler)(int);
    void     (*sa_sigaction)(int, siginfo_t *, void *);
    sigset_t   sa_mask;
    int        sa_flags;
    void     (*sa_restorer)(void);
};

参数说明：
• signum：同signal
• act：新处理配置
• sa_handler：标准处理函数
• sa_sigaction：实时信号处理函数（需设置SA_SIGINFO标志）
• sa_mask：执行处理函数期间阻塞的信号集
• sa_flags：控制标志位，常用值：

◦ `SA_NOCLDSTOP`：子进程停止时不产生SIGCHLD
◦ `SA_RESTART`：自动重启被中断的系统调用
◦ `SA_SIGINFO`：使用sa_sigaction处理函数

• oldact：保存原处理配置

siginfo_t结构体：

typedef struct {
    int      si_signo;    /* 信号编号 */
    int      si_code;     /* 信号来源 */
    pid_t    si_pid;      /* 发送进程PID */
    uid_t    si_uid;      /* 发送进程UID */
    void    *si_addr;     /* 引发故障的内存地址 */
    int      si_status;   /* 子进程退出状态 */
    union sigval si_value;/* 伴随数据 */
} siginfo_t;

返回值：
• 成功返回0，失败返回-1

3. 信号屏蔽控制

3.1 sigprocmask系统调用

功能：修改进程信号屏蔽字
函数声明：

#include <signal.h>

int sigprocmask(int how, 
               const sigset_t *set,
               sigset_t *oldset);

参数说明：
• how：操作类型
• SIG_BLOCK：添加set到屏蔽集
• SIG_UNBLOCK：从屏蔽集移除set
• SIG_SETMASK：直接设置屏蔽集为set
• set：待操作信号集
• oldset：保存原屏蔽集

返回值：
• 成功返回0，失败返回-1

4. 信号等待策略

4.1 sigsuspend系统调用

功能：原子操作解除信号屏蔽并等待信号
函数声明：

#include <signal.h>

int sigsuspend(const sigset_t *mask);

参数说明：
• mask：临时信号屏蔽字

返回值：
• 总是返回-1，errno=EINTR

4.2 sigwaitinfo系统调用

功能：同步等待指定信号并获取详细信息
函数声明：

#include <signal.h>

int sigwaitinfo(const sigset_t *set,
               siginfo_t *info);

参数说明：
• set：等待信号集合
• info：接收信号详细信息

返回值：
• 成功返回信号编号，失败返回-1

4.3 sigtimedwait系统调用

功能：带超时的信号等待
函数声明：

#include <signal.h>

int sigtimedwait(const sigset_t *set,
                siginfo_t *info,
                const struct timespec *timeout);

参数说明：
• timeout：超时时间结构体

struct timespec {
    time_t tv_sec;   /* 秒 */
    long   tv_nsec;  /* 纳秒 */
};

返回值：
• 成功返回信号编号，超时返回-1且errno=EAGAIN

综合对比表