棧和隊列(必備).doc

棧和隊列是操作受限的線性表，好像每本講數(shù)據(jù)結(jié)構(gòu)的數(shù)都是這么說的。有些書按照這個思路給出了定義和實現(xiàn)；但是很遺憾，這本書沒有這樣做，所以，原書中的做法是重復(fù)建設(shè)，這或許可以用不是一個人寫的這樣的理由來開脫。 順序表示的棧和隊列，必須預(yù)先分配空間，并且空間大小受限，使用起來限制比較多。而且，由于限定存取位置，順序表示的隨機存取的優(yōu)點就沒有了，所以，鏈?zhǔn)浇Y(jié)構(gòu)應(yīng)該是首選。 棧的定義和實現(xiàn) #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 隊列的定義和實現(xiàn) #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 構(gòu)造一個空棧 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 構(gòu)造一個空隊列 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