首页 > > 程序设计 > C/C++ >

数据结构学习(C )之栈和队列

2008-02-23 05:25:14来源：互联网阅读 ()

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

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

　　栈的定义和实现

#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

　　没什么好说的，您能够清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单。