渣渣寫算法之隊列

渣渣寫算法之隊列

隊列 Queue

隊列可以用數組和連結清單來實作

考慮到隊列的移除時數組資料的調整，分成了幾個情況

①移動數組，這樣當然來講，是性能不咋好的，通過一個指針并移動整體位置來實作，從一個角度解決了由于出對導緻非環形的數組中無用項的問題

public class ArrayQueue<T>
    {
        public int Length
        {
            get
            {
                return curIndex + 1;
            }
        }
        private int maxSize = 100;

        private int curIndex = -1;

        private T[] _data = null;

        public ArrayQueue()
        {
            _data = new T[maxSize];
        }

        public void Clear()
        {
            curIndex = -1;
        }


        public void EnQueue(T item)
        {
            curIndex++;
            if (curIndex >= maxSize)
            {
                Console.WriteLine("隊列已滿");
                return;
            }
            _data[curIndex] = item;
        }



        public T DeQueue()
        {
            if (curIndex > -1)
            {
                var data = _data[0];
                if (curIndex > 0)
                {
                    for (int i = 1; i <= curIndex; i++)
                    {
                        _data[i - 1] = _data[i];
                    }
                }
                curIndex--;
                return data;
            }
            throw new Exception("No Elem");
            return default(T);
        }

    }
      

　　②環形數組實作1，利用倆指針配合來完成數組的利用，用count統計控制目前有效的個數

public class CircleArrayQueue<T>
    {
        private int maxSize = 100;
        private int firstIndex = -1;
        private int lastIndex = -1;
        private T[] _data = null;

        public CircleArrayQueue(int setMaxSize = 4)
        {
            maxSize = setMaxSize;
            _data = new T[maxSize];
        }

        private bool isFull()
        {
           return Length== maxSize;
        }

        private bool isEmpty()
        {
            return Length==0;
        }

        public void Clear()
        {
            firstIndex = lastIndex = -1;
            Length = 0;
        }

        public int Length { get; private set; } = 0;



        public void EnQueue(T item)
        {
            if (isFull())
            {
                Console.WriteLine("已滿");
                return;
            }
            Length++;
            lastIndex++;
            if (lastIndex >= maxSize)
            {
                lastIndex = 0;
            }
            _data[lastIndex] = item;
            if (firstIndex == -1)
            {
                firstIndex = 0;
            }
        }



        public T DeQueue()
        {
            if (isEmpty())
            {
                throw new Exception("沒有元素");
            }
            Length--;
            var data = _data[firstIndex];
            firstIndex++;
            if (firstIndex >= maxSize)
            {
                firstIndex = 0;
            }
            return data;
        }

    }
      

　　

③環形數組實作2，其實兩個指針也可以統計出隊列中有效項的個數，不用額外定義一個count個數

public class CircleArray2Queue<T>
    {
        private int maxSize = 100;
        private int firstIndex = -1;
        private int lastIndex = -1;
        private T[] _data = null;

        public CircleArray2Queue(int setMaxSize = 4)
        {
            maxSize = setMaxSize;
            _data = new T[maxSize];
        }

        private bool isFull()
        {
            return (lastIndex + 1) % maxSize == firstIndex;
        }

        private bool isEmpty()
        {
            return firstIndex == -1||lastIndex == firstIndex;
        }

        public int Length
        {
            get
            {
                return firstIndex == -1 ? 0 : (lastIndex + maxSize - firstIndex) % maxSize + 1;
            }
        }

        public void Clear()
        {
            firstIndex = lastIndex = -1;
        }


        public void EnQueue(T item)
        {
            if (isFull())
            {
                Console.WriteLine("已滿");
                return;
            }
            lastIndex++;
            if (lastIndex >= maxSize)
            {
                lastIndex = 0;
            }
            _data[lastIndex] = item;
            if (firstIndex == -1)
            {
                firstIndex = 0;
            }
        }



        public T DeQueue()
        {
            if (isEmpty())
            {
                throw new Exception("沒有元素");
            }
            var data = _data[firstIndex];
            if (firstIndex != lastIndex)
            {
                firstIndex++;
                if (firstIndex >= maxSize)
                {
                    firstIndex = 0;
                }
            }
            return data;
        }

    }
      

　　④ 當然 ，還可以使用單連結清單來實作，通過連結清單的指針指向下一個，來找下一個元素，出隊的時候修正連結清單指針即可

public class CircleLinkQueue<T>
    {
        private class Item
        {
            public Item Next;
            public T Data;
        }

        private Item curItem = null;

        private Item firstItem = null;

        public int Length { get; private set; } = 0;

        public void Clear()
        {
            Length = 0;
            firstItem = null;
            curItem = null;
        }

        public void EnQueue(T item)
        {
            Length++;
            var d = new Item()
            {
                Data = item
            };
            if (curItem == null)
            {
                firstItem = d;
            }
            else
            {
                curItem.Next = d;
            }
            curItem = d;
        }



        public T DeQueue()
        {
            if (Length > 0 && firstItem != null)
            {
                var dd = firstItem.Data;
                Length--;
                firstItem = firstItem.Next;
                return dd;
            }
            else
            {
                throw new Exception("No Elem");               
            }
        }
    }
      

　　相比較于數組本身，數組有天然的指針結構，相鄰的元素有着天然的聯系，但是維護起來需要一定的邏輯，是以連結清單就定義了一個結構，包含了對元素本身和執行下一個元素，來友善指定聯系，連結清單中相連的元素在内部可能是不連續的。