二、栈和队列

栈和队列都是线性结构，它们是操作受限的线性表，即它们的操作是线性表操作的子集。因此也可以用线性表在某种条件下的操作来完成栈和队列的操作。

1. 栈

栈是后进先出的线性表。即限定仅能在表的一端进行插入（入栈）或删除（出栈）操作的线性表。栈结构在计算机中有广泛的应用。常见的如许多软件都有的 “撤销” 和 “恢复” 功能就是用栈实现的。

实现：

template<typename T>class AStack
{//带模板的栈抽象类
public:
  void ClearStack();  //把栈置为空栈
  bool StackEmpty()const;  //若栈为空栈，则返回 true；否则返回 false
  int StackLength()const;  //返回栈的元素个数
  bool GetTop(T &e)const;  //若栈不空，则用e返回栈顶元素，返回true；否则返回false
  bool Push(T e);  //插入元素 e 为新的栈顶元素，成功返回 true；否则返回 false
  bool Pop(T &e); //若栈不空，则删除栈顶元素，用e返回其值，返回true；否则返回false
  void StackTraverse(void(*visit) (T*))const;
  //从栈底到栈顶依次对栈中每个元素调用函数 visit()
};

1.1 栈的顺序存储结构

实现：

//顺序栈的类
template<typename T>class SqStack: public AStack<T>
{//带模板并继承 AStack 的顺序栈类
private:
  T *base, *top;  //栈存储空间的基址，栈顶指针
  int stacksize;  //栈当前的存储容量
public:
  SqStack(int k = 1)  //缺省值为 1
  {//构造函数，动态生成具有 k 个初始存储空间的空栈
    base = new T[k];
    assert(base != NULL);
    top = base;  //栈顶指向栈底
    stacksize = k;
  }
  ~SqStack()
  {//析构函数
    delete[] base;  //释放栈空间
  }
  void ClearStack()
  {//把栈置为空栈
    top = base;  //栈顶指向栈底
  }
  bool StackEmpty()const
  {//若栈为空栈，则返回 true；否则返回 false
    return top == base;
  }
  int StackLength()const
  {//返回栈的元素个数
    return top - base;
  }
  bool GetTop(T &e)const
  {//若栈不为空，则用 e 返回栈顶元素，并返回 true；否则返回 false
    if (top > base)  //栈不空
    {
      e = *(top - 1);  //将栈顶元素赋给 e
      return true;
    }
    else
      return false;
  }
  bool Push(T e)
  {//插入元素 e 为新的栈顶元素，成功返回 true；否则返回 false
    T *newbase;
    if (top - base == stacksize)  //栈满
    {
      newbase = new T[stacksize * 2];
      if (newbase == NULL)
        return false;
      for(int j = 0; j < top - base; j++)
        *(newbase + j) = *(base + j);  //将原栈空间中的数据复制到新的栈空间
      delete[] base;
      base = newbase;
      top = base + stacksize;
      stacksize *= 2;
    }
    *top++ = e;  //将 e 入栈成为新的栈顶元素，栈顶指针上移一个存储单元
    return true;
  }
  bool Pop(T &e)
  {//若栈不为空，则删除栈顶元素，用 e 返回其值，并返回 true; 否则返回 false
    if (top == base)
      return false;
    e = *--top;  //栈顶指针下移一个单元后将栈顶元素赋给 e
    return true;
  }
  void StackTraverse(void(*visit) (T*))const
  {//从栈底到栈顶依次对栈中每个元素调用函数 visit()
    T *p = *base;  
    while(p < top)
      visit(*p++);
    cout << endl;
  }
};

顺序存储结构的线性表在表中插入和删除元素时要移动大量数据元素，导致效率低下。我们把顺序栈中不进行插入和删除操作的栈底设在下标 [0] 处，对应线性表的表头，把栈顶设在下标高端，对应线性表的表尾，这样就避免了移动数据元素，提高了效率。

1.2 栈的链式存储结构

栈也可以用链式存储结构定义。为了提高效率，设置链表的表头为栈顶，链表的表尾为栈底。

实现：

//用双向链表实现链栈的类
template<typename T>class DLinkStack: public AStack<T>, public DLinkList<T>
{//继承 AStack 和 DLinkList 两个类的带模板的链栈类
public:
  void ClearStack()const
  {//把双向循环链表置空即把栈置为空栈
    ClearList();
  }
  bool StackEmpty()const
  {//判断双向循环链表是否为空，即栈是否为空
    return ListLength();
  }
  bool GetTop(T &e)const
  {//若栈不空，用 e 返回栈顶元素，并返回 true；否则返回 false
    return GetElem(1, e);
  }
  bool Push(T e)
  {//插入元素 e 为新的栈顶元素，成功返回 true；否则返回 false
    return ListInsert(1, e);
  }
  bool Pop(T &e)const
  {//若栈不空，则删除栈顶元素，用 e 返回其值，并返回 true；否则返回 false
    return ListDelete(1, e);
  }
  void StackTraverse(void(*visit) (T*))const
  {//从栈底到栈顶依次对栈中每个元素调用函数 visit()
    ListBackTraverse(visit);
    //由双向循环链表的表头出发，逆序对每个元素调用函数 visit()
  }
};

2. 栈的应用和递归

2.1 数制转换

根据栈的先进后出特性，可以用栈来改变顺序。如十进制数 m 转换为 n 进制的结果。方法是将 m 连续除以 n ，所得余数依次是 n 进制由低位到高位的值，但输出却要由高位到低位，可借助先入栈再出栈来改变顺序，输出正确结果。

注意：非负数和负数在转换时的差异。

2.2 表达式求值

算术表达式的求值也要用到栈。原因是在表达式字符串中先出现的运算符不一定先执行，要根据 “从左到右，先乘除后加减，括号优先” 的规则进行运算。计算机使用逆波兰式（后缀表达式）。

2.3 汉诺塔问题与递归实现

如果函数中有直接或间接调用自身函数的语句，这样的函数被称为递归函数。递归函数用得好，可大大简化编程工作。但函数自己调用自己，有可能造成死循环。为了避免死循环，要做到两点：

• 降阶。递归函数虽然调用自身，但并不是简单的重复，它的实参值每次是不一样的。一般逐渐减小，称为降阶。
• 有出口。即在某种条件下，不再进行递归调用。所以递归函数中总有 if 语句。

在函数调用（无论是不是递归调用）中，总是 “先调用的函数后返回，后调用的函数先返回” 。因此用栈来存储函数调用时的各状态值是再合适不过的了。算法语言的编译系统的内部总是设置一个栈来处理函数调用问题。

汉诺塔问题是说明递归调用最好的例子，用递归解决汉诺塔问题算法简单，意义明确。

一般说来，递归算法可以利用循环和自设栈转换为非递归算法。

2.4 迷宫问题

迷宫问题可以递归求解，也可以用栈求解。用栈来求解的算法是由入口试探性地前进，把每一步的状况（当前位置和下一步方向）存入栈中，如果前面的路不通，则可以用出栈退回到前一点，从前一点再向其他方向继续试探。

2.5 皇后问题

皇后问题是回溯算法的典型案例，也会用到栈。

2.6 马踏棋盘问题

马踏棋盘问题是在 N * N 方格的棋盘上，从任意指定方格出发，为马寻找一条或所有条走遍棋盘每一格并且每格只经过一次的路径。

马踏棋盘问题和迷宫问题很相似，都是由当前位置来确定下一步的位置，而且下一步是不曾走过的。不同的是迷宫问题的有解条件是到达出口，马踏棋盘问题的有解条件是走了 N * N 步。

2.7 背包问题

简化的背包问题：有 N 件物品，每件的重量为 w[i] 。背包的承重量为 W ，问能否从这 N 件物品中选若干件放在背包中，使其总重量恰好为 W ？

0-1 背包问题：有 N 件物品和一个容量为 W 的背包。第 i 件物品的重量是 w[i] ，价值是 v[i]。求将哪些物品装入背包可使价值总和最大。

3. 队列

队列是先进先出的线性表。即限定仅能在表的一端（队尾）进行插入（入队）操作，在表的另一端（队头）进行删除（出队）操作的线性表。队列结构在计算机有广泛的应用。常见的如打印机任务的排队就是用队列实现的。

实现：

//队列抽象类
template<typename T>class AQueue
{//带模板的队列抽象类
public:
  void ClearQueue();  //将队列清空为空队列
  bool QueueEmpty()const;  //若队列为空队列，返回 true；否则返回 false
  int QueueLength()const;  //求队列长度
  bool GetHead(T &e)const; //若队列不空，则用e返回队头元素，并返回true，否则false
  bool EnQueue(T e);  //插入元素e为队列的新队尾元素，成功返回true，否则返回false
  bool DeQueue(T &e);  //若队列不空，删除队头元素，用e返回其值，成功返回true
  void QueueTraverse(void(*visit) (T*))const;
  //从队头到队尾依次对队列中每个元素调用函数 visit()
};

3.1 队列的链式存储结构

对列是线性表的子集，故可以将单链表作为链队列的父类，在此基础上派生出子类链队列。

实现：

//链队列的类
template<typename T>class LinkQueue: public AQueue<T>, public LinkList<T>
{//继承 AQueue 和 LinkList 两个类的带模板的类
private:
  LNode<T> *rear;  //队尾指针（子类增加的数据成员）
public:
  LinkQueue()
  {//构造函数，构造一个空队列
    rear = Head;
  }
  void ClearQueue()
  {//将队列清空为空队列
    ClearList();
    rear = Head;
  }
  bool QueueEmpty()const
  {//若队列为空队列，则返回 true；否则返回 false
    return ListEmpty();
  }
  bool QueueLength()const
  {//求队列的长度
    return ListLength();
  }
  bool GetHead(T &e)const
  {//若队列不空，则用 e 返回队头元素，并返回 true；否则返回false
    return GetElem(1, e);
  }
  bool EnQueue(T e)
  {//若插入元素 e 为队列的新队尾元素，成功返回 true；否则返回 false
    LNode<T> *p;
    p = new LNode<T>;  //动态生成新结点
    if (p == NULL)
      return false;
    p->data = e;
    p->next = NULL;
    rear->next = p;
    rear = p;
    return true;
  }
  bool DeQueue(T &e)
  {//若队列不空，删除队头元素，用 e 返回其值，并返回 true；否则返回 false
    bool flag = ListDelete(1, e);  //删除单链表的第 1 个元素，表空则删除失败
    if (Head->next == NULL)  //删除后成为空表
      rear = Head;
    return flag;
  }
  void QueueTraverse(void(*visit) (T*))const
  {//从队头到队尾依次对队列中每个元素调用函数 visit()
    ListTraverse(visit);
  }
};

链队列的 EnQueue() 函数本来也可以用 LinkList 类成员函数的调用 ListInsert(ListLength()+1, e); 来实现在链表尾插入元素 e 。但对于单链表结构涞水，这样做效率不高，因而重写了 EnQueue() 函数（这也是增加子类私有数据成员 rear 的原因）。

3.2 队列的顺序存储结构

实现：

//顺序循环队列类
template<typename T>class SqQueueCy: public AQueue<T>
{//带模板并继承 AQueue 的顺序循环队列类
protected:
  T *base;
  int front;  
  int rear;
  int queuesize;
public:
  SqQueueCy(int k = 1)
  {//构造函数，动态生成具有 k 个初始存储空间的空队列
    base = new T[k];
    assert(base != NULL);
    front = rear = 0;
    queuesize = k;
  }
  ~SqQueueCy()
  {//析构函数
    delete[] base;
  }
  bool QueueEmpty()const
  {//若队列为空队列，则返回 true；否则返回 false
    return front == rear;
  }
  int QueueLength()const
  {//返回队列长度
    return (rear - front + queuesize) % queuesize;
    //+queuesize确保在rear<front时返回非负值，%queuesize确保返回值小于 queuesize
  }
  bool GetHead(T &e)const
  {//若队列不为空，则用 e 返回队头元素，并返回 true；否则返回 false
    if (front == rear)
      return false;
    e = *(base + front);
    return true;
  }
  bool EnQueue(T e)
  {//插入元素 e 为新的队尾元素，成功返回 true；否则返回 false
    T *newbase;
    int i;
    if ((rear + 1) % queuesize == front)
    {
      newbase = new T[queuesize * 2];
      if (newbase == NULL)
        return false;
      for(i = 0; i < queuesize - 1; i++)
        *(newbase + i) = *(base + (front + i) % queuesize);
      delte[] base;
      base = newbase;
      front = 0;
      rear = queuesize - 1;
      queuesize *= 2;
    }
    *(base + rear) = e;
    rear = ++rear % queuesize;
    return true;
  }
  bool DeQueue(T &e)
  {//若队列不空，则删除队头元素，用 e 返回其值，并返回 true；否则返回 false
    if (front == rear)
      return false;
    e = *(base + front);
    front = ++front % queuesize;
    return true;
  }
  void QueueTraverse(void(*visit) (T*))const
  {//从队头到队尾依次对队列中每个元素调用函数 visit()
    int i = front;
    while(i != rear)
    {
      visit(base + i);
      i = ++i % queuesize;
    } 
    cout << endl;
  }
};

顺序循环队列在队列满的时候，其实存储空间还有一个单元空着，如果把这个单元也用掉，会出现 “front == rear” 的情况，无法和队列空的情况相区别。所以循环队列的最大长度等于队列存储空间 - 1 。顺序循环队列利用求余构成队列的循环，可以重复使用元素出队后的存储空间，并且在队列满的情况下还可以扩充存储空间。

4. 队列的应用————排队和排队机的模拟

模拟排队和排队机需要两种数据结构：一种队列结构，模拟排队情况；另一种是优先队列，总是先处理（删除）按关键字排在最前面的时间。