栈和队列(必备).doc

栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。 顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。 栈的定义和实现 #ifndef Stack_H #define Stack_H #include List.h template class Stack : List/栈类定义 public: void Push(Type value) Insert(value); Type Pop() Type p = *GetNext(); RemoveAfter(); return p; Type GetTop() return *GetNext(); List :MakeEmpty; List :IsEmpty; ; #endif 队列的定义和实现 #ifndef Queue_H #define Queue_H #include List.h template class Queue : List/队列定义 public: void EnQueue(const Type &value) LastInsert(value); Type DeQueue() Type p = *GetNext(); RemoveAfter(); IsEmpty(); return p; Type GetFront() return *GetNext(); List :MakeEmpty; List :IsEmpty; ; #endif 测试程序 #ifndef StackTest_H #define StackTest_H #include Stack.h void StackTest_int() cout endl 整型栈测试 endl; cout endl 构造一个空栈 endl; Stack a; cout 将120入栈，然后再出栈 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 a; cout 将120入队，然后再出队 endl; for (int i = 1; i = 20; i+) a.EnQueue(i); while (!a.IsEmpty() cout a.DeQueue() ; cout endl; #endi