读书人

二个堆栈实现自定义队列的入队出队方法

发布时间: 2012-09-09 09:27:54 作者: rapoo

2个堆栈实现自定义队列的入队出队方法 - 调用者定义2个栈的容量

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace MyQueue{    public class MyQueue2<T>    {        private int _bigStackFlag = 0;        private int _bigCapacity;        private int _smallCapacity;        private bool _isSameCapacity;        private Stack<T> _big;        private Stack<T> _small;        public int Count { get; private set; }        public bool IsEmpty { get { return this.Count == 0; } }        public bool IsFull        {            get            {                if (this._isSameCapacity)                {                    return this.Count >= this._smallCapacity + 1;                }                else                {                    return this.Count >= this._smallCapacity + 2;                }            }        }        public MyQueue2(int capacity1, int capacity2)        {            if (capacity1 >= capacity2)            {                this._bigCapacity = capacity1;                this._smallCapacity = capacity2;            }            else            {                this._bigCapacity = capacity2;                this._smallCapacity = capacity1;            }            this._big = new Stack<T>(this._bigCapacity);            this._small = new Stack<T>(this._smallCapacity);            this._isSameCapacity = (this._bigCapacity == this._smallCapacity);            this.Count = 0;        }        public void Enqueue(T item)        {            if (this.IsFull)            {                throw new System.InvalidOperationException("Queue full");            }            if (this._small.Count < this._smallCapacity)            {                this._small.Push(item);            }            else            {                this._big.Push(item);                this._bigStackFlag++;            }            this.Count++;            Console.WriteLine("Enqueue " + item.ToString());        }        public T Dequeue()        {            if (this.IsEmpty)            {                throw new System.InvalidOperationException("Queue empty");            }            while (this._small.Count != 1)            {                this._big.Push(this._small.Pop());            }            T result = this._small.Pop();            while (this._big.Count > this._bigStackFlag)            {                this._small.Push(this._big.Pop());            }            if (this._bigStackFlag != 0)            {                if (this._bigStackFlag == 1)                {                    this._small.Push(this._big.Pop());                }                else if (this._bigStackFlag == 2)                {                    T tmp = this._big.Pop();                    this._small.Push(this._big.Pop());                    this._big.Push(tmp);                }                else                {                    throw new Exception("inner expection: this._bigStackFlag is larger than 2!");                }                this._bigStackFlag--;            }            this.Count--;            Console.WriteLine("Dequeue " + result.ToString());            return result;        }    }    class Test    {        static void Main(string[] args)        {            MyQueue2<int> q = new MyQueue2<int>(2, 6);            //MyQueue2<int> q = new MyQueue2<int>(3, 3);            for (int i = 1; i < 5; i++)            {                q.Enqueue(i);            }            q.Dequeue();            q.Enqueue(5);            Console.WriteLine("before clear");            while (!q.IsEmpty)            {                q.Dequeue();            }            //q.Dequeue();            Console.WriteLine("clear");            for (int i = 6; i < 11; i++)            {                q.Enqueue(i);            }            Console.WriteLine("done");        }    }}

读书人网 >其他相关

热点推荐