文档介绍：数据结构学习(C++) 之栈和队列栈和队列是操作受限的线性表, 似乎每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现;但是很遗憾,本文没有这样做,所以,有些书中的做法是重复建设, 这或许可以用不是一个人写的这样的理由来开脱。顺序表示的栈和队列,必须预先分配空间,并且空间大小受限,使用起来限制比较多。而且, 由于限定存取位置, 顺序表示的随机存取的优点就没有了, 所以, 链式结构应该是首选。栈的定义和实现#ifndef Stack_H #define Stack_H #include "" 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 "" 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 "" void StackTest_int() { cout << endl << " 整型栈测试" << endl; cout << endl << " 构造一个空栈" << endl; Stack<int> a; cout << "将1~ 20 入栈,然后再出栈" << endl; for (int i= 1;i <= 20; i++) (i); while (!()) cout << () << ' '; cout << endl; } #endif #ifndef QueueTest_H #define QueueTest_H #include "" void QueueTest_int() { cout << endl << " 整型队列测试" << endl; cout << endl << " 构造一个空队列" << endl; Queue<int> a; cout << "将1~ 20 入队,然后再出队" << endl; for (int i= 1;i <= 20; i++) (i); while (!()) cout << () << ' '; cout << endl; } #endif 没什么好说的, 你可以清楚的看到, 在单链表的基础上, 栈和队列的实现是如此的简单。更多内容请看数据结构数据结构教程数据结构相关文章专题,或栈应用栈的应用很广泛, 栈的最大的用途是解决回溯问题, 这也包含了消解递归; 而当你用栈解决回溯问题成了习惯的时候, 你就很少想到用递归了, 比如迷宫求解。另外, 人的习惯也是先入为主的, 比如树的遍历, 从学的那天开始, 就是递归算法, 虽然书上也教了用栈实现的方法,但应用的时候,你首先想到的还是递归;当然了,假如语言本身不支持递归( 如 BASIC ) ,那栈就是唯一的选择了——似乎现在的高级语言都是支持递归的。如下是表达式类的定义和实现, 表达式可以是中缀表示也可以是后缀表示, 用头节点数据域里的 type 区分,这里有一点说明的是,由于单链表的赋值函数,我原来写的时候没有复制头节点的内容, 所以, 要是在两个表达式之间赋值, 头节点里存的信息就丢了。你可以改写单链表的赋值函数来解决这个隐患,或者你根本不不在两个表达式之间赋值也行。#ifndef EXPression_H #define Expression_H #include "" #inclu