数据结构学习（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.ltesting.net