在说什么是线性结构之前，我想还是先提前学习具体的结构，然后再一一总结为好。 栈（stack）应该是线性结构中容易的一种数据结构了，这种结构的主要操作有两种：将一个新的值添加到栈称为推送（push）该值; 删除堆栈中的顶层的值称为弹出（pop）栈。以后我们就直接用英文来表示了。在stack中这种的顺序处理方式我们通常称为LIFO，意思是后进先出。
栈的模型
我们用下面的模型来模拟栈的这个结构： 假设你在一个自助餐厅，客人在自助餐线上开始时拿起自己的盘子，那些盘子就放在弹簧柱上，这样子是为了方便顾客从自助餐线上拿起顶部的盘子，就像下图的模式那样：
当放碗机添加新的盘子时，它会放在堆叠的顶部，推动弹簧的压缩，其他的略微下降，如图所示：
对于顾客来说，他们只能从stack的顶部取走盘子，一旦当他们这么做之后，其余的盘子就会弹回原来的位置上去。因此，后加进来的盘子就是个被取走的盘子。 stack在编程中如此重要还有一个小原因，那就是嵌套函数（nested function）的调用形式就是以这种方式进行的。举个例子，如果main函数中我们调用f函数，那么一个f函数的栈框架就会放在main函数栈框架的顶部，就像这样：
如果f函数中还调用了g函数，那么就会在f的栈框架（stack frame）的上方为g函数开辟一个全新的栈框架。就像这样：
当g函数返回的时候，它的栈结构就会被pop回f函数中，同样的f函数也会pop会main函数中，终返回初始的模式。 所以总结起来就是：
调用顺序（入栈）：
main -> f()->g();
返回顺序（出栈）：
g() -> f() ->main;栈的基本操作
一般对栈的操作比较少，常见的有（这里的方法名是笔者自己所定，是在vs2015中，STL自带）：
我们也知道我们可以用上面的方法写一些常用的。很好用的函数。下面的是我自己写的一些好用的函数:
/*移除并返回栈顶的元素*/
int popAndReturn(stack<int> & operandStack) {
int n = operandStack.top();
operandStack.pop();
return n;
}
/*清空栈顶的元素*/
void clear(stack<int> & operandStack) {
while(!operandStack.empty()) {
operandStack.pop();
}
}
栈的实现
这篇文章的内容可能比较多（主要是代码）。我个人认为这些可实现的数据结构，一定要结合实际的代码来学习是佳的。 现在明确一点，我们的任务，是实现上述所说的数据结构，其接口中主要的方法有：
在编写这个类之前，我们新建一个空项目，空项目下需要建立下面五个文件（三个头文件，两个Cpp文件）：
error类
这里，error的目的是输出错误信息，类似于下面代码的作用：
cout << "错误信息" << endl;以后的代码不再贴此部分的详细内容：
- error.h代码
#ifndef _error_h
#define _error_h
#include <string>
/*
*函数:error
*用法: error("string")
*----------------------
*返回错误信息，并终止程序
*/
void error(std::string msg);
#endif
- error.cpp代码
#include <iostream>
#include <string>
#include <cstdlib> //EXIT_FAILURE
#include "error.h"
using namespace std;
void error(string msg) {
cerr << msg << endl;
exit(EXIT_FAILURE);
}
实现方法的选择
我们可以考虑用vector来实现charstack，因为这样的话我们不用考虑怎么删除元素，怎么为元素分配空间。但是更重要的是，依靠Vector类会让我们更难分析CharStack类的性能，因为Vector类隐藏了许多的复杂性(封装了很多细节)。因为我们目前还不知道Vector类是如何实现的，这就导致我们不知道在push和pop方法需要的情况下添加或删除元素涉及多少工作量。 接下来，我们要论的的主要目的是分析数据表示如何影响算法的效率。如果所有工作量都可见，那么这种分析就更容易。所以我们以后要用底层的东西来表示。
使用内置数组类型来存储元素的优点是数组不隐藏具体的细节。从数组中选择一个元素需要几个机器语言指令，在现代计算机上花费多少的时间还有在堆上分配数组存储或在不再需要时回收该存储通常的时间，这些操作都在在恒定时间运行。在典型的内存管理系统中，需要相同的时间来分配一个1000字节的块，就像分配一个10的块一样。 我们知道。对于数组来说，一旦为数组分配了空间，就无法改变它的大小。但是，我们可以做的是分配一些固定的初始大小的数组，然后只要旧的空间用尽，将其替换为全新的数组。在此过程中，你必须将所有元素从旧数组复制到新的数组，然后确保旧数组使用的内容被循环回到堆中。 下面先看看我们需要实现的功能有哪些：
charstack.h代码
/*
*这个文件定义了charstack类，它用来实现char类型的栈抽象
*/
#ifndef _charstack_h
#define _charstack_h
/*
*这个类模拟char型的栈，它的基本类型类似于
* stack <char>,我们现在用指定的基本类型去实现
*这些抽象的操作，然后我们可以利用前面的模板知识
*将这些转换为一般的模板
*/
class CharStack{
public：
/*
* 构造函数: CharStack
* 用法: CharStack cstk;
* ----------------------
* 初始化一个新的空栈，使其能够装下一系列的字符
*/
CharStack();
/*
* 析构函数: ~CharStack
* 用法: 常常隐式调用
* -------------------------
* 释放这个结构在堆中占用的空间
*/
~CharStack();
/*
* 方法: size
* 用法: int nElems = cstk.size();
* --------------------------------
* 返回栈中的字符数量
*/
int size();
/*
* 方法: getCapacity()
* 用法: int n = cstk.getCapacity();
* --------------------------------
* 返回栈中的容量
*/
int getCapacity();
/*
* 方法: isEmpty
* 用法: if (cstk.isEmpty()) . . .
* --------------------------------
* 当栈中没有字符元素的时候，返回true
*/
bool isEmpty();
/*
* 方法: clear
* 用法: cstk.clear();
* --------------------
* 移除栈中所有的元素
*/
void clear();
/*
* 方法: push
* 用法: cstk.push(ch);
* ---------------------
* 将一个元素压入栈中.
*/
void push(char ch);
/*
* 方法: pop
* 用法: char ch = cstk.pop();
* ----------------------------
* 移除栈顶元素并返回其值.
*/
char pop();
/*
* 方法: peek
* 用法: char ch = cstk.peek();
* -----------------------------
* 返回堆栈上的上面的值，而不删除它。
* 在空栈上调用查看会产生错误
*/
char peek();
#include "charstackpriv.h"
};
#endif
要存储堆栈元素，charstackpriv.h文件需要跟踪几个变量。
1. 它需要一个指向包含CharStack中所有字符的动态数组的指针。
2. 它需要跟踪已经为该数组分配了多少元素，以便实现可以判断何时耗尽空间，并需要重新分配其内部存储。由于该值表示数组在其当前配置中可以存储的字符数，因此通常称为动态数组的容量。
3. 后，重要的是，数组通常会包含比容量允许的更少的字符。因此，数据结构需要包括跟踪有效大小的变量。在私有部分中包含这三个实例变量，可以使用比数组操作更复杂的栈操作来实现。
charstackpriv.h文件的内容如图所示：
charstackpriv.h代码
private:
/* 实例化参数 */
char *array; /* 指向字符型的动态数组指针 */
int capacity; /* 为数组分配空间，也即是容量 */
int count; /* 当前被压入的栈中的元素个数 ，这里应该注意，count是从0开始算的*/
/*当count = 1的时候，压入栈的元素是位于位置0的，也就是说，count始终
是指向栈顶位置的上一位*/
/* 私有函数声明 */
void expandCapacity(); //扩展容量
我们实现的时候，注意构造函数必须初始化内部数据结构用来表示空栈。此时计数变量必须为零，必须提供具有初始容量的堆栈。在此例子中，构造函数通过为10个字符分配空间开始，INITIAL_CAPACITY的值是个常量。如果这个值选择较大值可以减少堆栈扩展的机会，从而节省执行时间; 决定用于INITIAL_CAPACITY的什么值是时间空间权衡（time-space tradeoff）的一个例子。以后还会介绍到。实现代码：
charstackImp.cpp代码
#include "charstack.h"
#include "error.h"
using namespace std;
/*常量*/
const int INITIAL_CAPACITY = 10;
/*构造函数和析构函数*/
CharStack::CharStack() {
capacity = INITIAL_CAPACITY; //设置初始容量
array = new char[capacity]; //动态分配字符栈
count = ; //一开始的时候，栈中没有元素
}
CharStack::~CharStack() {
delete[] array; //释放动态分配的空间
}
int CharStack::size() {
return count;
}
int CharStack::getCapacity(){
return capacity;
}
bool CharStack::isEmpty() {
return count == ;
}
void CharStack::clear() {
count = ; /*注意 这个时候我们只是把count的值赋值为0，但是实际的元素
*还在内存中，只是不在这个对象里面了，所以不是真正意义上的
*销毁
*/
}
void CharStack::push(char ch) {
if(count == capacity) expandCapacity(); //判断是否需要扩展容量再进行push操作
array[count] = ch; //因为count是从0开始计算的，所以不是count+1
count++; //栈中个数+1
}
char CharStack::pop() {
if (isEmpty()) error("pop: Attempting to pop an empty stack"); //不允许弹出空栈
return array[count - 1];
count--;
}
char CharStack::peek() {
if (isEmpty()) error("peek: Attempting to peek at an empty stack");
return array[count - 1]; //栈顶元素
}
void CharStack::expandCapacity(){
char *oldArray = array;
array = new char[capacity * 2];
for(int i = ; i < count; i++){
array[i] = oldArray[i];
}
delete[] oldArray;
}
重要代码的分析
- 对于push部分的代码
void CharStack::push(char ch) {
if(count == capacity) expandCapacity(); //判断是否需要扩展容量再进行push操作
array[count] = ch; //因为count是从0开始计算的，所以不是count+1
count++; //栈中个数+1
}
这里的先将ch的值赋值给array[count]，是因为count是表明栈中元素的个数的，从0开始算。假设一旦栈push个元素10，那么显然元素10对应的下标是0，而count对应的值为1.具体的结构如下：
所以，push的步骤是，先判断是否需要拓展容量，然后先将数据压入栈中，再将容量扩大。对照着这个，也不难理解pop代码了。
- 对于expandCapacity代码
void CharStack::expandCapacity(){
char *oldArray = array;
array = new char[capacity * 2];
for(int i = ; i < count; i++){
array[i] = oldArray[i];
}
delete[] oldArray;
}
从代码中可以看出，expandCapacity方法通过保存指向旧数组的指针开始。然后，它将分配一个新的数组，其容量是现有数组的两倍，将旧数组中的所有字符复制到新数组中，后释放旧数组存储.
测试代码
#include <iostream>
#include <string>
#include "charstack.h"
using namespace std;
int main(){
CharStack mystack;
for(int i = ; i < 5; i++){
char ch;
cin >> ch;
mystack.push(ch);
}
if(!mystack.isEmpty()) cout << "栈中的元素个数为" << mystack.size();
cout << endl;
char getElement = mystack.pop();
cout << "被移除的元素为：" << getElement << endl;
mystack.clear();
cout << "清空栈后，元素个数为：" << mystack.size() << endl;
cout << "此时的栈的容量为：" << mystack.getCapacity();
return ;
}
测试结果：
算法复杂度分析
在分析此类的性能时，重要的问题是每个操作的运行时间如何随着栈中的值数量的变化而变化。对于CharStack类，大多数方法运行常数。栈的大小会发生变化的方法是push方法，因为这种方法有时不得不扩大数组的容量。 到目前为止，我们的复杂性分析集中在坏情况下的表现。如果按push操作必须扩展栈的容量，则调用它时将以线性时间运行，因此在坏的情况下，似乎推算的计算复杂度必须为O（N）。 然而，有一个重要的特征使得push操作与传统复杂性分析中出现的其他操作不同：差的情况不可能每次发生。
比如，如果在栈上push一个元素并触发expandCapacity，使得该特定调用在O（N）时间内运行（扩展容量时候是O(N)），push下一个元素的时间 将保证为O（1），因为容量已经被扩展。这种复杂度测量的风格被称为平摊分析（amortized analysis）。
为了使此过程更容易理解，我们举个实际的例子。无论栈是否扩展，每次push操作都会产生一些代价。如果我们使用希腊字母α代表固定成本，则push N个项目的总固定成本为αN.然而，扩展内部数组的容量，这是一个线性时间操作（代码中的for循环），其花费了栈上字符数量的常数β倍。在总运行时间方面，糟糕的情况是如果在后一次使用时候发生扩张。在这种情况下，终的push操作会产生βN的额外成本。由于扩展容量总是使数组的大小增加一倍，当栈为N的一半大到N的1/4时，容量也必须扩大， 等等。
（如果上述例子不好理解，可以这样，假设要输入100个栈元素，那么次扩展需要扩展的元素为20，第二次为40，第三次为80，第四次为160.....，反过来，如果终栈的容量为N，那么说明前一次扩大时，扩大的容量是N/2,然后依次类推）因此，push N个项目的总成本由以下公式给出：
也就是说，平均时间为
这里，后面的求和是不可能大于2的（即平均时间< α + 2β），平均时间是常数，所以，此时平均复杂度为O（常数） = O（1）。
