数据结构：栈与队列之特殊线性表-栈的概念及操作

"单链表中的数据结点类型QNode被定义，以及链队的头结点类型LiQueue的定义，这两个数据结构是栈和队列实现的基础。内容涉及第3章栈和队列，包括栈和队列的概念、性质以及它们在解决问题中的应用，如迷宫问题、回文数判断和括号匹配。" 本文主要讨论了数据结构中的两种特殊线性表——栈和队列。栈是一种限制仅在表尾进行插入和删除操作的数据结构，这种操作特性被称为“后进先出”或“先进后出”（LIFO）。当一个元素被添加到栈中，这个过程称为入栈或压栈；反之，从栈中移除元素则称为出栈或弹栈。栈的两个端点分别是栈顶和栈底，通常在实现时，栈顶是动态变化的，而栈底是固定的。 在栈的示例中，假设我们有三个元素a、b和c依次入栈，每个元素只能入栈一次。根据栈的LIFO特性，可能出现的出栈序列有多种情况。例如，情况1下，c可以首先出栈，接着b出栈，最后a出栈，即出栈序列可以是c、b、a。另一种情况2中，b可能首先出栈，然后c出栈，最后a出栈，即出栈序列可以是b、c、a，或者b出栈后c不出栈，直接a出栈，序列变为b、a，或者b出栈后，c先出栈，再是a，序列也是b、c、a。 队列则是一种遵循“先进先出”（FIFO）原则的数据结构。在队列中，新元素在队尾加入，旧元素从队头移出。队列的典型操作包括入队（enqueue）和出队（dequeue）。队列的应用广泛，例如在操作系统中用于任务调度，或在数据传输中作为缓冲区。 在实际问题中，栈和队列常常用来解决特定的问题。例如，迷宫问题中可以利用栈进行深度优先搜索，判断回文数时可以使用栈来比较字符串正反两端的字符，而括号匹配问题则可以通过栈来检查左括号和右括号的对应关系。 栈和队列是数据结构的基础组成部分，它们的特性使得它们在算法设计和程序实现中扮演着重要角色。理解并熟练掌握这两种数据结构及其操作，对于解决计算机科学中的许多问题至关重要。