1.3.38

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

这里采用“假删除”的方式,对要删除的元素不直接删除而是打上标记,这样就可以维持插入的顺序。

代码

数组实现

using System;

namespace _1._3._38
{
    class ArrayBasedGeneralizeQueue<Item>
    {
        private Item[] queue;
        private bool[] IsVisited;
        private int count;
        private int first;
        private int last;

        /// <summary>
        /// 建立一个队列。
        /// </summary>
        public ArrayBasedGeneralizeQueue()
        {
            this.queue = new Item[2];
            this.IsVisited = new bool[2];
            this.first = 0;
            this.last = 0;
            this.count = 0;
        }

        /// <summary>
        /// 检查队列是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.count == 0;
        }

        /// <summary>
        /// 为队列重新分配空间。
        /// </summary>
        /// <param name="capacity"></param>
        private void Resize(int capacity)
        {
            Item[] temp = new Item[capacity];
            for (int i = 0; i < this.count; ++i)
            {
                temp[i] = this.queue[i];
            }
            this.queue = temp;

            bool[] t = new bool[capacity];
            for (int i = 0; i < this.count; ++i)
            {
                t[i] = this.IsVisited[i];
            }
            this.IsVisited = t;
        }

        /// <summary>
        /// 向队列中插入一个元素。
        /// </summary>
        /// <param name="item">要插入队列的元素。</param>
        public void Insert(Item item)
        {
            if (this.count == this.queue.Length)
            {
                Resize(this.queue.Length * 2);
            }

            this.queue[this.last] = item;
            this.IsVisited[this.last] = false;
            this.last++;
            this.count++;
        }

        /// <summary>
        /// 从队列中删除并返回第 k 个插入的元素。
        /// </summary>
        /// <param name="k">要删除元素的顺序(从 1 开始)</param>
        /// <returns></returns>
        public Item Delete(int k)
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            if (k > this.last || k < 0)
            {
                throw new ArgumentOutOfRangeException();
            }

            if (IsVisited[k - 1] == true)
            {
                throw new ArgumentException("this node had been already deleted");
            }

            Item temp = this.queue[k - 1];
            this.IsVisited[k - 1] = true;
            this.count--;
            return temp;
        }
    }
}

链表实现

using System;

namespace _1._3._38
{
    class LinkedListBasedGeneralizeQueue<Item>
    {
        private class Node<T>
        {
            public T item;
            public Node<T> next;
            public bool IsVisited;
        }

        private Node<Item> first;
        private Node<Item> last;
        private int count;

        /// <summary>
        /// 建立一个队列。
        /// </summary>
        public LinkedListBasedGeneralizeQueue()
        {
            this.first = null;
            this.last = null;
            this.count = 0;
        }

        /// <summary>
        /// 检查数组是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.first == null;
        }

        /// <summary>
        /// 在队尾插入元素。
        /// </summary>
        /// <param name="item">需要插入的元素。</param>
        public void Insert(Item item)
        {
            Node<Item> oldLast = this.last;
            this.last = new Node<Item>()
            {
                item = item,
                IsVisited = false,
                next = null
            };

            if (oldLast == null)
            {
                this.first = this.last;
            }
            else
            {
                oldLast.next = this.last;
            }
            count++;
        }

        /// <summary>
        /// 删除第 k 个插入的结点
        /// </summary>
        /// <param name="k">结点序号(从 1 开始)</param>
        /// <returns></returns>
        public Item Delete(int k)
        {
            if (k > this.count || k <= 0)
            {
                throw new ArgumentOutOfRangeException();
            }

            k--;

            //找到目标结点
            Node<Item> current = this.first;
            for (int i = 0; i < k; ++i)
            {
                current = current.next;
            }

            if (current.IsVisited == true)
            {
                throw new ArgumentException("this node had been already deleted");
            }

            current.IsVisited = true;
            return current.item;
        }

    }
}
上一题 下一题