庄周梦蝶

2007-03-30

C#实现栈和队列

有了前一篇C#链表的实现，实现栈和队列易如反掌。

栈，利用单向链表实现：

public abstract class AbstractStack
    {
        public abstract Object Pop();
        public abstract void Push(Object obj);
        public abstract bool IsEmpty();
        public abstract Object Top();
        public abstract void Clear();
    }

    public class Stack : AbstractStack
    {
        private SList list;
        public Stack()
        {
            list = new SList();
        }
        public override bool IsEmpty()
        {
            return list.IsEmpty();
        }
        public override void Push(Object obj)
        {
            list.Push(obj);
        }
        public override object Pop()
        {
            return list.Pop();
        }
        public override object Top()
        {
            return list.getTail();
        }
        public override void Clear()
        {
            list.Clear();
        }
    }

队列的实现，通过双向链表实现，对于环形数组的实现请参考《数组结构之栈与链表》：

public interface Queue
    {
        bool IsEmpty();
        void Enqueue(Object obj);
        Object Dequeue();
        Object First();
    }

    public class ListQueue:Queue
    {
        private LinkedList list;
        public ListQueue()
        {
            list = new LinkedList();
        }

        public bool IsEmpty()
        {
            return list.IsEmpty();
        }

        public void Enqueue(Object obj)
        {
            list.Push(obj);
        }
        public Object Dequeue()
        {
            return list.Shift();
        }

        public Object First()
        {
            return list.getHead();
        }
    }