当前页面位置: » 丰搜网 » 文档中心 » 详细内容
数据结构学习(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 |
没什么好说的，你可以清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单。
