 |
linux中的pushd命令及栈原理
今天看了linux下面的pushd的命令：感觉不错。
我们可以将目录pushd到目录栈中，然后通过pushd进行切换目录。
但是这个命令多了一个功能+n和-n。就将对栈中的元素进行移动，其实pushd不添加参数就是移动栈中元素的。
这个是怎么移动的哪，我看网上介绍不是很清楚，自己打开数据结构，看了一下。
栈是限定在表的一端进行元素的插入和删除运算的线性表，将进行插入和删除的这一端称为栈顶，另一端称为栈底。
栈的基本操作有下面几类：
（1）InitStack（S）
构造一个空栈S。
（2）StackEmpty（S）
判栈空。若S为空栈，则返回TRUE，否则返回FALSE。
（3）StackFull（S）
判栈满。若S为满栈，则返回TRUE，否则返回FALSE。
注意：该运算只适用于栈的顺序存储结构。
（4）Push（S，x）
进栈。若栈S不满，则将元素x插入S的栈顶。
（5）Pop（S）
退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
（6）StackTop（S）
取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
对于栈的基本操作命令：
1,操作1,2,3我们就不用考虑了，这三个命令在调用之前已经处理了，对我们使用者是透明的。
2,操作4,进栈：pushd目录 就是这个操作
3,操作5,退栈：popd 就是这个操作
4,操作6,取栈顶元素，好像没有这个操作，但其实用dirs查看这个栈中所有元素。
加强的栈功能：
1,对于没有参数的pushd，其实就是将栈顶的第一个元素和第二元素交换位置。
提示：这个操作的所有操作，当前目录显示的有当前栈中第一个元素。
2,push+n和-n是我主要解释的。
这个命令中有队列的影子的。栈中元素移动时，都是从栈顶移出，然后插入到栈底。
(1)我们将栈按像数组一样进行编号，从栈顶开始:0,1,2,3...
pushd +n不是将编号为n的移到栈顶，移出的0到n-1个元素依次插到栈底。
例如：栈中的元素为a,b,c,d
pushd+1后元素为b,c,d,a
pushd +2后元素为c,d,a,b
pushd +0后元素没有变化:a,b,c,d
(2)对于pushd-n命令和上面一样，只是编号不一样。
这次编号从栈底从开始(假如有4个元素)：-3,-2,-1,-0
pushd-n，将编号为-n的移到栈顶，移出的从栈顶到-n+1的元素依次插到栈底。
例如：栈中的元素为a,b,c,d
pushd-1后元素为c,d,a,b
pushd -2后元素为b,c,d,a
pushd-0后元素没有变化:d,a,b,c
(3)总结一下：
假设有n个元素，那么pushd -i 与pushd +(n-1-i)是相同的。
例如有4个元素的话：
pushd -2与pushd+(4-1-2)是相同的。
这样就清楚这个命令对栈中元素是怎么移动的了。
| |
