1.3.33

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

解答

动态数组这里要注意 first 不要小于零。

代码

Deque 类

using System;
using System.Collections;
using System.Collections.Generic;

namespace _1._3._33
{
    public class Deque<Item> : IEnumerable<Item>
    {
        private class DoubleNode<T>
        {
            public T item;
            public DoubleNode<T> next;
            public DoubleNode<T> prev;
        }

        DoubleNode<Item> first;
        DoubleNode<Item> last;
        int count;

        /// <summary>
        /// 默认构造函数,建立一个双端队列。
        /// </summary>
        public Deque()
        {
            this.first = null;
            this.last = null;
            this.count = 0;
        }

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

        /// <summary>
        /// 返回队列中元素的数量。
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.count;
        }

        /// <summary>
        /// 向左端添加一个元素。
        /// </summary>
        /// <param name="item">要添加的元素。</param>
        public void PushLeft(Item item)
        {
            DoubleNode<Item> oldFirst = this.first;
            this.first = new DoubleNode<Item>()
            {
                item = item,
                prev = null,
                next = oldFirst
            };
            if (oldFirst == null)
            {
                this.last = this.first;
            }
            else
            {
                oldFirst.prev = this.first;
            }
            this.count++;
        }

        /// <summary>
        /// 向右端添加一个元素。
        /// </summary>
        /// <param name="item">要添加的元素。</param>
        public void PushRight(Item item)
        {
            DoubleNode<Item> oldLast = this.last;
            this.last = new DoubleNode<Item>()
            {
                item = item,
                prev = oldLast,
                next = null
            };

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

        /// <summary>
        /// 从右端删除并返回一个元素。
        /// </summary>
        /// <returns></returns>
        public Item PopRight()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Item temp = this.last.item;
            this.last = this.last.prev;
            this.count--;

            if (this.last == null)
            {
                this.first = null;
            }
            else
            {
                this.last.next.item = default(Item);
                this.last.next = null;
            }
            return temp;
        }

        /// <summary>
        /// 从左端删除并返回一个元素。
        /// </summary>
        /// <returns></returns>
        public Item PopLeft()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Item temp = this.first.item;
            this.first = this.first.next;
            this.count--;

            if (this.first == null)
            {
                this.last = null;
            }
            else
            {
                this.first.prev.item = default(Item);
                this.first.prev = null;
            }

            return temp;
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new DequeEnumerator(this.first);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class DequeEnumerator : IEnumerator<Item>
        {
            private DoubleNode<Item> current;
            private DoubleNode<Item> first;

            public DequeEnumerator(DoubleNode<Item> first) 
            {
                this.current = new DoubleNode<Item>();
                this.current.next = first;
                this.current.prev = null;
                this.first = this.current;
            }

            public Item Current => current.item;

            object IEnumerator.Current => current.item;

            public void Dispose()
            {
                this.current = null;
                this.first = null;
            }

            public bool MoveNext()
            {
                if (this.current.next == null)
                    return false;
                this.current = this.current.next;
                return true;
            }

            public void Reset()
            {
                this.current = this.first;
            }
        }
    }
}

ResizingArrayDeque 类

using System;
using System.Collections;
using System.Collections.Generic;

namespace _1._3._33
{
    public class ResizingArrayDeque<Item> : IEnumerable<Item>
    {
        private Item[] deque;
        private int first;
        private int last;
        private int count;

        /// <summary>
        /// 默认构造函数,建立一个双向队列。
        /// </summary>
        public ResizingArrayDeque()
        {
            this.deque = new Item[2];
            this.first = 0;
            this.last = 0;
            this.count = 0;
        }

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

        /// <summary>
        /// 返回队列中元素的数量。
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.count;
        }

        /// <summary>
        /// 为队列重新分配空间。
        /// </summary>
        /// <param name="capacity">需要重新分配的空间大小。</param>
        private void Resize(int capacity)
        {
            if (capacity <= 0)
                throw new ArgumentException();

            Item[] temp = new Item[capacity];
            for (int i = 0; i < count; ++i)
            {
                temp[i] = this.deque[(this.first + i) % this.deque.Length];
            }
            this.deque = temp;
            this.first = 0;
            this.last = this.count;
        }


        /// <summary>
        /// 在队列左侧添加一个元素。
        /// </summary>
        /// <param name="item">要添加的元素</param>
        public void PushLeft(Item item)
        {
            if (this.count == this.deque.Length)
            {
                Resize(2 * this.count);
            }

            this.first--;
            if (this.first < 0)
            {
                this.first += this.deque.Length;
            }
            this.deque[this.first] = item;
            this.count++;
        }

        public void PushRight (Item item)
        {
            if (this.count == this.deque.Length)
            {
                Resize(2 * this.count);
            }

            this.deque[this.last] = item;
            this.last = (this.last + 1) % this.deque.Length;
            this.count++;
        }

        public Item PopRight()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            this.last--;
            if (this.last < 0)
            {
                this.last += this.deque.Length;
            }
            Item temp = this.deque[this.last];
            this.count--;
            if (this.count > 0 && this.count == deque.Length / 4)
                Resize(this.deque.Length / 2);
            return temp;
        }

        public Item PopLeft()
        {
            if (IsEmpty())
                throw new ArgumentException();

            Item temp = this.deque[this.first];
            this.first = (this.first + 1) % this.deque.Length;
            this.count--;
            if (this.count > 0 && this.count == deque.Length / 4)
            {
                Resize(this.deque.Length / 2);
            }
            return temp;
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new ResizingDequeEnumerator(this.deque, this.first, this.count);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class ResizingDequeEnumerator : IEnumerator<Item>
        {
            private Item[] deque;
            private int current;
            private int first;
            private int count;

            public ResizingDequeEnumerator(Item[] deque, int first, int count)
            {
                this.deque = deque;
                this.first = first;
                this.count = count;
                this.current = -1;
            }

            Item IEnumerator<Item>.Current => this.deque[(this.first + this.current) % this.deque.Length];

            object IEnumerator.Current => this.deque[(this.first + this.current) % this.deque.Length];

            void IDisposable.Dispose()
            {
                this.deque = null;
                this.current = -1;
            }

            bool IEnumerator.MoveNext()
            {
                if (this.current == this.count - 1)
                {
                    return false;
                }

                this.current++;
                return true;
            }

            void IEnumerator.Reset()
            {
                this.current = -1;
            }
        }
    }
}

Program.cs

using System;

namespace _1._3._33
{
    /*
     * 1.3.33
     * 
     * Deque。
     * 一个双向队列(或称 deque)和栈或队列类似,但它同时支持在两端添加或删除元素。
     * Deque 能够存储一组元素并支持下表中的 API:
     * 
     * Deque()
     * 创建空双向队列。
     * Bool isEmpty()
     * 双向队列是否为空。
     * int size()
     * 双向队列中的元素数量。
     * void pushLeft(Item item)
     * 向左端添加一个新元素。
     * void pushRight(Item item)
     * 向右端添加一个新元素。
     * Item popLeft()
     * 从左端删除一个元素。
     * Item popRight()
     * 从右端删除一个元素。
     * 
     * 编写一个使用双向链表实现这份 API 的 Deque 类,
     * 以及一个使用动态数组调整实现这份 API 的 ResizingArrayDeque 类。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Deque<string> a = new Deque<string>();
            ResizingArrayDeque<string> b = new ResizingArrayDeque<string>();

            a.PushLeft("first");
            b.PushLeft("first");
            a.PushRight("second");
            b.PushRight("second");
            Display(a, b);

            a.PopLeft();
            b.PopLeft();
            Display(a, b);
            a.PopRight();
            b.PopRight();
            Display(a, b);
        }

        static void Display(Deque<string> a, ResizingArrayDeque<string> b)
        {
            foreach (string s in a)
            {
                Console.Write(s + " ");
            }
            Console.WriteLine();
            foreach (string s in b)
            {
                Console.Write(s + " ");
            }
            Console.WriteLine();
            Console.WriteLine();
        }
    }
}
上一题 下一题