C++数据结构学习:栈和队列[组图]
栈和队列是操作受限的线性表，似乎每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这
栈和队列是操作受限的线性表，似乎每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。
栈的定义和实现
#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
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
队列的定义和实现
#ifndef Queue_H
#define Queue_H
#include "List.h"
template class Queue : List//队列定义
{
public:
void EnQueue(const Type &value)
{
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
LastInsert(value);
}
Type DeQueue()
{
Type p = *GetNext();
RemoveAfter();
IsEmpty();
return p;
}
Type GetFront()
{
return *GetNext();
}
List ::MakeEmpty;
List ::IsEmpty;
};
#endif
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
测试程序
#ifndef StackTest_H
#define StackTest_H
#include "Stack.h"
void StackTest_int()
{
cout << endl << "整型栈测试" << endl;
cout << endl << "构造一个空栈" << endl;
Stack a;
![]()
![]()
![]()
![]()
<!-- frame contents -->
<!-- /frame contents -->
![]()
![]()
![]()
![]()
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
【后记】没什么好说的，你可以清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单，这也是我对于原书重复建设不满的最大原因。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
栈的定义和实现
#ifndef Stack_H
#define Stack_H
#include "List.h"
template
{
public:
void Push(Type value)
{
Insert(value);
}
Type Pop()
{
Type p = *GetNext();
RemoveAfter();
return p;
}
Type GetTop()
{
return *GetNext();
}
List
List
};
#endif
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
队列的定义和实现#ifndef Queue_H
#define Queue_H
#include "List.h"
template
{
public:
void EnQueue(const Type &value)
{
}
Type DeQueue()
{
Type p = *GetNext();
RemoveAfter();
IsEmpty();
return p;
}
Type GetFront()
{
return *GetNext();
}
List
List
};
#endif
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或
测试程序#ifndef StackTest_H
#define StackTest_H
#include "Stack.h"
void StackTest_int()
{
cout << endl << "整型栈测试" << endl;
cout << endl << "构造一个空栈" << endl;
Stack
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
cout << "将1～20入队，然后再出队" << endl;
for (int i = 1; i <= 20; i++) a.EnQueue(i);
while (!a.IsEmpty()) cout << a.DeQueue() << ' ';
cout << endl;
}
#endif
【后记】没什么好说的，你可以清楚的看到，在单链表的基础上，栈和队列的实现是如此的简单，这也是我对于原书重复建设不满的最大原因。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题，或精彩图集
精彩文章