ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——栈和队列(定义和实现) (转)

数据结构学习(C++)——栈和队列(定义和实现) (转)

原创 IT综合 作者:amyz 时间:2007-11-09 16:54:49 0 删除 编辑
数据结构学习(C++)——栈和队列(定义和实现) (转)[@more@]

栈和队列是操作受限的线性表,好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现;但是很遗憾,这本书没有这样做,所以,原书中的做法是重复建设,这或许可以用不是一个人写的这样的理由来开脱。

顺序表示的栈和队列,必须预先分配空间,并且空间大小受限,使用起来限制比较多。而且,由于限定存取位置,顺序表示的随机存取的优点就没有了,所以,链式结构应该是首选。

栈的定义和实现

#ifndef Stack_HXML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

#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 << "将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

【后记】没什么好说的,你可以清楚的看到,在单链表的基础上,栈和队列的实现是如此的简单,这也是我对于原书重复建设不满的最大原因。


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-981484/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7362583