《数据结构、算法与应用》 C++描述 -- 第8章 栈 学习笔记

定义：

栈（stack）是一种特殊的线性表，其插入（也称为入栈或压栈）和删除（也成为出栈或弹栈）操作都在表的同一端进行。这一端称为栈顶（top），另一端成为栈底（bottom）。可以使用前面实现过的基于数组和链表的线性表实现栈结构。在计算过程中经常使用。

现实中的应用：

• 打印机纸盘
• 自助餐厅的盘子等

抽象数据类型：

template
class stack 
{
   public:
      virtual ~stack() {}
      virtual bool empty() const = 0;
                  // return true if stack is empty
      virtual int size() const = 0;
                  // return number of elements in stack
      virtual T& top() = 0;
                  // return reference to the top element
      virtual void pop() = 0;
                  // remove the top element
      virtual void push(const T& theElement) = 0;
                  // insert theElement at the top of the stack
};

栈的插入和删除都被限制在一端进行，因此可以选择数组的左端或右端定义为栈顶。而数组尾端操作效率较高（从右端插入和删除不需要移动其他元素），可将右端定义为栈顶。

template
class derivedArrayStack : private arrayList, public stack
{
   public:
      derivedArrayStack(int initialCapacity = 10): arrayList (initialCapacity) {}
      bool empty() const{
					return arrayList::empty();
			}
      int size() const{
					return arrayList::size();
			}
      T& top(){
          if (arrayList::empty())
             throw stackEmpty();
          return get(arrayList::size() - 1);
      }
      void pop()
      {
         if (arrayList::empty())
            throw stackEmpty();
         erase(arrayList::size() - 1);
      }
      void push(const T& theElement)
      {insert(arrayList::size(), theElement);}
};

评论：

 虽然上述方法能很简单的实现栈，但会带来性能上的损失。例如当往栈中插入一个元素是，push方法会调用arrayList 的insert方法，插入元素前要对下标进行检查，可能要将数组加长，而且还要往回复制。但下标检查和往回复制都是不必要的，因为我们总是将新元素插到最右端。

因此，可用数组实现性能更好的栈。

template
class arrayStack : public stack
{
   public:
      arrayStack(int initialCapacity = 10);
      ~arrayStack() {delete [] stack;}
      bool empty() const {return stackTop == -1;}
      int size() const
          {return stackTop + 1;}
      T& top()
         {
            if (stackTop == -1)
               throw stackEmpty();
            return stack[stackTop];
         }
      void pop()
           {
              if (stackTop == -1)
                 throw stackEmpty();
              stack[stackTop--].~T();  // destructor for T
           }
      void push(const T& theElement);
   private:
      int stackTop;         // current top of stack
      int arrayLength;      // stack capacity
      T *stack;           // element array
};

template
arrayStack::arrayStack(int initialCapacity)
{// Constructor.
   if (initialCapacity < 1)
   {ostringstream s;
    s << "Initial capacity = " << initialCapacity << " Must be > 0";
    throw illegalParameterValue(s.str());
   }
   arrayLength = initialCapacity;
   stack = new T[arrayLength];
   stackTop = -1;
}

template
void arrayStack::push(const T& theElement)
{// Add theElement to stack.
   if (stackTop == arrayLength - 1)
      {// no space, double capacity
         changeLength1D(stack, arrayLength, 2 * arrayLength);
         arrayLength *= 2;
      }

   // add at stack top
   stack[++stackTop] = theElement;
}

同样的可以使用链表描述栈。使用左端作为栈顶的性能要优于使用右端作为栈顶。因此，将链表的左端作为栈顶。

linkedStack类实现：

template
class linkedStack : public stack
{
   public:
      linkedStack(int initialCapacity = 10)
            {stackTop = NULL; stackSize = 0;}
      ~linkedStack();
      bool empty() const
           {return stackSize == 0;}
      int size() const
          {return stackSize;}
      T& top()
         {
            if (stackSize == 0)
               throw stackEmpty();
            return stackTop->element;
         }
      void pop();
      void push(const T& theElement)
           {
              stackTop = new chainNode(theElement, stackTop);
              stackSize++;
           }
   private:
      chainNode* stackTop;  // pointer to stack top
      int stackSize;           // number of elements in stack
};

template
linkedStack::~linkedStack()
{// Destructor.
   while (stackTop != NULL)
   {// delete top node
      chainNode* nextNode = stackTop->next;
      delete stackTop;
      stackTop = nextNode;
   }
}

template
void linkedStack::pop()
{// Delete top element.
   if (stackSize == 0)
      throw stackEmpty();

   chainNode* nextNode = stackTop->next;
   delete stackTop;
   stackTop = nextNode;
   stackSize--;
}

数组描述的性能要好于链表描述的栈。

原因：

• 数组的空间分配是一组一组进行的；而链表的空间分配是一个节点一个节点进行的。
• 从占用内存空间上看：链表中每个节点还要保存指向下一个元素的指针，所需要分配的空间也相对更大。