堆栈实现先进先出队列

实现思路：
        使用两个大小相同的堆栈（命名为s1,s2），来实现堆栈。队列包含一下几个操作：创建、注销、满判断、空判断、入队、出队。

创建：
       创建管理结构体，结构体包含队列容量、使用量、包含两个栈指针的数组。使用另外的库函数来创建堆栈。两个栈的大小和队列的容量相同。

注销：
       顺序注销两个栈，以及管理结构体。

满判断：
空判断：
       根据管理结构体中存储的容量和使用量来判断。

入队：
        首先使用前面的函数判断队列是否满，满则出错。将数据压入栈s1，并增加使用量计数。

出队：
        首先判断队列是否为空，空则出错。判断s2栈是否为空，空则将s1栈内容出栈，入栈到s2，s1的最后一个元素直接返回给函数调用者，不入栈；s2栈非空，则直接从s2中返回一个元素给函数调用者。返回元素要较少使用量计数。


代码实现见github(https://github.com/zhangst/exercise/tree/master/interview/fifo)，这种实现还有一个问题，空间浪费。创建一个容量为16的队列，需要两个容量为16的堆栈才能实现，总空间占用为32了。

linux gcc alignment 字节对齐

为什么对齐：
     方便CPU更快速的读取内存数据，Intel CPU也可以识别不对齐的元素，但效率会慢；而RSIC ARM 不能正确识别未正确对齐的变量
     变量对齐并不是C语言定义的，全由编译器根据当前平台的特性确定，所以不能直接确定某个struct的对齐情况。

三个前提：
    struct可以在元素之间和结尾添加填充字节
    数组内元素之间是不能添加填充字节
    可以创建struct类型的数组，要保证数据第二个元素也对齐

结构体不指定__attribute__((aligned()))属性：
       内置类型以自己的长度作为对齐条件，如 short 2字节对齐，int 4字节对齐；这些类型作为struct内元素时，会影响struct的对齐。
       struct内元素按自己的自身长度对齐，struct以最严格的元素的方式对齐（根据CPU字长看）
               32位PC，字长4字节，结构体内有元素大于4字节时，struct也以4字节对齐
               64位PC，字长8字节，struct内元素有大于等于8字节的元素时，struct以8字节对齐

结构体指定 type attribute __attribute__ ((aligned))属性：
        属性是对编译器的建议，编译器会尽量达成
        __attribute__ ((aligned(4)));   建议编译器此结构体以4字节对齐
        __attribute__ ((aligned));        建议编译器使用对此平台maximum useful alignment,有点扯，我平台测试的和手册结果居然不一样
        aligned 指定的长度也会受linker的限制，有些linker有自己的最大对齐值


参考资料：
http://stackoverflow.com/questions/364483/determining-the-alignment-of-c-c-structures-in-relation-to-its-members
http://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/Type-Attributes.html#Type-Attributes

学车记

      考完科目一，上周办完上车手续，这周总算是上车了。接下来的是连续4周，八个半天的高强度练习，希望自己可以顺利通过考试，拿到驾照。
        我选的是周末直通车，比计时班略贵，上车之前，所有直通车的学院被教练队长叫到办公室，做了40分钟的思想教育，主旨是要和教练和平共处，换位思考，理解教练。教育完后，上车，本以为马上可以开始学习了，结果坐在车里又被教练教育了30分钟，汗。直通车不同于计时班，从开始到结尾，始终是那一个教练教你。人与人之间的初次相处，保持克制相互友好是比较容易的，但是长时间的睦邻友好就不容易了，容易产生矛盾，我觉得这是队长和师傅说教的原因。

        今天主要是主要学习了换挡、离合等的使用，缓慢匀速的前进、倒车，控制车和几个杆的距离，其中最为难是缓慢匀速的前进，必须很熟练的控制离合的力度，动作太大容易熄火，很不易控制。对于贴库、移库教练给了各种口诀，一会需要背诵。
       驾校真是繁忙，学驾照的人真是多，驾校早上、下午、晚上三个时段，每次班车都拉来满满的一车人。教练一天要工作11个小时，风吹日晒，甚是辛苦啊。
     

2009.12.16-2012.4.13

    网御工作两年多，今天是最后一个工作日，这样无声无息的结束了。两年多来付出很多，收获很多。

    中午请几个老同事在祖母的菜馆吃饭，聊了聊，希望以后还能够再见到大家。

linux shell中的管道执行

linux shell中管道发挥的作用是文件描述符重定向，例如 prog1 | prog2 | prog3，管道会将prog1的标准输出重定向为prog2的标准输入，将prog2的标准输出重定向为prog3的标准输入，prog1的标准输入和prog3的标准输出并没有改变。比如命令"ps -ef | grep -w "nginx""将ps命令的标准输出内容作为grep的输入，两个命令的组合的只输出关于nginx进程的信息。

这里归档两个平时没有想明白的问题：

1、shell管道中程序按什么顺序执行？进程关系是什么样子？
当前有很多的shell程序，实现各不同，有的支持作业控制，代表有：bash(bourne again shell)，有的不支持，代表有bourne shell。

prog1 | prog2 | prog3

1）在不支持作业控制shell中，prog3是shell的子进程，而prog1和prog2为prog3的子进程。执行如下图所示

 

（摘自APUE）

 2）对于支持作业控制的shell，prog1、prog2、prog3都为shell的子进程，在bash中的执行顺序为 prog1、prog2、prog3，具体和shell的实现有关。

[root@zhangst ~]# uname -a
Linux zhangst.F14 2.6.35.6-45.fc14.i686 #1 SMP Mon Oct 18 23:56:17 UTC 2010 i686 i686 i386 GNU/Linux
[root@zhangst ~]# ps -o pid,ppid,pgid,session,tpgid,tty,comm | cat | grep -v "*"
  PID  PPID  PGID  SESS  TPGID TT       COMMAND
 2667  2664  2667  2667  2689 pts/0    bash
 2689  2667  2689  2667  2689 pts/0    ps
 2690  2667  2689  2667  2689 pts/0    cat
 2691  2667  2689  2667  2689 pts/0    grep

上面的例子中ps、cat、grep三个进程都为bash的子进程，ps进程最先执行，并且三个进程在一个进程组中，ps为组长进程，这个组为前台进程组（TPGID），而bash为后台进程。


2、如何判断管道中程序是否成功执行？某个程序执行失败是否影响其它程序的执行？

1）shell中有一个变量数组PIPESTATUS，保存了上一个执行管道的状态。
echo ${PIPESTATUS[*]}；就可以输出所有管道进程的执行状态。

[root@zhangst test]# ./0 | ./1 | ./2
[root@zhangst test]# echo ${PIPESTATUS[*]}
0 1 2 

0、1、2三个程序main函数中只包含一条return代码，分别返回 0，1，2。


2）bash中管道程序的执行相互不影响的，参考下面的例子：

[root@zhangst test]# ./0 | grep -v | ./2
用法: grep [选项]... PATTERN [FILE]...
试用‘grep --help’来获得更多信息。
2
0
[root@zhangst test]# echo ${PIPESTATUS[*]}
0 2 2

0、2三个程序分别在标准错误输出输出0、2，然后返回0、2
grep -v是不正确的，不能正确执行，但是0和2都正确执行完毕了。