数据结构学习（C++）之栈和队列

数据结构学习（C++）之栈和队列2008-01-05栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，本文没有这样做，所以，有些书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。

顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。

栈的定义和实现

#ifndef Stack_H
#define Stack_H
#include "List.h"
template <class Type> class Stack : List<Type>//栈类定义
{
 public:
  void Push（Type value）
  {
   Insert（value）;
  }
 Type Pop（）
 {
  Type p = *GetNext（）;
  RemoveAfter（）;
  return p;
 }
 Type GetTop（）
 {
  return *GetNext（）;
 }
 List<Type> ::MakeEmpty;
 List<Type> ::IsEmpty;
};
#endif

队列的定义和实现

#ifndef Queue_H
#define Queue_H
#include "List.h"
template <class Type> class Queue : List<Type>//队列定义
{
 public:
  void EnQueue（const Type &value）
  {
   LastInsert（value）;
  }
 Type DeQueue（）
 {
  Type p = *GetNext（）;
  RemoveAfter（）;
  IsEmpty（）;
  return p;
 }
 Type GetFront（）
 {
  return *GetNext（）;
 }
 List<Type> ::MakeEmpty;
 List<Type> ::IsEmpty;
};
#endif

测试程序