栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。 顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。 栈的定义和实现 #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 测试程序 #ifndef StackTest_H #define StackTest_H   #include "Stack.h"   void StackTest_int() {        cout << endl << "整型栈测试" << endl;        cout << endl << "构造一个空栈" << endl;        Stack<int> a;        cout << "将1～20入栈，然后再出栈" << endl;       for (int i = 1; i <= 20; i++) a.Push(i);        while (!a.IsEmpty()) cout << a.Pop() << ' ';        cout << endl; }   #endif   #ifndef QueueTest_H #define QueueTest_H   #include "Queue.h"   void QueueTest_int() {        cout << endl << "整型队列测试" << endl;        cout << endl << "构造一个空队列" << endl;        Queue<int> a;        cout << "将1～20入队，然后再出队" << endl;       for (int i = 1; i <= 20; i++) a.EnQueue(i);        while (!a.IsEmpty()) cout << a.DeQueue() << ' ';        cout << endl; }   #endif 【后记】没什么好说的，你可以清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单，这也是我对于原书重复建设不满的最大原因。

评论