C++數據結構學習:棧和隊列

2019-11-17 05:04:01

字體：大中小

來源：轉載

供稿：網友

　　棧和隊列是操作受限的線性表，似乎每本講數據結構的數都是這么說的。有些書按照這個思路給出了定義和實現；但是很遺憾，這本書沒有這樣做，所以，原書中的做法是重復建設，這或許可以用不是一個人寫的這樣的理由來開脫。

　　順序表示的棧和隊列，必須預先分配空間，并且空間大小受限，使用起來限制比較多。而且，由于限定存取位置，順序表示的隨機存取的優點就沒有了，所以，鏈式結構應該是首選。

　　棧的定義和實現
　　#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

更多內容請看C/C++技術專題數據結構數據結構教程專題，或　　隊列的定義和實現
　　#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

更多內容請看C/C++技術專題數據結構數據結構教程專題，或　　測試程序
　　#ifndef StackTest_H
　　#define StackTest_H
　　#include "Stack.h"
　　void StackTest_int()
　　{
　　cout << endl << "整型棧測試" << endl;
　　cout << endl << "構造一個空棧" << endl;
　　Stack 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 a;
　　cout << "將1～20入隊，然后再出隊" << endl;
　　for (int i = 1; i <= 20; i++) a.EnQueue(i);
　　while (!a.IsEmpty()) cout << a.DeQueue() << ' ';
　　cout << endl;
　　}
　　#endif

　　【后記】沒什么好說的，你可以清楚的看到，在單鏈表的基礎上，棧和隊列的實現是如此的簡單，這也是我對于原書重復建設不滿的最大原因。

更多內容請看C/C++技術專題數據結構數據結構教程專題，或

上一篇：C語言中的面向對象(3)－類模擬的性能分析

下一篇：C++數據結構學習:用棧做表達式求值