Forum Navigation
Stack and Queue
Posted: 01/22/08 23:19:41I know some people were asking for a implementation of Stack and Queue in Tango's collections classes. I got really bored and wrote a bare-bones implementation of both using a circular doubly-linked list. I'm still "moving in" to D, so it's probably not using the best features of D, and I haven't even tested or compiled it yet, but here it goes.
And yes, I know it's perfectly useless to have a circular doubly-linked stack. I was writing a queue, then I forgot what I was doing and wrote a stack. I came out of my stupor wondering why I had a circular doubly-linked stack. It was funny.
package tango.util.collection.LinkedQueue; // written 20080122110838 PST // by Chris Miller (lord Sauron the Great {at} gmail {dot} com) class LinkedQueue(K) { private struct Node(K) { K data; Node(K) left, right; } // private struct Node(K) private Node(K) head=null; public LinkedQueue(); public void push(K e) { Node(K) d=new Node(); d.data=e; if(!head) { head=d; d.left=d; d.right=d; return; } // if(!head) head.left.right=d; d.left=head.left; head.left=d; d.right=head; } // public void push(K e) public K peek() { if(!head) return null; return head.data; } public K pop() { if(!head) return null; else if(head.left==head && head.right==head) { K temp=head.data; head=null; return temp; } // else if(head.left==head && head.right==head) K temp=head.data; head.left.right=head.right; head.right.left=head.left; head=head.right; return temp; } // public K pop() } // class LinkedQueue(K)package tango.util.collection.LinkedStack; // written 20080122101455 PST // by Chris Miller (lord Sauron the Great {at} gmail {dot} com) class LinkedStack(K) { private struct Node(K) { K data; Node(K) left, right; } // private struct Node(K) private Node(K) head=null; public LinkedStack(); public void push(K e) { Node(K) d=new Node(); d.data=e; d.right=head; d.left=head.left; head.left=d; head.right=d; head=d; } // public void push(K e) public K peek() { if(!head) return null; return head.data; } public K pop() { if(!head) return null; if(head.left==head && head.right==head) { K temp=head.data; head=null; return temp; } // if(head.left==head && head.right==head) head.right.left=head.left; head.left.right=head.right; K temp=head.data; head=head.right; return temp; } // public K pop() } // class LinkedStack(K)I'm not all to familiar with Tango, either, so that probably ignores a lot of Tango conventions for collections, but it's a starting point, no?
Registered Linux Addict #431495
http://profile.xfire.com/mrstalinman | John 3:16!
http://www.fsdev.net/ | http://www.mindofsauron.blogspot.com/