1.3.8

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

解答

首先是 DoublingStackOfStrings 类,据我猜测应该是用数组实现的栈,扩容时长度增加一倍,缩短时长度减小一半。

官方 JAVA 代码参考:FixedCapacityStackOfString.java

代码

DoublingStackOfStrings 类

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

namespace _1._3._8
{
    class DoublingStackOfStrings : IEnumerable<string>
    {
        private string[] items;
        private int count;

        /// <summary>
        /// 新建一个字符串栈。
        /// </summary>
        public DoublingStackOfStrings()
        {
            this.items = new string[2];
            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="s"></param>
        public void Push(string s)
        {
            if (this.count == this.items.Length)
                Resize(this.items.Length * 2);
            this.items[this.count] = s;
            this.count++;
        }

        /// <summary>
        /// 从栈中弹出一个字符串,返回被弹出的元素。
        /// </summary>
        /// <returns></returns>
        public string Pop()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack underflow");
            count--;

            //缩小长度
            if (count > 0 && count <= items.Length / 4)
                Resize(items.Length / 2);

            return items[count];

        }

        /// <summary>
        /// 返回栈顶元素(但不弹出它)。
        /// </summary>
        /// <returns></returns>
        public string Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack underflow");
            return items[count - 1];
        }

        /// <summary>
        /// 为栈重新分配空间,超出空间的元素将被舍弃。
        /// </summary>
        /// <param name="capcity">重新分配的空间大小。</param>
        private void Resize(int capcity)
        {
            string[] temp = new string[capcity];

            for (int i = 0; i < this.count; ++i)
            {
                temp[i] = items[i];
            }

            items = temp;
        }

        public IEnumerator<string> GetEnumerator()
        {
            return new StackEnumerator(this.items);
        }

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

        private class StackEnumerator : IEnumerator<string>
        {
            int current;
            string[] items;

            public StackEnumerator(string[] items)
            {
                this.items = items;
                current = -1;
            }

            string IEnumerator<string>.Current => this.items[this.current];

            object IEnumerator.Current => this.items[this.current];

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

            bool IEnumerator.MoveNext()
            {
                if (this.current == items.Length - 1)
                    return false;
                this.current++;
                return true;
            }

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

主函数

using System;

namespace _1._3._8
{
    /*
     * 1.3.8
     * 
     * 给定以下输入,给出 DoublingStackOfStrings 的数组的内容和大小。
     * 
     * it was - the best - of times - - - it was - the - -
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            DoublingStackOfStrings stack = new DoublingStackOfStrings();

            string[] input = "it was - the best - of times - - - it was - the - -".Split(' ');


            foreach (string n in input)
            {
                if (n == "-")
                    stack.Pop();
                else
                    stack.Push(n);
            }

            foreach (string s in stack)
            {
                Console.Write(s + ' ');
            }

            Console.WriteLine($"\nStack Size: {stack.Size()}");
        }
    }
}
上一题 下一题