首页 > 国家软考 > 第二课堂 > 程序员设计师 > 新闻

《数据结构(C++)》辅导系列：栈和队列

2007-5-11 15:08:28   Count:
 微软MCSE2003:Security  微软MCSE2003+MCDBA
 国家软考-网络工程师  华为认证网络工程师（HCNE）
 Adobe平面设计师(ACCD)  Adobe网络设计师（ACCD）
 国家信息化网络安全工程师  CEAC网络应用工程师
 CEAC微机装配与维护工程师  信息产业部数据恢复职业技术培训
 黑客系列：黑客攻防实战  瑞星病毒防范技能工程师
　　栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。
　　顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。
　　栈的定义和实现
　　#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
　　队列的定义和实现
　　#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
　　【后记】没什么好说的，你可以清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单，这也是我对于原书重复建设不满的最大原因。
浏览该文章的用户为您推荐了该信息: 
阅读该文章的用户同时也阅读了：
       
   
   
 
站内检索：
本月授课安排
栏目导航
阅读排行