本博文中引入的：

一　栈

  栈是限定仅在一端进行插入或者删除操作的线性表，例如可利用空间表就是一个栈。

一些术语：

  • 栈顶元素-栈的可访问元素。
  • 入栈-元素插入栈。
  • 出栈-删除栈中的元素。
单击此处查看栈的抽象类声明

  下面是从教材中摘录的栈的抽象类声明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Stack abtract class
template <typename E> class Stack {
private:
  void operator =(const Stack&) {}     // Protect assignment
  Stack(const Stack&) {}         // Protect copy constructor

public:
  Stack() {}                       // Default constructor
  virtual ~Stack() {}              // Base destructor

  // Reinitialize the stack.  The user is responsible for
  // reclaiming the storage used by the stack elements.
  virtual void clear() = 0;

  // Push an element onto the top of the stack.
  // it: The element being pushed onto the stack.
  virtual void push(const E& it) = 0;

  // Remove the element at the top of the stack.
  // Return: The element at the top of the stack.
  virtual E pop() = 0;

  // Return: A copy of the top element.
  virtual const E& topValue() const = 0;

  // Return: The number of elements in the stack.
  virtual int length() const = 0;
};

（一）顺序栈

  顺序栈的实现是顺序表实现的简化。在建立栈时必须首先说明一个固定长度。当前位置总是在栈顶（即表尾）。

单击此处查看顺序栈的实现

  下面是从教材中摘录的顺序栈的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// This is the file to include in your code if you want access to the
// complete AStack template class

// First, get the declaration for the base stack class
#include "stack.h"

// This is the declaration for AStack.
// Array-based stack implementation
template <typename E> class AStack: public Stack<E> {
private:
  int maxSize;              // Maximum size of stack
  int top;                  // Index for top element
  E *listArray;          // Array holding stack elements

public:
  AStack(int size =defaultSize)   // Constructor
    { maxSize = size; top = 0; listArray = new E[size]; }

  ~AStack() { delete [] listArray; }  // Destructor

  void clear() { top = 0; }           // Reinitialize

  void push(const E& it) {         // Put "it" on stack
    Assert(top != maxSize, "Stack is full");
    listArray[top++] = it;
  }

  E pop() {                // Pop top element
    Assert(top != 0, "Stack is empty");
    return listArray[--top];
  }

  const E& topValue() const {     // Return top element
    Assert(top != 0, "Stack is empty");
    return listArray[top-1];
  }

  int length() const { return top; }  // Return length
};

（二）链式栈

  链式栈的实现是链表实现的简化，例如可利用空间表。

单击此处查看链式栈的实现

  下面是从教材中摘录的链式栈的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// This is the file to include in your code if you want access to the
// complete LStack template class

// Include the link class
#include "link.h"

// First, get the declaration for the base stack class
#include "stack.h"

// This is the declaration for LStack.
// Linked stack implementation
template <typename E> class LStack: public Stack<E> {
private:
  Link<E>* top;            // Pointer to first element
  int size;                   // Number of elements

public:
  LStack(int sz =defaultSize) // Constructor
    { top = NULL; size = 0; }

  ~LStack() { clear(); }          // Destructor

  void clear() {                  // Reinitialize
    while (top != NULL) {         // Delete link nodes
      Link<E>* temp = top;
      top = top->next;
      delete temp;
    }
    size = 0;
  }

  void push(const E& it) { // Put "it" on stack
    top = new Link<E>(it, top);
    size++;
  }

  E pop() {                // Remove "it" from stack
    Assert(top != NULL, "Stack is empty");
    E it = top->element;
    Link<E>* ltemp = top->next;
    delete top;
    top = ltemp;
    size--;
    return it;
  }

  const E& topValue() const { // Return top value
    Assert(top != 0, "Stack is empty");
    return top->element;
  }

  int length() const { return size; } // Return length
};

  与链表不同的是，链式栈不需要表头结点，这是因为链表为空表或当前位置在链表末端时，没有元素可供指针head tail curr指向，因而需要添加表头结点供其指向；注意到在栈中并没有这样的指针，它的栈顶通过索引整型变量top来访问，因此不需要表头结点。

（三）顺序栈和链式栈的比较

  实现顺序栈和链式栈的所有操作都只需要常数时间，因此它们的时间效率接近。在空间效率方面来看，和顺序表与链表的比较类似，顺序栈需要首先明确长度，因而造成空间浪费；而链式栈的长度可变，但是带来了结构性开销。
  当需要实现多个栈时，对顺序栈做如下优化，可以减少它的空间浪费：使用一个数组来存储两个栈，每个栈从各自的端点向中间延伸。但是，它有一个重要的使用条件：这两个栈的空间需求有相反的关系，也就是说，最好是一个栈增长时另一个栈缩短。尤其是当需要从一个栈中取出元素放入另一个栈中时。

（四）栈的应用——递归

  递归的核心思想就是重复将问题分解为同类的子问题，反映到程序中就是重复调用子程序。子程序调用是通过把有关子程序的必要信息（包括返回地址、参数、局部变量）存储到一个栈中实现的，这块信息称为活动记录；子程序调用再把活动记录压入栈。每次从子程序中返回时，就从栈中弹出一个活动记录。例如阶乘函数：

1
2
3
4
5
6
long fact(int n) {       // Compute n! recursively
  // To fit n! into a long variable, we require n <= 12
  Assert((n >= 0) && (n <= 12), "Input out of range");
  if (n <= 1)  return 1; // Base case: return base solution
  return n * fact(n-1);  // Recursive call for n > 1
}

  使用4来调用该函数，那么它在栈中的流程如图F1所示。其中，β\beta表示程序调用fact的指令所在的地址。注意到，在第一次调用时，必须把地址β\beta存放入栈，并且把4传递给函数。接下来再一次调用时，注意函数的返回值是n∗fact(n−1)n * fact(n-1)，因此nn的当前值4连同需要将这次调用的指令地址β1\beta_1一同保存入栈，并且把3传递给函数。此后过程类似。返回时，将每一活动记录弹出栈并相乘，逐次累积。
F1.递归函数在栈中的实现流程示例
  这样的过程经常需要耗费大量的时间和空间，因此某些时候（但不总是）用迭代来代替递归。

二　队列

  队列是限定元素只能从队尾插入的线性表。

一些术语：

  • 入队-从队尾插入元素。
  • 出队-从队首删除元素。
单击此处查看队列的抽象类声明

  下面是从教材中摘录的队列的抽象类声明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// Abstract queue class
template <typename E> class Queue {
private:
  void operator =(const Queue&) {}     // Protect assignment
  Queue(const Queue&) {}         // Protect copy constructor

public:
  Queue() {}          // Default
  virtual ~Queue() {} // Base destructor

  // Reinitialize the queue.  The user is responsible for
  // reclaiming the storage used by the queue elements.
  virtual void clear() = 0;

  // Place an element at the rear of the queue.
  // it: The element being enqueued.
  virtual void enqueue(const E&) = 0;

  // Remove and return element at the front of the queue.
  // Return: The element at the front of the queue.
  virtual E dequeue() = 0;

  // Return: A copy of the front element.
  virtual const E& frontValue() const = 0;

  // Return: The number of elements in the queue.
  virtual int length() const = 0;
};

（一）顺序队列

  由于顺序队列的顺序性，如果仅仅是简单地变化顺序表，执行出队/入队操作的效率总是不尽人意，因为无论如何排列，总是有出队/入队操作之一需要将原本的元素全部移动一位。这样的问题可以通过移动队列来解决，也就是说在出队时，其他元素都不移动，放宽了队列的所有元素都必须处于数组前n个位置的条件，入队时仍然将元素添加至队尾，然而这很容易造成数组中靠后的空间耗尽。实际上，如果数组是循环的，那么这个问题就迎刃而解了，如图F2所示。
F2.使用循环数组实现顺序队列示例
  如果数组的长度是size，那么数组的位置索引从0至size-1，并且size-1的位置被定义为位置0（等价于位置size%size)的前驱。

如何判断循环数组是空的还是满的？
  如果我们用下面的策略来判断：

  • 空队列判定-rear表示的位置是front表示位置的前驱（rear和front表示的位置相同时，表示有且仅有1个元素）；
  • 满队列判定-rear表示的位置是front表示位置的前驱（rear位于size-1的位置，front位于0的位置）。

  注意到，仅凭rear和front的位置无法判断队列空/满。一个很直接的办法是新定义一个成员变量记录元素个数（或者至少有一个布尔变量指示队列是否为空）；还有另一个办法被教材选用，就是将数组的大小设置为n+1，但只允许存储至多n个元素。后者的实现办法如下。

单击此处查看顺序队列的实现

  下面是从教材中摘录的顺序队列的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// This is the file to include in your code if you want access to the
// complete AQueue template class

// First, get the declaration for the base stack class
#include "queue.h"

// This is the declaration for AStack.
// Array-based queue implementation
template <typename E> class AQueue: public Queue<E> {
private:
  int maxSize;               // Maximum size of queue
  int front;                 // Index of front element
  int rear;                  // Index of rear element
  E *listArray;           // Array holding queue elements

public:
  AQueue(int size =defaultSize) {  // Constructor 
    // Make list array one position larger for empty slot
    maxSize = size+1;
    rear = 0;  front = 1;
    listArray = new E[maxSize];
  }

  ~AQueue() { delete [] listArray; } // Destructor

  void clear() { rear = 0; front = 1; } // Reinitialize

  void enqueue(const E& it) {     // Put "it" in queue
    Assert(((rear+2) % maxSize) != front, "Queue is full");
    rear = (rear+1) % maxSize;       // Circular increment
    listArray[rear] = it;
  }

  E dequeue() {           // Take element out
    Assert(length() != 0, "Queue is empty");
    E it = listArray[front];
    front = (front+1) % maxSize;    // Circular increment
    return it;
  }

  const E& frontValue() const {  // Get front value
    Assert(length() != 0, "Queue is empty");
    return listArray[front];
  }

  virtual int length() const         // Return length
   { return ((rear+maxSize) - front + 1) % maxSize; }
};

（二）链式队列

  与顺序队列不同，链式队列不具有顺序性，因而在链表的基础上只需进行简单的变化。它与链式栈不同——链式栈只需要在栈顶执行入栈/出栈操作，对特殊情况（例如空队列）执行入栈/出栈操作时，只需要改变top指针即可，top指针所指的结点的data域是入栈元素，next域是原来的栈顶元素。

  在实现链式队列时，使用头结点可以简化实现方式和对特殊情况（例如空队列）的操作，这是因为链式队列需要对队首和队尾进行操作。以向空队列插入元素为例：

  • 如果不使用头结点，那么在首次入队时，需要判空，并且改变front和rear指针指向新插入的元素，此后插入元素便在rear指针后加入元素并改变rear指针；
  • 如果使用头结点（初始化时，front和rear指针都指向头结点），那么无论是否时首次入队，都不需要判空，只需要在rear指针后加入元素并改变rear指针。

  实际上，top指针和rear指针是很相似的，对于插入元素而言，前者是在指针前插入元素并改变指针，后者是在指针后插入元素并改变指针。头结点在这里只是优化了front结点的相关操作。

单击此处查看链式队列的实现

  下面是从教材中摘录的链式队列的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// This is the file to include in your code if you want access to the
// complete LQueue template class

// Include the link class
#include "link.h"

// First, get the declaration for the base stack class
#include "queue.h"

// Implementations for linked queue function members
// Linked queue implementation
template <typename E> class LQueue: public Queue<E> {
private:
  Link<E>* front;       // Pointer to front queue node
  Link<E>* rear;        // Pointer to rear queue node
  int size;                // Number of elements in queue

public:
  LQueue(int sz =defaultSize) // Constructor 
    { front = rear = new Link<E>(); size = 0; }

  ~LQueue() { clear(); delete front; }      // Destructor

  void clear() {           // Clear queue
    while(front->next != NULL) { // Delete each link node
      rear = front;
      delete rear;
    }
    rear = front;
    size = 0;
  }

  void enqueue(const E& it) { // Put element on rear
    rear->next = new Link<E>(it, NULL);
    rear = rear->next;
    size++;
  }

  E dequeue() {              // Remove element from front
    Assert(size != 0, "Queue is empty");
    E it = front->next->element;  // Store dequeued value
    Link<E>* ltemp = front->next; // Hold dequeued link
    front->next = ltemp->next;       // Advance front
    if (rear == ltemp) rear = front; // Dequeue last element
    delete ltemp;                    // Delete link
    size --;
    return it;                       // Return element value
  }

  const E& frontValue() const { // Get front element
    Assert(size != 0, "Queue is empty");
    return front->next->element;
  }

  virtual int length() const { return size; }
};

（三）顺序队列和链式队列的比较

  实现顺序队列和链式队列的所有操作都只需要常数时间，因此它们的时间效率接近。在空间效率方面，它们和顺序栈与链式栈的比较是相似的，不过顺序队列不能在一个数组中存储两个队列，除非二者数据项从一个队列转入另一个队列。