數據結構學習（C++）——棧和隊列（定義和實現）

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

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

棧的定義和實現

#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

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

原文轉自：http://www.kjueaiud.com