PHP实现双向链表、栈，c语言实现双向链表

PHP实现双向链表、栈，c语言实现双向链表

前期写过一个PHP实现单向链表、实现排序单向链表的一篇文章，传送门：http://www.cnblogs.com/yydcdut/p/3777760.html。双向链表写过了，再拿出来提一提：http://www.cnblogs.com/yydcdut/p/3782661.html。

这次再来分享一下实现双向链表和栈的实现。代码虽然是以前写的了，但是发现PHP写的这些代码很容易看懂！

双向链表                                                                                      

<?<span>php
        </span><span>//</span><span>双向链表</span>
        <span>class</span><span> Hero
        {
            </span><span>public</span> <span>$pre</span>=<span>null</span>;<span>//</span><span>前指针</span>
            <span>public</span> <span>$no</span>;<span>//</span><span>排名</span>
            <span>public</span> <span>$name</span>;<span>//</span><span>名字</span>
            <span>public</span> <span>$next</span>=<span>null</span>;<span>//</span><span>后指针</span>
            
            <span>/*</span><span>*
            *构造函数，申明链表头
            </span><span>*/</span>
            <span>public</span> <span>function</span> __construct(<span>$no</span>='',<span>$name</span>=''<span>)
            {
                </span><span>$this</span>->no=<span>$no</span><span>;
                </span><span>$this</span>->name=<span>$name</span><span>;
            }
            </span><span>/*</span><span>*
            *插入
            </span><span>*/</span>
            <span>static</span> <span>public</span> <span>function</span> addHero(<span>$head</span>,<span>$hero</span><span>)
            {
                </span><span>$cur</span> = <span>$head</span><span>;
                </span><span>$isExist</span>=<span>false</span><span>;
                </span><span>//</span><span>判断目前这个链表是否为空</span>
                <span>if</span>(<span>$cur</span>-><span>next</span>==<span>null</span><span>)
                {
                    </span><span>$cur</span>-><span>next</span>=<span>$hero</span><span>;
                    </span><span>$hero</span>->pre=<span>$cur</span><span>;
                }
                </span><span>else</span><span>
                {
                    </span><span>//</span><span>如果不是空节点，则安排名来添加
                    //找到添加的位置            </span>
                    <span>while</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                    {
                        </span><span>if</span>(<span>$cur</span>-><span>next</span>->no > <span>$hero</span>-><span>no)
                        {</span><span>//</span><span>如果大于了排名，跳出</span>
                            <span>break</span><span>;
                        }
                        </span><span>else</span> <span>if</span>(<span>$cur</span>-><span>next</span>->no == <span>$hero</span>-><span>no)
                        {</span><span>//</span><span>如果等于排名，则代表有这个元素了</span>
                            <span>$isExist</span>=<span>true</span><span>;
                            </span><span>echo</span> "<br>不能添加相同的编号"<span>;
                        }
                        </span><span>$cur</span>=<span>$cur</span>-><span>next</span><span>;
                    }
                    </span><span>if</span>(!<span>$isExist</span><span>)
                    {</span><span>//</span><span>如果元素不存在，执行插入操作</span>
                        <span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                        {</span><span>$hero</span>-><span>next</span>=<span>$cur</span>-><span>next</span><span>;}
                        </span><span>$hero</span>->pre=<span>$cur</span><span>;
                        </span><span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                        {</span><span>$hero</span>-><span>next</span>->pre=<span>$hero</span><span>;}
                        </span><span>$cur</span>-><span>next</span>=<span>$hero</span><span>;            
                    }
                }
            }
            </span><span>//</span><span>遍历</span>
            <span>static</span> <span>public</span> <span>function</span> showHero(<span>$head</span><span>)
            {
                </span><span>$cur</span>=<span>$head</span><span>;
                </span><span>while</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                {
                    </span><span>echo</span> "<br>编号：".<span>$cur</span>-><span>next</span>->no."名字：".<span>$cur</span>-><span>next</span>-><span>name;
                    </span><span>$cur</span>=<span>$cur</span>-><span>next</span><span>;
                }
            }        
            </span><span>static</span> <span>public</span> <span>function</span> delHero(<span>$head</span>,<span>$herono</span><span>)
            {
                </span><span>$cur</span>=<span>$head</span><span>;
                </span><span>$isFind</span>=<span>false</span><span>;
                </span><span>while</span>(<span>$cur</span>!=<span>null</span><span>)
                {
                    </span><span>if</span>(<span>$cur</span>->no==<span>$herono</span><span>)
                    {
                        </span><span>$isFind</span>=<span>true</span><span>;
                        </span><span>break</span><span>;
                    }
                    </span><span>//</span><span>继续找</span>
                    <span>$cur</span>=<span>$cur</span>-><span>next</span><span>;
                }
                </span><span>if</span>(<span>$isFind</span><span>)
                {
                    </span><span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
                    {</span><span>$cur</span>->next_pre=<span>$cur</span>-><span>pre;}
                    </span><span>$cur</span>->pre-><span>next</span>=<span>$cur</span>-><span>next</span><span>;
                }
                </span><span>else</span><span>
                {</span><span>echo</span> "<br>没有找到目标"<span>;}            
            }
        }
        </span><span>$head</span> = <span>new</span><span> Hero();
        </span><span>$hero1</span> = <span>new</span> Hero(1,'1111'<span>);
        </span><span>$hero3</span> = <span>new</span> Hero(3,'3333'<span>);
        </span><span>$hero2</span> = <span>new</span> Hero(2,'2222'<span>);
        Hero</span>::addHero(<span>$head</span>,<span>$hero1</span><span>);
        Hero</span>::addHero(<span>$head</span>,<span>$hero3</span><span>);
        Hero</span>::addHero(<span>$head</span>,<span>$hero2</span><span>);
        Hero</span>::showHero(<span>$head</span><span>);
        Hero</span>::delHero(<span>$head</span>,2<span>);
        Hero</span>::showHero(<span>$head</span><span>);
</span>?>

双向链表的插入操作示意图：

<span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
    </span><span>$hero</span>-><span>next</span>=<span>$cur</span>-><span>next</span><span>;
</span><span>$hero</span>->pre=<span>$cur</span><span>;
 </span><span>if</span>(<span>$cur</span>-><span>next</span>!=<span>null</span><span>)
    </span><span>$hero</span>-><span>next</span>->pre=<span>$hero</span><span>;
</span><span>$cur</span>-><span>next</span>=<span>$hero</span>;

 

if($cur->next!=null) $cur->next->pre=$cur->pre; $cur->pre->next=$cur->next;

 

栈                                                                                              

<?<span>php

    </span><span>class</span><span> myStack
    {
        </span><span>private</span> <span>$top</span>=-1<span>;
        </span><span>private</span> <span>$maxSize</span>=5<span>;
        </span><span>private</span> <span>$stack</span>=<span>array</span><span>();
        </span><span>public</span> <span>function</span> push(<span>$val</span><span>)
        {
            </span><span>if</span>(<span>$this</span>->top == <span>$this</span>-><span>maxSize)
            {
                </span><span>echo</span> "<br>已经满了"<span>;
            }
            </span><span>$this</span>->top++<span>;
            </span><span>$this</span>->stack[<span>$this</span>->top]=<span>$val</span><span>;
        }
        
        </span><span>public</span> <span>function</span><span> showStack()
        {
            </span><span>if</span>(<span>$this</span>->top==-1<span>)
            {
                </span><span>echo</span> "<br>栈为空！"<span>;
                </span><span>return</span><span> ;
            }
            </span><span>for</span>(<span>$i</span>=<span>$this</span>->top;<span>$i</span>>-1;<span>$i</span>--<span>)
            {
                </span><span>echo</span> "<br>stack[".<span>$i</span>."]=".<span>$this</span>->stack[<span>$i</span><span>];
            }
        }
        
        </span><span>public</span> <span>function</span><span> pop()
        {
            </span><span>if</span>(<span>$this</span>->top==-1<span>)
            {
                </span><span>echo</span> "<br>栈为空！"<span>;
                </span><span>return</span><span> ;
            }
            
            </span><span>$val</span>=<span>$this</span>->stack[<span>$this</span>-><span>top];
            </span><span>$this</span>->top--<span>;
            </span><span>echo</span> "<br>弹出".<span>$val</span><span>;
        }
    }

    </span><span>$mystack</span> = <span>new</span><span> myStack;
    </span><span>$mystack</span>->push('111'<span>);
    </span><span>$mystack</span>->push('222'<span>);
    </span><span>$mystack</span>-><span>showStack();
    </span><span>$mystack</span>-><span>pop();
    </span><span>$mystack</span>-><span>pop();
</span>?>

我是天王盖地虎的分割线                                                                

《PHP实现链表》传送门：http://www.cnblogs.com/yydcdut/p/3777760.html

 

 

 

转载请注明出处：转载请注明出处：http://www.cnblogs.com/yydcdut

java 中用双向链表模拟栈

里只实现了Stack部分功能

public class Stack{

private Node top;

public Stack(){
this.top = null;
}

public void push(Node node){
if(node == null)
return;
if(this.top == null){
this.top = node;
node.setNext(null);
node.setPre(null);
}
else{
this.top.setNext(node);
node.setPre(this.top);
node.setNext(null);
this.top = node;
}
}

public Node pop(){
if(this.top == null)
return null;
Node curr = this.top;
Node pre = curr.getPre();
pre.setNext(null);
this.top = pre;
return curr;
}

public Node top(){
return this.top;
}

public boolean isEmpty(){
return this.top == null ? true : false;
}

public void empty(){
this.top = null;
}

public static void main(String[] args){
Stack stack = new Stack();
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);

System.out.println(stack.isEmpty());
stack.push(n1);
System.out.println(stack.top().getValue());
stack.push(n2);
stack.push(n3);
System.out.println(stack.pop().getValue());
stack.empty();
}
}

class Node {
private int value;
private Node next;
private Node pre;

public Node(int value, Node next, Node pre){
this.value = value;
this.next = next;
this.pre = pre;
}

public Node(int value){
this.value = value;
this.next = null;
this.pre = null;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public Node getPre() {
return pre;
}

public void setPre(Node pre) {
this.pre = pre;
}
}

用链表实现堆栈或队列是什

堆栈或队列数据都需要种容器来盛放
比用内置数组来实现队列
int a[100];
入队操作样实现：已有元素全部移位新元素插入
（当实现效率比较低）

容器选择链表则入队操作样实现：
构造链节点（C结构体）要入队元素填入新节点再利用链表插入操作新节点插入链表

所用链表实现堆栈或队列盛放数据容器选作链表利用链表插入节点、删除节点来实现堆栈、队列相应操作

比用链表实现队列C写下几函数
//入队
void insert(指向队列（链表）指针待入队元素)；
//出队
void delete（指向队列（链表）指针）；