栈

理解桟的定义需要注意：首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

栈的应用

递归

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

递归过程退回的顺序是它前行顺序的逆序。显然这符合栈的存储方式。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压如栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切都由系统代劳就可以了。

例如：

long f(long m,long n)
{
    long sum;
    if(m==0) sum=n+1;
    else if(n==0) sum=f(m-1,1);
    else k=f(m-1,f(m,n-1));
return sum;
}

非递归：

long f(long m,long n)
{
  listStack<long> k;    //用链栈来实现
  k.push(m);
  k.push(n);
  long sum;
 while(k.length()!=1)  //栈中只有一个元素时退出循环
  {
      n=k.pop();      //出栈 
       m=k.pop();
      if(m==0) k.push(n+1);
      else if(n==0)
      {
        k.push(m-1);
        n=1;
        k.push(n);
      }
      else
      {
        k.push(m-1);
        k.push(m);
        k.push(n-1);

      }
  }
  sum=k.pop();  
return sum;
}

队列

注意，在大多数的课本中，队尾指向的是队列的最后一个元素的下一个元素。

“假溢出现象”：

在顺序存储结构中，队列的不断出队列会导致这些出去的元素的地址将无法使用（因为后续入队列的元素的地址将往后排）。

循环队列和链队列的优劣势

对于循环队列与链队列的比较，可以从两方面来考虑：

从时间上，其实它们的基本操作都是常数时间，即都为0(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。
对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，只是它在逻辑上把数组的头和尾相连，形成循环队列，当数组尾满的时候，要判断数组头是否为空，不为空继续存放数据，可以有效的利用资源。但是用循环队列有个小麻烦，不好判断数列是为空还是为满；

链队列就不存在上面的问题。“循环队列”最大优点就是节省空间和少分配空间，而链队列多了一点点地址存储开销。

矩阵

矩阵的压缩存储

按照我们正常的矩阵存储，其实对内存的空间开销还是比较大的，所以我们自然就想到了压缩存储。

那么什么是矩阵的压缩存储？其实就是为很多个值相同的元素只分配一个存储空间。对零元素不分配存储空间。那么这个值相同的元素，我们很容易就想到了线性代数的特殊矩阵，比如单位阵，对角阵，对称阵等，我们这里说三个。分别是对称矩阵、上下三角矩阵、和对角矩阵。

对称矩阵：

就是矩阵的行和列对调之后还是和原来的矩阵相等。那么这种矩阵就是对称矩阵。

ok，我们知道了对称矩阵的特性，所以要运用要压缩存储上，因为对称矩阵有这样的特性，所以我们存储的时候就不用将元素全部存储，我们只需要存储这个镜面一半的元素就可以了。比如上面这个，我们只存158234这些元素即可，相同的元素不要重复存储。

稀疏矩阵：

其实就是说矩阵中的元素为0的特别多。

那么我们再存储的时候其实存储分零元素是最能节省空间的。但是稀疏矩阵的位置又没有前面哪些矩阵的规律，所以我们存储的时候就干脆把元素的行列下标也存进去。形成一个三元组。也就是行下标、列下标、元素值。

注意三元组的存储方式牺牲了随机存储的优点。

rhb_blog

数据结构-栈和队列

栈

栈的应用

递归

队列

循环队列和链队列的优劣势

矩阵

矩阵的压缩存储