目录
3.1 抽象数据类型（ADT）
抽象数据类型是带有一组操作的一些对象的集合。
3.2 表ADT
我们将处理形如A0, A1, A2, A3, ···, AN-1的一边的表。这个表的大小是N。我们将大小为0的特殊的表称为空表。
Ai后继Ai-1，Ai-1前驱Ai（i>0)。
元素Ai在表中的位置为i。
在表ADT上进行操作：
printList、makeEmpty
find:返回某一项首次出现的位置
insert和remove：从表的某个位置插入或删除某个元素
findKth：返回某个位置上的元素。
3.2.1 表的简单数组实现
3.2.2 简单链表
下图指出了链表的一般思路
链表由一系列节点组成，这些节点不必在内存中相连。每一个节点均含有表元素和一个链，该链指向包含该元素后继元的另一个节点。我们称之为next链。最后一个单元的nect链指向nullptr。
为了执行printList()或find（x），我们只要从表的第一个节点开始然后用一些后继的next链遍历该表即可。
remove方法可以通过修改一个next指针来实现。
insert方法需要使用new操作符从系统取得一个新节点，此后执行两次next指针的调整。
让每一个节点持有一个指向它在表中的前驱节点的链，称这样的表为双向链表。
3.3 STL中的vector和list
标准模板库STL：包含常用数据结构实现的库
表ADT有两种流行的实现方法。
vector提供表ADT的一种可增长的数组实现。优点是它是以常数时间可索引的。缺点是插入新项和删除现有项的代价高昂。
list提供表ADT的双向链表实现。优点是插入新项和删除现有项代价低廉。缺点是不容易被索引。
vector和list两者均为类模板，它们用其所存储的项的类型来实例化而成为具体的类。
两者有几个方法是共有的：
int size() const;//返回容器中元素的个数 void clear();//从容器中删除所有元素 bool empty() const;//若容器不含有元素则返回true，否则返回false
两者都支持以常数时间向表的尾端添加和从表的尾端删除的操作和以常数时间访问表的前端项：
void push_back(const Object& x);//把x添加到表的尾端 void pop_back();//删除位于表的尾端的对象 const Object& back() const;//返回位于表的尾端处的对象（还提供一个返回引用的修改函数） const Object& front() const;//返回位于表的前端处的对象（还提供一个返回引用的修改函数）
因为双向链表在其前端可以进行高效的改动，而vector不能，下列两个方法只能对list可用：
void push_front(const Object& x);//把x添加到表的前端 void pop_front();//删除位于表的前段处的对象
vector有它自己的方法集，这些方法list不具备：
Object& operator[](int idx);//返回vecotor中下标为idx的对象，不带界限检验（还提供一个返回常量引用的访问函数） Object& at(int idx);//返回vecotor中下标为idx的对象，带有界限检验（还提供一个返回常量引用的访问函数） int capacity() const;//返回vector的内部容量 void reserve(int newCapacity);//设置新的容量如果有好的估计可用，那么它可以用于避免扩展vector
3.3.1 迭代器
在STL中，位置由内嵌类型iterator表示。对于list<string>位置由类型list<string>: : iterator表示。
获取迭代器
iterator begin();//返回一个适当的迭代器，表示容器中的第一项 iterator end();//返回一个适当的迭代器，表示容器中的尾端（终端）标记（即容器中最后一项之后的位置）
end方法有些不同寻常，因为它返回一个“越界”的迭代器。
考虑下列用于打印vector v 中的项的代码
for(int i = 0; i != v.size(); ++i)
cout << v[i] << end1;
如果我们想使用迭代器重新改写这段代码，那么会看到一个与begin方法和end方法自然的对应
for(vector<int>::iterator itr = v.begin(); itr != end(); itr ???) //迭代器可以用!=或==比较
cout << itr.??? << end1;
在循环终止测试中，i != v.size()和itr != v.end()两者都要测试循环计数器是否“越界”。
其中???代表迭代器方法
迭代器方法
itr++； ++itr;//将迭代器推进到下一个位置 *itr;//返回对存储在迭代器itr的位置上对象的引用。所返回的引用可以允许修改，也可以不允许修改 itr1 == itr2;//若itr1和itr2指向同一个位置则返回true，否则返回false itr1 != itr2;//若itr1和itr2指向不同的位置则返回true，否则返回false
使用这些操作的打印代码将是
for(vector<int>::iterator itr = v.begin(); itr != v.end(); ++itr)
cout << *itr <<end1;
运算符重载的使用使我们能够访问当前项，此时使用*itr++可以推进到下一项。于是，上面的代码片段可以写成
vector<int>::iterator itr = v.begin();
while(itr != v.end())
cout << *itr++ <<end1;
需要迭代器的容器操作
从表的指定位置上进行添加或删除的操作
iterator insert(iterator pos, const Object& x);//把x添加到表中由迭代器pos所给定的位置之前的位置上。这是对list（但不是对vector）的常数时间的操作。返回值是指向被插入项的位置的一个迭代器。 iterator erase(iterator pos);//删除由迭代器所给定的位置上的对象。这是对list（但不是对vector）的常数时间的操作。返回值是调用之前pos的后继元素所在的位置 iterator erase(iterator start, iterator end);//删除从位置start开始直到（但不包括）位置end，为止的所有的项。整个表可以通过调用c.erase(c.begin(), c.end())而被删除。
3.3.2 例子：对表使用erase
template <typename Container>
void removeEveryOtherItem( Container & lst )
{
auto itr = lst.begin( ); //itr是一个Container::iterator
while( itr != lst.end( ) )
{
itr = lst.erase( itr );
if( itr != lst.end( ) )
++itr;
}
}
如果表包含6， 5， 1， 4， 2，那么在方法被调用之后，它将只包含5， 4。
第四行上的auto使我们避免使用更长的类型Container: :iterator。
3.3.3 const_iterators
*itr的结果不只是迭代器正在指向的项的值，而且还有该项本身。
假设我们想要把一个集合中的所有项改成一个特定的值。
template <typename Container, typename Obeject>
void change(Container& c, const Obeject& newValue)
{
typename Container::iterator itr = c.begin();
while(itr != c.end())
*itr++ = newValue;
}
假设Container c是使用常量引用调用被传递到例程的。这意味着我们不想对c做任何的改变，而编译器将通过禁止调用c的任何修改函数来保证这一点。考虑下列代码，它打印由一些整数构成的list而且还试图对list进行隐蔽的修改：
void print( const Container & c, ostream & out = cout )
{
typename Container::iterator itr = lst.begin();
while(itr != lst.end())
{
out << *itr << end1;
*itr = 0; //问题在此
++itr;
}
}
如果该段程序是合法的，那么list的定常性就将毫无意义，因为它太容易被绕开了。该程序段不合法，将不会被编译。
STL提供的解决方案是，每一个集合容器不仅包含一个内嵌类型iterator，而且还有一个内嵌类型的const_iterator。在iterator和const_iterator之间的主要区别在于，对于const_iterator，operator*返回一个常量引用，因此对于const_iterator的*itr不能出现在赋值语句的左边。
不仅如此，编译器还将要求我们使用cont_iterator来遍历一个常量集合。它通过提供两种版本的begin和两种版本的end来完成遍历：
iterator begin() const_iterator begin() const iterator end() const_iterator end() const
这两种形式的begin可以在同一个类中只是因为方法的定常性（是访问函数还是修改函数）被认为是特征的一部分。
如果是对非常量容器调用begin，那么返回一个iterator的“修改函数”版的begin被调用。
如果对常量容器调用begin，那么所返回的则是const_iterator，并且返回值不可赋给iterator。如果我们试图赋给它，那么将会产生一个编译错误。一旦itr是一个const_iterator类型的量，则*itr=0就会很容易地被检查出是非法的。
如果使用auto声明迭代器，则编译器将推算出它代替的是iterator还是const_iterator。
C++11一个附加的特性是，允许编写即使Container类型没有begin和end成员函数也能正常运行的程序。
非成员的自由函数begin和end的定义让我们在任何允许使用c.begin（）的地方使用begin(c)。使用begin(c)而不是使用c.gegin()编写泛型代码具有下列优点：
它使得泛型代码能够在有begin/end作为成员函数的容器上正常运行，而且对那些没有begin/end但以后可能用一些适当的非成员函数来扩充功能的容器也能正常运行。
template <typename Container>
auto begin(Container& c) -> decltype(c.begin))
{
return c.begin();
}
template <typename Container>
auto begin(const Container&c) ->decltype(c.begin())
{
return c.begin();
}
作为C++11中的自由函数，begin和end的加入通过添加语言特色auto和decltype而成为可能。
在这段代码中，begin的返回类型经推导是c.begin()的类型。
下面的程序利用auto来声明迭代器并用到了非成员函数begin和end
template <typename Container>
void print( const Container & c, ostream & out = cout )
{
if( c.empty( ) )
out << "(empty)";
else
{
auto itr = begin( c ); //itr是一个Container::const_iterator
out << "[ " << *itr++; // 打印第一项
while( itr != end( c ) )
out << ", " << *itr++;
out << " ]" << endl;
}
}
3.4 vector的实现
3.5 list的实现
在考虑设计时，我们需要提供如下4个类：
1、List类本身，它包含连接到表两端的链、表的大小，以及一些方法。
2、Node类，它很有可能是一个私有的内嵌类。一个节点包含数据和指向前后两个节点的两个指针，以及一些适当的构造函数。
3、const_iterator类，它抽象了位置的概念，而且是一个公有的内嵌类。存储一个指向“当前”节点的指针，并提供基本迭代器操作的实现，所有的操作，像=、==、！=和++等，均以重载运算符的形式出现。
4、iterator类，它抽象了位置的概念，而且是一个公有的内嵌类。有着与const_iterator相同的功能，但operator*返回的是所指项的引用，而不是对该项的常量引用。iterator可以用在任何需要const_iterator的例程中，但反之不真。换句话说，itr是一个const_iterator。
因为迭代器类存储一个指向“当前节点”的指针，并且终端标记是一个合法的位置，所以在表的终端创建一个表示终端标记的附加节点是有意义的。此外，还可以在表的前端创建一个附加节点，逻辑上代表开始标志。这些附加节点有时候称为标记节点；特别地，前端节点有时候也叫作头结点，而在尾端的节点有时候就叫作尾结点。
使用这些附加节点的好处在于，它们通过排除一些特殊情况大大地简化了编码过程。例如，如果我们不使用头结点，那么删除第一个节点就变成了一种特殊的情形，因为我们在删除期间必须重新安置链表对第一个节点的连接，还因为删除算法一般需要访问正在被删除的节点前面的节点（而没有头节点，则第一个节点就没有在它前面的节点）。
下面例程显示了List类的架构以及部分的实现
template <typename Obeject>
class List
{
private:
struct Node //struct中的成员默认是公有的，外界可以访问；但Node是私有的，外界不可访问
{
Object data;
Node *prev;
Node *next;
Node( const Object & d = Object{ }, Node * p = nullptr, Node * n = nullptr )
: data{ d }, prev{ p }, next{ n } { }
Node( Object && d, Node * p = nullptr, Node * n = nullptr )
: data{ std::move( d ) }, prev{ p }, next{ n } { }
};
public:
class const_iterator
{
public:
// Public constructor for const_iterator.
const_iterator( ) : current{ nullptr }
{ }
// Return the object stored at the current position.
// For const_iterator, this is an accessor with a
// const reference return type.
const Object & operator* ( ) const
{ return retrieve( ); } //retrieve见71行
const_iterator & operator++ ( ) //指定空参数，表示前缀++
{
current = current->next;
return *this;
}
const_iterator operator++ ( int ) //指定单参数，表示后缀++
{
const_iterator old = *this;
++( *this );
return old;
}
const_iterator & operator-- ( )
{
current = current->prev;
return *this;
}
const_iterator operator-- ( int )
{
const_iterator old = *this;
--( *this );
return old;
}
bool operator== ( const const_iterator & rhs ) const
{ return current == rhs.current; }
bool operator!= ( const const_iterator & rhs ) const
{ return !( *this == rhs ); }
protected: //标记为protected使得从const_iterator继承来的那些类有权访问这些成员，但不允许其他类有这种访问权
Node *current; //指向"当前“节点的指针
// Protected helper in const_iterator that returns the object
// stored at the current position. Can be called by all
// three versions of operator* without any type conversions.
Object & retrieve( ) const
{ return current->data; }
// Protected constructor for const_iterator.
// Expects a pointer that represents the current position.
const_iterator( Node *p ) : current{ p } //构造函数，protected并未给List对该构造函数的访问权，使用friend声明
{ }
friend class List<Object>; //使用friend声明，赋予List类访问const_iterator的非公有成员的权利
};
class iterator : public const_iterator //继承，iterator具有和const_iterator完全相同的功能，继承了const_iterator的所有数据和方法，并且可以用在任何需要const_iterator的地方。
{
public:
// Public constructor for iterator.
// Calls the base-class constructor.
// Must be provided because the private constructor
// is written; otherwise zero-parameter constructor
// would be disabled.
iterator( )
{ }
Object & operator* ( )
{ return const_iterator::retrieve( ); }
// Return the object stored at the current position.
// For iterator, there is an accessor with a
// const reference return type and a mutator with
// a reference return type. The accessor is shown first.
const Object & operator* ( ) const
{ return const_iterator::operator*( ); }
iterator & operator++ ( )
{
this->current = this->current->next;
return *this;
}
iterator operator++ ( int )
{
iterator old = *this;
++( *this );
return old;
}
iterator & operator-- ( )
{
this->current = this->current->prev;
return *this;
}
iterator operator-- ( int )
{
iterator old = *this;
--( *this );
return old;
}
protected:
// Protected constructor for iterator.
// Expects the current position.
iterator( Node *p ) : const_iterator{ p } //保护型构造函数用到一个初始化表列来初始化继承来的当前节点
{ }
friend class List<Object>;
};
public:
List( )
{ init( ); }
~List( ) //析构函数回收头节点和尾节点
{
clear( );
delete head;
delete tail;
}
List( const List & rhs )
{
init( );
for( auto & x : rhs )
push_back( x );
}
List & operator= ( const List & rhs )
{
List copy = rhs;
std::swap( *this, copy );
return *this;
}
List( List && rhs )
: theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
{
rhs.theSize = 0;
rhs.head = nullptr;
rhs.tail = nullptr;
}
List & operator= ( List && rhs )
{
std::swap( theSize, rhs.theSize );
std::swap( head, rhs.head );
std::swap( tail, rhs.tail );
return *this;
}
// Return iterator representing beginning of list.
// Mutator version is first, then accessor version.
iterator begin( )
{ return iterator( head->next ); } //返回一个构造的迭代器（iterator类和const_iterator类每个都有一个构造函数，该构造函数接受指向Node的指针作为它的参数）
const_iterator begin( ) const
{ return const_iterator( head->next ); }
// Return iterator representing endmarker of list.
// Mutator version is first, then accessor version.
iterator end( )
{ return iterator( tail ); }
const_iterator end( ) const
{ return const_iterator( tail ); }
// Return number of elements currently in the list.
int size( ) const
{ return theSize; }
// Return true if the list is empty, false otherwise.
bool empty( ) const
{ return size( ) == 0; }
void clear( ) //通过反复删除成员项直至List为空来完成清除工作。这种方式使得clear避免染指回收节点的工作，因为节点的回收已经归入pop_front处理
{
while( !empty( ) )
pop_front( );
}
// front, back, push_front, push_back, pop_front, and pop_back
// are the basic double-ended queue operations.
Object & front( )
{ return *begin( ); }
const Object & front( ) const
{ return *begin( ); }
Object & back( )
{ return *--end( ); }
const Object & back( ) const
{ return *--end( ); }
void push_front( const Object & x )
{ insert( begin( ), x ); }
void push_back( const Object & x ) //在表尾插入x，insert方法是在一个位置之前插入
{ insert( end( ), x ); }
void push_front( Object && x )
{ insert( begin( ), std::move( x ) ); }
void push_back( Object && x )
{ insert( end( ), std::move( x ) ); }
void pop_front( )
{ erase( begin( ) ); }
void pop_back( ) //删除表尾元素
{ erase( --end( ) ); }
// Insert x before itr.
iterator insert( iterator itr, const Object & x )
{
Node *p = itr.current;
++theSize;
return iterator( p->prev = p->prev->next = new Node{ x, p->prev, p } );
}
// Insert x before itr.
iterator insert( iterator itr, Object && x )
{
Node *p = itr.current;
++theSize;
return iterator( p->prev = p->prev->next = new Node{ std::move( x ), p->prev, p } );
}
// Erase item at itr.
iterator erase( iterator itr )
{
Node *p = itr.current;
iterator retVal( p->next );
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
--theSize;
return retVal;
}
iterator erase( iterator from, iterator to )
{
for( iterator itr = from; itr != to; )
itr = erase( itr );
return to;
}
private:
int theSize; //跟踪一个数据成员的大小，以便size方法能够以常数时间被实现。
Node *head; //指向头节点的指针
Node *tail; //指向尾节点的指针
void init( ) //创建一个空的List
{
theSize = 0;
head = new Node;
tail = new Node;
head->next = tail;
tail->prev = head;
}
};
下图阐释包含x的新节点是如何拼接到由p所指向的节点和节点p.prev之间的。对节点指针的赋值可以描述如下。
Node* newNode = new Node{x, p -> prev, p};//第1步和第2步
p -> prev -> next = newNode;//第3步
p -> prev = newNode;//第4步
可以将第3步和第4步合并，只得到如下两行
Node* newNode = new Node{x, p -> prev, p};//第1步和第2步
p -> prev = p -> prev -> next = newNode;//第3步和第4步
不过，此时这两行还可以合并，得到
p -> prev = p -> prev -> next = new Node{x, p -> prev, p};
这就缩短了下面的insert例程
// Insert x before itr.
iterator insert( iterator itr, const Object & x )
{
Node *p = itr.current;
theSize++;
return { p->prev = p->prev->next = new Node{ x, p->prev, p } };
}
// Insert x before itr.
iterator insert( iterator itr, Object && x )
{
Node *p = itr.current;
theSize++;
return { p->prev = p->prev->next = new Node{ std::move( x ), p->prev, p } };
}
下图显示删除一个节点的思路。如果p指向要被删除的节点，则只要改变两个指针就可以回收这个节点
p -> prev -> next = p -> next; p -> next -> prev = p -> prev; delete p;
下面显示的是一对erase例程。
// Erase item at itr.
iterator erase( iterator itr )
{
Node *p = itr.current;
iterator retVal{ p->next }; //代表被删除元素的后面的项
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;
theSize--;
return retVal;
}
iterator erase( iterator from, iterator to )
{
for( iterator itr = from; itr != to; )
itr = erase( itr ); //已经返回指向下一个位置的iterator,for循环不用再itr++
return to;
}
程序经过修订的受保护部分如下，此时对iterator和const_iterator构造函数的调用本来以前它们只需要一个参数，但现在都需要两个参数
const_iterator begin( ) const
{
const_iterator itr{ *this, head };
return ++itr;
}
const_iterator经修订后的受保护部分代码，添加了执行附加的错误检测的能力
protected:
const List<Object> *theList;
Node *current;
const_iterator( const List<Object> & lst, Node *p )
: theList{ &lst }, current{ p }
{
}
void assertIsValid( ) const
{
if( theList == nullptr || current == nullptr || current == theList->head )
throw IteratorOutOfBoundsException{ };
}
insert方法可以修改成下列代码
// Insert x before itr.
iterator insert( iterator itr, const Object & x )
{
itr.assertIsValid( );
if( itr.theList != this )
throw IteratorMismatchException{ };
Node *p = itr.current;
theSize++;
return { *this, p->prev = p->prev->next = new Node{ x, p->prev, p } };
}
3.6 栈ADT
栈是一个带有限制的表，它的插入和删除只能在一个位置上进行，即只能在表的末端进行，这个末端叫作栈顶。
3.6.1 栈模型
对栈的基本操作就是push（进栈）和 pop（出栈），前者等价于一次插入，而后者则是删除最近插入的元素。最近插入的元素在执行pop之前可以通过使用top例程进行考查。在栈ADT中，对空栈执行pop或top一般均被认为是一个错误。另一方面，执行push时空间用尽是一个实现限制，但不是ADT错误。
栈有时又叫作LIFO（后进先出）表（Last in，First out list）。下图描述的模型只表示push是输入操作而pop和top是输出操作。
下图展示了在进行若干操作后的一个抽象的栈。一般的模型是，存在某个元素位于栈顶，而该元素是唯一的可见元素。
3.6.2 栈的实现
由于栈是一个表，因此任何实现表的方法都能实现栈。显然，list 和 vector 都支持栈操作，99%的时间它们都是最合理的选择。偶尔设计一种特殊目的的实现可能会更快。因为栈操作是常数时间操作，所以，除非在非常独特的环境下，否则是不可能产生任何明显的改进的。
对于这些特殊的时机，我们将给出栈的两种流行的实现，一种实现使用链接结构，而另一种则使用数组，二者均简化了在vector和list中的思路，因此我们不提供代码。
栈的链表实现
栈的第一种实现是使用单链表。我们通过在表的前端插入来实施 push 操作，通过删除表前端元素实施pop操作。top操作只是考查表前端的元素并返回它的值。有时也把pop操作和top操作合二为一。
栈的数组实现
栈的另一种实现避免了链而且可能是更流行的解决方案。它用到来自vector的back、push_back 和 pop_back，因此实现起来很简单。与每个栈相关联的是 theArray 和topofStack，对于空栈topofStack是-1（这就是空栈的初始化做法）。为将某个元素x推入栈中，我们使 topofStack 增1然后置 theArray[topOfStack]=x。为了弹出栈元素，我们置返回值为 theArray[topofStack]，然后使 topofstack 减1。
注意，这些操作不仅以常数时间运行，而且是以非常快的常数时间运行。
3.6.3 应用
平衡符号
编译器检查程序的语法错误，但是常常由于缺少一个符号（如遗漏一个花括号或是注释起始符）而引起编译器列出上百行的诊断，可是真正的错误并没有找出。
在这种情况下一个有用的工具就是检验是否每件事情都能成对出现的程序。于是，每一个右花括号、右方括号及右圆括号必然对应其相应的左括号。序列[0]是合法的，但[ ( ] ）是错误的。为简单起见，我们仅就圆括号、方括号和花括号进行检验并忽略出现的任何其他字符。
这个简单的算法用到一个栈，兹叙述如下∶做一个空栈。读入字符直到文件尾。如果字符是一个开放符号，则将其推入栈中。如果字符是一个封闭符号，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开放符号，则报错。在文件尾，如果栈非空则报错。
它是线性的，事实上它只须对输入进行一趟检验。因此，它是联机（on-line）的，而且是相当快的。当报错时决定如何处理可能需要做一些附加的工作——例如判断可能的原因。
后缀表达式
假设我们有一个便携计算器并想要计算一趟外出购物的花费。为此，我们将一列数据相加并将结果乘以1.06，它是所购物品的价格以及附加的地方销售税。如果购物各项花销为4.99、5.99和6.99，那么输入这些数据的自然的方式将是
4.99＋5.99＋6.99*1.06=
随着计算器的不同，这个结果或者是所要的答案19.05，或者是科学答案18.39。最简单的四功能计算器都将给出第一个答案（默认前面三项先加最后计算乘法），但是许多先进的计算器是知道乘法的优先级高于加法的（先计算6.99*1.06）。
另一方面，有些项是需要上税的，而有些项则不是，因此，如果只有第一项和最后一项是要上税的，那么计算的顺序
4.99*1.06＋5.99＋6.99*1.06=
将在科学计算器上给出正确的答案（18.69）而在简单计算器上给出错误的答案（19.37）。科学计算器一般包含括号，因此我们总可以通过加括号的方法得到正确的答案，但是使用简单计算器时需要记住一些中间结果。
该例的典型计算顺序可以是将4.99和1.06相乘并存为A1，然后将5.99和A1相加，再将结果存入A1；我们再将6.99和1.06相乘并将答案存为A2，最后将A1和A2相加并将最后答案放入A1。可以将这种操作顺序书写如下∶
4.99 1.06 * 5.99＋6.991.06 *＋
这个记法叫作后缀记法（postfix notation）或逆波兰记法（reverse Polish notation），其求值过程恰好就是上面所描述的过程。计算这个问题最容易的方法是使用一个栈。当见到一个数时就把它推入栈中；在遇到一个运算符时该运算符就作用于从该栈弹出的两个数（符号）上，再将所得结果推入栈中。例如，后缀表达式
6523+8*+3+*计算如下∶
前4个字符放入栈中，此时栈变成
下面读到一个“+”号，所以3和2从栈中弹出并且它们的和5被压入栈中
接着，8进栈
现在见到一个“*”号，因此8和5弹出并且5*8=40进栈。
接下来又见到一个“+”号，因此40和5被弹出并且5+40=45进栈。
现在，将3压入栈中
然后，“+”使得3和45从栈中弹出并将45+3=48压入栈中。
最后，见到一个“*”号，从栈中弹出48和6；将结果6*48=299压进栈中。
计算一个后缀表达式花费的时间是O（N），因为对输入中的每个元素的处理都是由一些栈操作组成从而花费常数的时间。该算法的计算非常简单。注意，当一个表达式以后缀记号给出时，没有必要知道任何优先的规则（乘除和加减顺序无优先级）。这是一个明显的优点。
中缀到后缀的转换
可以用栈将一个标准形式的表达式（或叫作中缀式（infix））转换成后缀式（postfix）。我们通过只允许操作+、*、（、），并坚持普通的优先级法则而将一般的问题浓缩成小规模的问题。同时还要进一步假设表达式是合法的。设欲将中缀表达式
a+b*c+(d*e+f)*g
转换成后缀表达式。正确的答案是abc*+de*f+g*+。
当读到一个操作数的时候，立即把它放到输出中。但运算符并不立即输出，而是必须先存在某个地方。正确的做法是将已经见到的运算符放进栈中而不是放到输出中。当遇到左圆括号时也要将其推入栈中。计算从一个空栈开始。
如果见到一个右括号，那么就将栈元素弹出，将弹出的符号写出直至遇到一个（对应的）左括号为止，但是这个左括号只被弹出并不输出。
如果见到任何其他的符号，如+、*、（ ，那么我们从栈中弹出栈元素直到发现优先级更低的元素为止。有一个例外∶除非是在处理一个右括号）的时候，否则我们绝不从栈中移走左括号（。对于这种操作，+的优先级最低，而（的优先级最高。当从栈弹出元素的工作完成后，我们再将运算符压入栈中。
最后，如果读到输入的末尾，则将栈元素弹出直到该栈变成空栈，再将这些符号写到输出中。
这个算法的思路是，当看到一个运算符的时候，先把它放到栈中。栈代表挂起的运算符。然而，栈中有些具有高优先级的运算符现在知道需要完成使用，应该被弹出，它们将不再处于挂起的状态。这样，在把当前运算符放入栈中之前，那些在栈中并在当前操作符之前要完成使用的运算符要被弹出。详细的解释见下表∶
圆括号增加了额外的复杂性。当左括号是一个输入符号时可以把它看成是一个高优先级的运算符（这样，挂起的那些操作符仍是挂起的），而当它在栈中时把它看成是低优先级的运算符（因为高优先级会被弹出，看成低优先级不会被一个操作符意外地删除）。右括号被处理成特殊的情况。
我们将把上面长的中缀表达式转换成后缀形式。
首先，符号 a被读入，于是它被传向输出。然后，“+”被读入并被放入栈中。接下来b被读入并传向输出。这一时刻的状态如下∶
当前运算符优先级小于或等于栈顶运算符时，栈顶运算符弹出
这种转换工作只需要O（N）的时间并经过一趟输入后完成。可以通过指定减法和加法有相同的优先级以及乘法和除法有相同的优先级而将减法和除法添加到指令集中去。需要注意的是，表达式a-b-c应转换成ab-c-而不是转换成abc--。我们的算法做
函数调用
当存在函数调用的时候，需要存储的所有重要信息，诸如寄存器的值（对应一些变量的名字）和返回地址（它可从程序计数器得到，一般情况是在一个寄存器中）等，都要以抽象的方式存在“一张纸上”并被置于一个堆（pile）的顶部。然后控制转移到新函数，这样就可以自由地用它的一些值替换这些寄存器。如果它又进行其他的函数调用，那么也遵循相同的过程。当该函数要返回时，它查看堆（pile）顶部的那张"纸"并复原所有的寄存器，然后进行返回转移。
显然，全部工作均可由一个栈来完成，而这正是在实现递归的每一种程序设计语言中实际发生的事实。所存储的信息或称为活动记录（activation record），或叫作栈帧（stack frame）。在典型情况下，需要做轻微的调整∶当前环境由栈顶描述。因此，一条返回语句就可给出前面的环境（不用复制）。
在不进行栈溢出检测的语言和系统中，程序将会崩溃而没有明显的说明。在正常情况下我们不应该越出栈空间，发生这种情况通常是失控递归（忘记基准情形）产生的迹象。另一方面，某些完全合法并且表面上无害的程序也可以越出栈空间。图3.25中的例程打印一个容器，该例程完全合法，实际上是正确的。它正常地处理空容器的基准情形，并且递归也没问题。可以证明这个程序是正确的。然而遗憾的是，如果这个容器含有200000个元素要打印，那么就要有表示第11行上嵌套调用的200000个活动记录的一个栈。一般这些活动记录由于它们包含的全部信息而特别庞大，因此这个程序很可能要越出栈空间。（如果200000个元素还不足以使程序崩溃，那么可用更大的数代替它。）
这个程序是称为尾递归的使用极为不当的例子。尾递归指的是在最后一行进行的递归调用。尾递归可以手工消除，做法是通过将代码放到一个while循环体中并借助每次对函数参数的一次赋值代替递归调用。它模拟了递归调用，因为什么也不需要存储。在递归调用结束之后，实际上没有必要知道那些存储的值。因此，我们就可以带着在一次递归调用中本应用过的那些值转移到函数的顶部。图3.26中的函数显示该算法生成的、改进后的程序。尾递归的去除是如此简单，以至于某些编译器能够自动地完成。但是即使如此，最好还是不要让我们自己的程序带着尾递归。
递归总能够被彻底去除（编译器是在转变成汇编语言时完成递归去除的），但是这么做是相当冗长乏味的。一般做法是要求使用一个栈，而且仅当能够把最低限度的最小值放到栈上时这个方法才值得一用。我们将不对此做进一步的详细讨论，只是指出，虽然非递归程序一般说来确实比等价的递归程序要快，但是速度优势的代价却是由于去除递归而使得程序清晰性受到了影响。
3.7 队列ADT
像栈一样，队列（queue）也是一种表。然而，使用队列时插入在一端进行而删除则在另一端进行。
3.7.1 队列模型
队列的基本操作是 enqueue（入队），它是在表的末端（叫作队尾（rear））插入一个元素，以及 dequeue （出队），它是删除（并返回）在表的开头（叫作队头（front））的元素。图3.27显示了一个队列的抽象模型。
3.7.2 队列的数组实现
对于队列而言，任何表的实现都是合法的。对于每一种操作，链表实现和数组实现都给出快速的O（1）运行时间。下面讨论队列的数组实现。
对于每一个队列数据结构，我们保留一个数组 theArray 以及位置front 和back，它们代表队列的两端。我们还要记录实际存在于队列中的元素的个数currentSize。下图表示处于某个中间状态的一个队列。
为使一个元素x入队（即执行enqueue），我们让currentSize和back 增1，然后置 theArray [back]=x。若使一个元素 dequeue（出队），我们置返回值为thearray[front]，且currentSize减1，然后使front增1.
上述实现存在一个潜在的问题。经过10次 enqueue 后队列似乎是满了，因为back 现在是数组的最后一个下标，而下一次再 enqueue 就会是一个不存在的位置。然而，队列中也许只存在几个元素，因为若干元素可能已经出队了。像栈一样，即使在有许多操作的情况下队列也常常不是很大。
简单的解决方法是，只要front 或back 到达数组的尾端，它就又绕回到开头。下面诸图显示在某些操作期间的队列情况。这叫作循环数组（circular array）实现。
实施回绕所需要的附加代码是极小的（不过它可能使得运行时间加倍）。如果 front 或back 增1导致超越了数组，那么其值就要重置到数组的第一个位置。
有些程序设计员使用不同的方式表示队列的队头和队尾。例如，有人不使用一项来记录大小，因为他们依赖于当队列为空时back=front-1的基准情形。队列的大小通过比较back 和front 隐式地算出。这是一种非常隐秘的方法，因为存在某些特殊的情形，因此，如果想修改用这种方法编写的代码，那就要特别小心。如果 currentSize 不作为明确的数据成员被保留，那么当存在theArray.capacity（）-1个元素时队列就满了，因为只有theArray.capacity（）个不同的大小可被区分，而0又是其中的一个。由于实现方法有多种选择，因此如果不使用currentSize 这个数据成员，那就很可能有必要在代码中进行一些注释。
在确保 enqueue 的次数不会大于队列容量的应用中，使用回绕是没有必要的。除非主调例程肯定队列非空，否则 dequeue 很少执行。因此对这种操作，只要不是关键的代码，错误的检测常常被跳过。一般说来这并不是无可非议的，因为这样可能得到的时间节省量是极小的。
3.7.3 队列的应用
当作业送交给一台打印机的时候，它们就以到达的顺序被排列起来。因此，被送往打印机的作业基本上被放到一个队列中。
事实上，每一个实际生活中的排队都（应该）是一个队列。例如，在一些售票口排列的队伍都是队列，因为服务的顺序是先来到的先买票。
另一个例子是关于计算机网络的。有许多种PC的网络设置，其中磁盘是放在一台叫作文件服务器（file server）的机器上的。使用其他计算机的用户是按照先到先使用的原则访问文件的，因此其数据结构是一个队列。
进一步的例子如下∶
● 当所有的接线员忙不开的时候，对大公司的呼叫一般都被放到一个队列中。
● 在大型的大学里，如果所有的终端都被占用，由于资源有限，学生们必须在一个等待表上签字登记。在终端上待得时间最长的学生将首先被强制离开，而等待时间最长的学生则将是下一个被允许使用终端的用户。
称为排队论（queueing theory）的整个数学分支处理用概率的方法计算用户预计要排队等待多长时间才会得到服务、等待服务的队伍能够排多长，以及其他一些诸如此类的问题。问题的答案依赖于用户参与排队的频繁程度，以及一旦用户得到服务时处理服务花费的时间。这两个参数作为概率分布函数给出。在一些简单的情况下，答案可以解析地算出。一种简单情况的例子是一条电话线有一个接线员。如果接线员忙，打来的电话就被放到一个等待队列中（一直放到某个最大的限度为止）。这个问题在商业上很重要，因为研究表明，人们会很快挂上电话。
如果有k个接线员，那么这个问题解决起来要困难得多。解析求解困难的问题往往使用模拟的方法进行。此时，我们需要使用一个队列来进行模拟。如果k很大，那么还需要其他一些数据结构来使得模拟更有效地进行。在第6章将会看到这种模拟是如何进行的。那时我们将对k的若干值进行模拟并选择能够给出合理等待时间的最小的k。
队列还有其他丰富的用途，正如栈一样，这样一种简单的数据结构竟然能够如此重要，实在令人惊奇。
小结
本章描述了一些ADT的概念，并且利用3种最常见的抽象数据类型阐述了这种概念。主要目的就是将ADT的具体实现与它们的功能分开。程序必须知道操作都做些什么，但是如果不知道如何去做那就更好。
表、栈和队列或许在全部计算机科学中是3个基本的数据结构，大量的例子证明了它们广泛的用途。特别地，我们看到栈是如何用来记录函数调用的，以及递归实际上是如何实现的。这对于我们的理解非常重要，其原因不只因为它使得过程语言成为可能，而且还因为知道递归的实现从而消除了围绕其使用的大量迷团。虽然递归非常强大，但它并不是完全随意操作的，递归的误用和乱用可能导致程序崩溃。