linux中的pushd命令及栈原理

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)是相同的。

这样就清楚这个命令对栈中元素是怎么移动的了。