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

namespace _1._3._1
{
    class FixedCapacityStackOfStrings : IEnumerable<string>
    {
        private string[] a;
        private int N;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        /// <param name="capacity">栈的大小。</param>
        public FixedCapacityStackOfStrings(int capacity)
        {
            this.a = new string[capacity];
            this.N = 0;
        }

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

        /// <summary>
        /// 检查栈是否已满。
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return this.N == this.a.Length;
        }

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(string item)
        {
            this.a[N] = item;
            this.N++;
        }

        /// <summary>
        /// 从栈中弹出一个元素，返回被弹出的元素。
        /// </summary>
        /// <returns></returns>
        public string Pop()
        {
            this.N--;
            return this.a[N];
        }

        /// <summary>
        /// 返回栈顶元素（但不弹出它）。
        /// </summary>
        /// <returns></returns>
        public string Peek()
        {
            return this.a[N - 1];
        }

        public IEnumerator<string> GetEnumerator()
        {
            return new ReverseEnmerator(this.a);
        }

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

        private class ReverseEnmerator : IEnumerator<string>
        {
            private int current;
            private string[] a;

            public ReverseEnmerator(string[] a)
            {
                this.current = a.Length;
                this.a = a;
            }

            string IEnumerator<string>.Current => a[current];

            object IEnumerator.Current => a[current];

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

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

            void IEnumerator.Reset()
            {
                this.current = a.Length;
            }
        }
    }
}

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

namespace Generics
{
    public class Stack<Item> : IEnumerable<Item>
    {
        private Node<Item> first;
        private int count;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Stack()
        {
            this.first = null;
            this.count = 0;
        }

        /// <summary>
        /// 复制构造函数。
        /// </summary>
        /// <param name="s"></param>
        public Stack(Stack<Item> s)
        {
            if (s.first != null)
            {
                this.first = new Node<Item>(s.first);
                for (Node<Item> x = this.first; x.next != null; x = x.next)
                {
                    x.next = new Node<Item>(x.next);
                }
            }
        }

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

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

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(Item item)
        {
            Node<Item> oldFirst = this.first;
            this.first = new Node<Item>();
            this.first.item = item;
            this.first.next = oldFirst;
            this.count++;
        }

        /// <summary>
        /// 将一个元素从栈中弹出，返回弹出的元素。
        /// </summary>
        /// <returns></returns>
        public Item Pop()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            Item item = this.first.item;
            this.first = this.first.next;
            this.count--;
            return item;
        }

        /// <summary>
        /// 返回栈顶元素（但不弹出它）。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            return this.first.item;
        }

        /// <summary>
        /// 将两个栈连接。
        /// </summary>
        /// <param name="s1">第一个栈。</param>
        /// <param name="s2">第二个栈（将被删除）。</param>
        /// <returns></returns>
        public static Stack<Item> Catenation(Stack<Item> s1, Stack<Item> s2)
        {
            if (s1.IsEmpty())
            {
                s1.first = s2.first;
                s1.count = s2.count;
            }
            else
            {
                Node<Item> last = s1.first;
                while (last.next != null)
                {
                    last = last.next;
                }
                last.next = s2.first;
                s1.count += s2.count;
            }
            s2 = null;
            return s1;
        }

        /// <summary>
        /// 创建栈的浅表副本。
        /// </summary>
        /// <returns></returns>
        public Stack<Item> Copy()
        {
            Stack<Item> temp = new Stack<Item>();
            temp.first = this.first;
            temp.count = this.count;
            return temp;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            foreach (Item n in this)
            {
                s.Append(n);
                s.Append(‘ ‘);
            }
            return s.ToString();
        }

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

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

        private class StackEnumerator : IEnumerator<Item>
        {
            private Node<Item> current;
            private Node<Item> first;

            public StackEnumerator(Node<Item> first)
            {
                this.current = new Node<Item>();
                this.current.next = first;
                this.first = this.current;
            }

            Item IEnumerator<Item>.Current => current.item;

            object IEnumerator.Current => current.item;

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

            bool IEnumerator.MoveNext()
            {
                if (this.current.next == null)
                    return false;

                this.current = this.current.next;
                return true;
            }

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

using System;
using Generics;

namespace _1._3._4
{
    /*
     * 1.3.4
     * 
     * 编写一个 Stack 的用例 Parentheses，
     * 从标准输入中读取一个文本流并使用栈判定其中的括号是否配对完整。
     * 例如，对于 [()]{}{[()()]()} 程序应该打印 true，
     * 对于 [(]) 则打印 false。
     * 
     */
    class Parentheses
    {
        static bool isBalanced(string input)
        {
            Stack<char> stack = new Stack<char>();

            foreach (char i in input)
            {
                if (i == ‘(‘ || i == ‘[‘ || i == ‘{‘)
                    stack.Push(i);
                else
                {
                    if (stack.Peek() == ‘(‘ && i == ‘)‘)
                        stack.Pop();
                    else if (stack.Peek() == ‘{‘ && i == ‘}‘)
                        stack.Pop();
                    else if (stack.Peek() == ‘[‘ && i == ‘]‘)
                        stack.Pop();
                    else
                        return false;
                }
            }

            return stack.IsEmpty();
        }

        static void Main(string[] args)
        {
            string input = "[()]{}{[()()]()}";
            Console.WriteLine(isBalanced(input));
            string input2 = "[(])";
            Console.WriteLine(isBalanced(input2));
        }
    }
}

Stack<Integer> stack = new Stack<Integer>();
while (N > 0)
{
    stack.push(N % 2);
    N = N / 2;
}
for (int d : stack) StdOut.print(d);
StdOut.println();

using System;
using Generics;

namespace _1._3._5
{
    /*
     * 1.3.5
     * 
     * 当 N 为 50 时下面这段代码会打印什么？
     * 从较高的抽象层次描述给定正整数 N 时这段代码的行为。
     * 
     */
    class Program
    {
        //将十进制数 N 转换为二进制数。
        static void Main(string[] args)
        {
            int N = 50;
            Stack<int> stack = new Stack<int>();
            while (N > 0)
            {
                stack.Push(N % 2);
                N = N / 2;
            }
            foreach (int d in stack)
            {
                Console.WriteLine(d);
            }
            Console.WriteLine();
        }
    }
}

Stack<String> stack = new Stack<String>();
while (!q.isEmpty())
    stack.push(q.dequeue());
while(!stack.isEmpty())
    q.enqueue(stack.pop());

using System;
using Generics;

namespace _1._3._6
{
    /*
     * 1.3.6
     * 
     * 下面这段代码对队列 q 进行了什么操作？
     * 
     */
    class Program
    {
        //将队列反序
        static void Main(string[] args)
        {
            Queue<string> q = new Queue<string>();
            q.Enqueue("first");
            q.Enqueue("second");
            q.Enqueue("third");
            q.Enqueue("fourth");
            Stack<string> stack = new Stack<string>();
            while (!q.IsEmpty())
                stack.Push(q.Dequeue());
            while (!stack.IsEmpty())
                q.Enqueue(stack.Pop());

            Console.WriteLine(q.ToString());
        }
    }
}

/// <summary>
        /// 返回栈顶元素（但不弹出它）。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            return this.first.item;
        }

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()}");
        }
    }
}

using System;
using Generics;

namespace _1._3._9
{
    /*
     * 1.3.9
     * 
     * 编写一段程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式。
     * 例如，给定输入：
     * 1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
     * 你的程序应该输出：
     * ( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )
     * 
     */
    class Program
    {
        //在计算中序表达式算法的基础上做修改
        //压入数字时将该数字所在的位置也一并压入
        //弹出数字进行运算时在位置靠前的数字前加上左括号
        //A + B ) * C + D ) ) 为例
        //A 压入栈中并记录位置                                        
        //+ 压入栈中
        //B 压入栈中并记录位置                                             
        //) 计算，在 A 之前加入左括号，结果 E 压入栈中，位置为 A 的位置
        //* 压入栈中
        //C 压入栈中并记录位置
        //+ 压入栈中
        //D 压入栈中并记录位置
        //) 计算，在 C 之前加入左括号，结果 F 压入栈中，位置为 C 的位置
        //) 计算，在 E 之前加入左括号（也就是 A 之前），结果 G 压入栈中，位置为 E 的位置。
        static void Main(string[] args)
        {
            string input = "1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )";
            Stack<char> operators = new Stack<char>();
            Stack<Number> numbers = new Stack<Number>();
            int[] leftBrackets = new int[input.Length];
            
            for (int i = 0; i < input.Length; ++i)
            {
                if (input[i] == ‘ ‘)
                    continue;
                else if (input[i] == ‘+‘ || input[i] == ‘-‘ || input[i] == ‘*‘ || input[i] == ‘/‘)
                {
                    operators.Push(input[i]);
                }
                else if (input[i] == ‘)‘)
                {
                    Number B = numbers.Pop();
                    Number A = numbers.Pop();
                    char operation = operators.Pop();
                    Number C = new Number();
                    C.Position = A.Position;
                    leftBrackets[A.Position]++;

                    switch (operation)
                    {
                        case ‘+‘:
                            C.Value = A.Value + B.Value;
                            break;
                        case ‘-‘:
                            C.Value = A.Value - B.Value;
                            break;
                        case ‘*‘:
                            C.Value = A.Value * B.Value;
                            break;
                        case ‘/‘:
                            C.Value = A.Value / B.Value;
                            break;
                    }
                    numbers.Push(C);
                }
                else
                {
                    Number num = new Number();
                    num.Position = i;
                    num.Value = input[i] - ‘0‘;
                    numbers.Push(num);
                }
            }

            for (int i = 0; i < input.Length; ++i)
            {
                while (leftBrackets[i] != 0)
                {
                    Console.Write("( ");
                    leftBrackets[i]--;
                }

                Console.Write(input[i]);
            }
        }
    }

    struct Number
    {
        public int Value;
        public int Position;
    }
}

using System;
using Generics;

namespace _1._3._10
{
    /*
     * 1.3.10
     * 
     * 编写一个过滤器 InfixToPostfix，
     * 将算术表达式由中序表达式转为后序表达式。
     * 
     */
    class InfixToPostfix
    {
        //其实就是把右括号换成相应运算符
        //对于 (A + B)，忽略左括号，数字直接输出，运算符入栈，遇到右括号时再弹出
        //结果 A B +，变成后序表达式
        static void Main(string[] args)
        {
            Stack<string> stack = new Stack<string>();
            string[] input = "( 2 + ( ( 3 + 4 ) * ( 5 * 6 ) ) )".Split(‘ ‘);
            foreach (string n in input)
            {
                if (n == " ")
                    continue;
                else if (n == "+" || n == "-" || n == "*" || n == "/")
                {
                    stack.Push(n);
                }
                else if (n == ")")
                {
                    Console.Write(stack.Pop() + " ");
                }
                else if (n == "(")
                {
                    continue;
                }
                else
                {
                    Console.Write(n + " ");
                }
            }
            Console.WriteLine();
        }
    }
}

using System;
using Generics;

namespace _1._3._11
{
    /*
     * 1.3.11
     * 
     * 编写一段程序 EvaluatePostfix，从标准输入中得到一个后序表达式，求值并打印结果
     * （将上一题的程序中得到的输出用管道传递给这一段程序可以得到和 Evaluate 相同的行为）。
     * 
     */
    class EvaluatePostfix
    {
        static void Main(string[] args)
        {
            Stack<int> stack = new Stack<int>();

            string[] input = "7 16 * 5 + 16 * 3 + 16 * 1 +".Split(‘ ‘);

            foreach (string n in input)
            {
                if (n == " ")
                {
                    continue;
                }
                else if (n == "+")
                {
                    stack.Push(stack.Pop() + stack.Pop());
                }
                else if (n == "-")
                {
                    int temp = stack.Pop();
                    stack.Push(stack.Pop() - temp);
                }
                else if (n == "*")
                {
                    stack.Push(stack.Pop() * stack.Pop());
                }
                else if (n == "/")
                {
                    int temp = stack.Pop();
                    stack.Push(stack.Pop() / temp);
                }
                else
                {
                    stack.Push(int.Parse(n));
                }
            }

            Console.WriteLine(stack.Pop());
        }
    }
}

using System;
using Generics;

namespace _1._3._12
{
    /*
     * 1.3.12
     * 
     * 编写一个可迭代的 Stack 用例，它含有一个静态的 CopyTo() 方法，
     * 接受一个字符串的栈作为参数并返回该栈的一个副本。
     * 注意：这种能力是迭代器价值的一个重要体现，
     * 因为有了它我们无需改变基本 API 就能实现这种功能。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Stack<string> src = http://www.mamicode.com/new Stack<string>();
            src.Push("first");
            src.Push("second");
            src.Push("third");

            Stack<string> des = CopyTo(src);
            
            while (!des.IsEmpty())
            {
                Console.WriteLine(des.Pop());
            }

        }

        static Stack<string> CopyTo(Stack<string> src)
        {
            Stack<string> des = new Stack<string>();
            Stack<string> temp = new Stack<string>();

            foreach (string s in src)
            {
                temp.Push(s);
            }

            while (!temp.IsEmpty())
            {
                des.Push(temp.Pop());
            }

            return des;
        }
    }
}

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

namespace _1._3._14
{
    class ResizingArrayQueueOfStrings<Item> : IEnumerable<Item>
    {
        private Item[] q;
        private int count;
        private int first;
        private int last;

        public ResizingArrayQueueOfStrings()
        {
            this.q = new Item[2];
            this.count = 0;
            this.first = 0;

        }

        public bool IsEmpty()
        {
            return this.count == 0;
        }

        public int Size()
        {
            return this.count;
        }

        private void Resize(int capacity)
        {
            if (capacity < 0)
                throw new ArgumentException("capacity should be above zero");
            Item[] temp = new Item[capacity];
            for (int i = 0; i < count; ++i)
            {
                temp[i] = this.q[(this.first + i) % this.q.Length];
            }

            this.q = temp;
            this.first = 0;
            this.last = this.count;
        }

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

            this.q[this.last] = item;
            this.last++;
            if (this.last == this.q.Length)
                this.last = 0;
            this.count++;
        }

        public Item Dequeue()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Queue underflow");
            Item item = this.q[first];
            this.q[first] = default(Item);
            this.count--;
            this.first++;
            if (this.first == this.q.Length)
                this.first = 0;

            if (this.count > 0 && this.count <= this.q.Length / 4)
                Resize(this.q.Length / 2);
            return item;
        }

        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Queue underflow");
            return this.q[first];
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new QueueEnumerator(this.q, this.first, this.last);
        }

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

        private class QueueEnumerator : IEnumerator<Item>
        {
            int current;
            int first;
            int last;
            Item[] q;

            public QueueEnumerator(Item[] q, int first, int last)
            {
                this.current = first - 1;
                this.first = first;
                this.last = last;
                this.q = q;
            }

            Item IEnumerator<Item>.Current => this.q[this.current];

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

            void IDisposable.Dispose()
            {
                
            }

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

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

using System;

namespace _1._3._14
{
    /*
     * 1.3.14
     * 
     * 编写一个类 ResizingArrayQueueOfStrings，
     * 使用定长数组实现队列的抽象，然后扩展实现，
     * 使用调整数组的方法突破大小的限制。
     * 
     */
    class Program
    {
        public static void Main(string[] args)
        {
            ResizingArrayQueueOfStrings<string> queue = new ResizingArrayQueueOfStrings<string>();
            string[] input = "to be or not to - be - - that - - - is".Split(‘ ‘);

            foreach (string s in input)
            {
                if (!s.Equals("-"))
                    queue.Enqueue(s);
                else if (!queue.IsEmpty())
                    Console.Write(queue.Dequeue() + ‘ ‘);
            }
            Console.WriteLine("(" + queue.Size() + " left on queue)");
        }
    }
}

using System;
using Generics;

namespace _1._3._15
{
    /*
     * 1.3.15
     * 
     * 编写一个 Queue 的用例，接受一个命令行参数 k 并打印出标准输入中的倒数第 k 个字符串
     * （假设标准输入中至少有 k 个字符串）。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Queue<string> queue = new Queue<string>();
            string[] input = "1 2 3 4 5 6 7 8 9 10".Split(‘ ‘);
            int k = 4;

            foreach(string s in input)
            {
                queue.Enqueue(s);
            }

            int count = queue.Size() - k;
            for(int i = 0; i < count; ++i)
            {
                queue.Dequeue();
            }

            Console.WriteLine(queue.Peek());
        }
    }
}

/// <summary>
        /// 从标准输入按行读取所有日期，返回一个日期数组。
        /// </summary>
        /// <returns></returns>
        public static Date[] ReadDates()
        {
            char[] split = new char[] { ‘\n‘ };
            string[] input = Console.In.ReadToEnd().Split(split, StringSplitOptions.RemoveEmptyEntries);
            Date[] d = new Date[input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                d[i] = new Date(input[i]);
            }

            return d;
        }

using System;

namespace _1._3._16
{
    /*
     * 1.3.16
     * 
     * 使用 1.3.1.5 节中的 readInts() 作为模板为 Date 编写一个静态方法 readDates()，
     * 从标准输入中读取由练习 1.2.19 的表格指定的格式的多个日期并返回一个它们的数组。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            //输入结束后按 Ctrl + Z 标记结尾
            //输入格式：06/30/2017
            //以回车分隔
            Date[] date = Date.ReadDates();
            foreach (Date d in date)
            {
                Console.WriteLine(d);
            }
        }
    }
}

/// <summary>
        /// 从标准输入中按行读取所有交易信息，返回一个 Transaction 数组。
        /// </summary>
        /// <returns></returns>
        public static Transaction[] ReadTransactions()
        {
            char[] split = new char[] { ‘\n‘ };
            string[] input = Console.In.ReadToEnd().Split(split, StringSplitOptions.RemoveEmptyEntries);
            Transaction[] t = new Transaction[input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                t[i] = new Transaction(input[i]);
            }

            return t;
        }

using System;

namespace _1._3._17
{
    /*
     * 1.3.17
     * 
     * 为 Transaction 类完成练习 1.3.16
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            //用 Ctrl + Z 标记结束输入
            Transaction[] t = Transaction.ReadTransactions();

            foreach (Transaction n in t)
            {
                Console.WriteLine(n.ToString());
            }
        }
    }
}

x.next = x.next.next;

using System;
using Generics;

namespace _1._3._18
{
    /*
     * 1.3.18
     * 
     * 假设 x 是一条链表的某个结点且不是尾结点。
     * 下面这条语句的效果是什么？
     * x.next = x.next.next;
     * 
     */
    class Program
    {
        //删除 x 的后一个结点。
        static void Main(string[] args)
        {
            Node<string> x = new Node<string>();
            x.item = "first";
            Node<string> y = new Node<string>();
            y.item = "second";
            x.next = y;
            Node<string> z = new Node<string>();
            z.item = "third";
            y.next = z;

            Console.WriteLine("x: " + x.item);
            Console.WriteLine("x.next: " + x.next.item);
            x.next = x.next.next;
            Console.WriteLine();
            Console.WriteLine("x: " + x.item);
            Console.WriteLine("x.next: " + x.next.item);
        }
    }
}

using System;
using Generics;

namespace _1._3._19
{
    /*
     * 1.3.19
     * 
     * 给出一段代码，删除链表的尾结点，其中链表的首结点为 first。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Node<string> first = new Node<string>()
            {
                item = "first"
            };
            Node<string> second = new Node<string>()
            {
                item = "second"
            };
            Node<string> third = new Node<string>()
            {
                item = "third"
            };

            first.next = second;
            second.next = third;
            third.next = null;

            Node<string> current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }

            DeleteLast(first);
            Console.WriteLine();

            current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }
            Console.WriteLine();
        }

        static void DeleteLast(Node<string> first)
        {
            Node<string> current = first;

            while (current.next.next != null)
            {
                current = current.next;
            }

            current.next = null;
        }
    }
}

/// <summary>
        /// 删除指定位置的元素，返回该元素。
        /// </summary>
        /// <param name="index">需要删除元素的位置。</param>
        /// <returns></returns>
        public Item Delete(int index)
        {
            if (index >= this.count)
            {
                throw new IndexOutOfRangeException();
            }

            Node<Item> front = this.first;
            Item temp = this.first.item;
            if (index == 0)
            {
                this.first = this.first.next;
                return temp;
            }

            for (int i = 1; i < index; ++i)
            {
                front = front.next;
            }

            temp = front.next.item;
            front.next = front.next.next;
            this.count--;
            return temp;
        }

using System;
using Generics;

namespace _1._3._21
{
    /*
     * 1.3.21
     * 
     * 编写一个方法 find()，接受一条链表和一个字符串 key 作为参数。
     * 如果链表中的某个结点的 item 域的值为 key，则方法返回 true，否则返回 false。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList<string> link = new LinkedList<string>();
            link.Insert("first", 0);
            link.Insert("second", 1);
            link.Insert("third", 2);

            Console.WriteLine(Find(link, "second"));
            Console.WriteLine(Find(link, "fourth"));
        }

        static bool Find<Item>(LinkedList<Item> link, Item key)
        {
            foreach (Item i in link)
            {
                if (i.Equals(key))
                {
                    return true;
                }
            }

            return false;
        }
    }
}

t.next = x.next;
x.next = t;

using System;
using Generics;

namespace _1._3._22
{
    /*
     * 1.3.22
     * 
     * 假设 x 是一条链表中的某个结点，下面这段代码做了什么？
     * 
     */
    class Program
    {
        //将 t 插入到 x 之后
        static void Main(string[] args)
        {
            Node<string> first = new Node<string>();
            Node<string> second = new Node<string>();
            Node<string> third = new Node<string>();
            Node<string> fourth = new Node<string>();

            first.item = "first";
            second.item = "second";
            third.item = "third";
            fourth.item = "fourth";

            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = null;

            Node<string> current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }

            Node<string> t = new Node<string>();
            t.item = "t";

            t.next = second.next;
            second.next = t;

            Console.WriteLine();

            current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }
        }
    }
}

x.next = t;
t.next = x.next;

using System;
using Generics;

namespace _1._3._23
{
    /*
     * 1.3.23
     * 
     * 为什么下面这段代码和上一题中的代码效果不同？
     * 
     */
    class Program
    {
        //x.next = t        x 的下一个是 t
        //t.next = x.next   t 的下一个和 x 的下一个相同（也就是 t）
        //于是 t.next = t, 遍历会出现死循环。
        static void Main(string[] args)
        {
            Node<string> first = new Node<string>();
            Node<string> second = new Node<string>();
            Node<string> third = new Node<string>();
            Node<string> fourth = new Node<string>();

            first.item = "first";
            second.item = "second";
            third.item = "third";
            fourth.item = "fourth";

            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = null;

            Node<string> current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }

            Node<string> t = new Node<string>();
            t.item = "t";

            second.next = t;
            t.next = second.next;
            
            Console.WriteLine();

            current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }
        }
    }
}

using System;
using Generics;

namespace _1._3._24
{
    /*
     * 1.3.24
     * 
     * 编写一个方法 removeAfter()，接受一个链表结点作为参数并删除该结点的后续结点。
     * （如果参数结点的后续结点为空则什么也不做）
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Node<string> first = new Node<string>();
            Node<string> second = new Node<string>();
            Node<string> third = new Node<string>();
            Node<string> fourth = new Node<string>();

            first.item = "first";
            second.item = "second";
            third.item = "third";
            fourth.item = "fourth";

            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = null;

            Node<string> current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }

            RemoveAfter(second);
            Console.WriteLine();

            current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }
        }

        static void RemoveAfter<Item>(Node<Item> i)
        {
            i.next = null;
        }
    }
}

using System;
using Generics;

namespace _1._3._25
{
    /*
     * 1.3.25
     * 
     * 编写一个方法 insertAfter()，接受两个链表结点作为参数，
     * 将第二个结点插入链表并使之成为第一个结点的后续结点
     * （如果两个参数为空则什么也不做）。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Node<string> first = new Node<string>();
            Node<string> second = new Node<string>();
            Node<string> third = new Node<string>();

            first.item = "first";
            second.item = "second";
            third.item = "third";

            first.next = second;
            second.next = null;

            Node<string> current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }

            InsertAfter(second, third);
            Console.WriteLine();

            current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }
        }

        static void InsertAfter<Item>(Node<Item> A, Node<Item> B)
        {
            if (A == null || B == null)
                return;
            B.next = A.next;
            A.next = B;
        }
    }
}

using System;
using Generics;

namespace _1._3._26
{
    /*
     * 1.3.26
     * 
     * 编写一个方法 remove()，接受一条链表和一个字符串 key 作为参数，
     * 删除链表中所有 item 域为 key 的结点。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            LinkedList<string> link = new LinkedList<string>();
            link.Insert("first", 0);
            link.Insert("second", 1);
            link.Insert("third", 2);
            link.Insert("third", 3);
            link.Insert("third", 4);

            Console.WriteLine(link);
            Remove(link, "third");
            Console.WriteLine(link);
        }

        static void Remove(LinkedList<string> link, string key)
        {
            for (int i = 0; i < link.Size(); ++i)
            {
                if (link.Find(i) == key)
                {
                    link.Delete(i);
                    i--;
                }
            }
        }
    }
}

using System;
using Generics;

namespace _1._3._27
{
    /*
     * 1.3.27
     * 
     * 编写一个方法 max()，接受一条链表的首结点作为参数，返回链表中键最大的节点的值。
     * 假设所有键均为正整数，如果链表为空则返回 0。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Node<int> first = new Node<int>();
            Node<int> second = new Node<int>();
            Node<int> third = new Node<int>();
            Node<int> fourth = new Node<int>();

            first.item = 1;
            second.item = 2;
            third.item = 3;
            fourth.item = 4;

            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = null;

            Console.WriteLine("Max:" + Max(first));
        }

        static int Max(Node<int> first)
        {
            int max = 0;

            Node<int> current = first;
            while (current != null)
            {
                if (max < current.item)
                {
                    max = current.item;
                }
                current = current.next;
            }

            return max;
        }
    }
}

using System;
using Generics;

namespace _1._3._28
{
    /*
     * 1.3.28
     * 
     * 用递归方法解答上一道练习。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Node<int> first = new Node<int>();
            Node<int> second = new Node<int>();
            Node<int> third = new Node<int>();
            Node<int> fourth = new Node<int>();

            first.item = 1;
            second.item = 2;
            third.item = 3;
            fourth.item = 4;

            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = null;

            Console.WriteLine("Max:" + Max(first));
        }

        static int Max(Node<int> first, int max = 0)
        {
            if (first == null)
                return max;
            if (max < first.item)
                return Max(first.next, first.item);
            else
                return Max(first.next, max);
        }
    }
}

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

namespace _1._3._29
{
    public class Queue<Item> : IEnumerable<Item>
    {
        private Node<Item> last;
        private int count;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Queue()
        {
            this.last = null;
            this.count = 0;
        }

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

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

        /// <summary>
        /// 返回队列中的第一个元素（但不让它出队）。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Queue underflow");
            return this.last.next.item;
        }

        /// <summary>
        /// 将一个新元素加入队列中。
        /// </summary>
        /// <param name="item">要入队的元素。</param>
        public void Enqueue(Item item)
        {
            Node<Item> oldLast = this.last;
            this.last = new Node<Item>();
            this.last.item = item;
            this.last.next = this.last;

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

        /// <summary>
        /// 将队列中的第一个元素出队并返回它。
        /// </summary>
        /// <returns></returns>
        public Item Dequeue()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Queue underflow");
            Item item = this.last.next.item;
            this.last.next = this.last.next.next;
            this.count--;
            if (IsEmpty())
                this.last = null;
            return item;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            foreach (Item item in this)
            {
                s.Append(item);
                s.Append(" ");
            }
            return s.ToString();
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new QueueEnumerator(this.last);
        }

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

        private class QueueEnumerator : IEnumerator<Item>
        {
            private Node<Item> current;
            private Node<Item> first;

            public QueueEnumerator(Node<Item> last)
            {
                this.current = new Node<Item>();
                this.current.next = last.next;
                this.first = this.current;
            }

            Item IEnumerator<Item>.Current => this.current.item;

            object IEnumerator.Current => this.current.item;

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

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

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

    public class Node<Item>
    {
        public Item item;
        public Node<Item> next;
    }
}

using System;

namespace _1._3._29
{
    /*
     * 1.3.29
     * 
     * 用环形链表实现 Queue。
     * 环形链表也是一条链表，只是没有任何结点的链接为空，且只要链表非空则 last.next 的值为 first。
     * 只能使用一个 Node 类型的实例变量（last）。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string input = "to be or not to - be - - that - - - is";
            string[] s = input.Split(‘ ‘);
            Queue<string> queue = new Queue<string>();

            foreach (string n in s)
            {
                if (!n.Equals("-"))
                    queue.Enqueue(n);
                else if (!queue.IsEmpty())
                    Console.WriteLine(queue.Dequeue());
            }

            Console.WriteLine($"({queue.Size()}) left on queue");
            Console.WriteLine(queue);
        }
    }
}

using System;
using Generics;

namespace _1._3._30
{
    /*
     * 1.3.30
     * 
     * 编写一个函数，接受一条链表的首结点作为参数，
     * （破坏性地）将链表反转并返回链表的首结点。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Node<string> first = new Node<string>();
            Node<string> second = new Node<string>();
            Node<string> third = new Node<string>();
            Node<string> fourth = new Node<string>();

            first.item = "first";
            second.item = "second";
            third.item = "third";
            fourth.item = "fourth";

            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = null;

            Node<string> current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }

            first = Reverse(first);
            Console.WriteLine();

            current = first;
            while (current != null)
            {
                Console.Write(current.item + " ");
                current = current.next;
            }
        }

        //使用书中的递归方式实现
        static Node<Item> Reverse<Item>(Node<Item> first)
        {
            if (first == null)
                return null;
            if (first.next == null)
                return first;
            Node<Item> second = first.next;
            Node<Item> rest = Reverse(second);
            second.next = first;
            first.next = null;
            return rest;
        }
    }
}

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

namespace _1._3._31
{
    /*
     * 1.3.31
     * 
     * 实现一个嵌套类 DoubleNode 用来构造双向链表，
     * 其中每个结点都含有一个指向前驱元素的应用和一项指向后续元素的引用（如果不存在则为 null）。
     * 为以下任务实现若干静态方法：
     * 在表头插入结点。
     * 在表尾插入结点。
     * 从表头删除结点。
     * 从表尾删除结点。
     * 在指定结点之前插入新结点。
     * 在指定结点之后插入新结点。
     * 删除指定结点。
     * 
     */
    public class DoubleLinkList<Item> : IEnumerable<Item>
    {
        private class DoubleNode<T>
        {
            public T item;
            public DoubleNode<T> prev;
            public DoubleNode<T> next;
        }
        DoubleNode<Item> first;
        DoubleNode<Item> last;
        int count;

        /// <summary>
        /// 建立一条双向链表。
        /// </summary>
        public DoubleLinkList()
        {
            this.first = null;
            this.last = null;
            this.count = 0;
        }

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

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

        /// <summary>
        /// 在表头插入一个元素。
        /// </summary>
        /// <param name="item">要插入的元素。</param>
        public void InsertFront(Item item)
        {
            DoubleNode<Item> node = new DoubleNode<Item>()
            {
                item = item,
                next = this.first,
                prev = null
            };
            if (this.first != null)
            {
                this.first.prev = node;
            }
            else
            {
                this.last = node;
            }
            this.first = node;
            this.count++;
        }

        /// <summary>
        /// 在表尾插入一个元素。
        /// </summary>
        /// <param name="item">要插入表尾的元素。</param>
        public void InsertRear(Item item)
        {
            DoubleNode<Item> node = new DoubleNode<Item>()
            {
                item = item,
                next = null,
                prev = last
            };
            if (this.last != null)
            {
                this.last.next = node;
            }
            else
            {
                this.first = node;
            }
            this.last = node;
            this.count++;
        }

        /// <summary>
        /// 检索指定下标的元素。
        /// </summary>
        /// <param name="index">要检索的下标。</param>
        /// <returns></returns>
        public Item At(int index)
        {
            if (index >= count || index < 0)
                throw new IndexOutOfRangeException();

            DoubleNode<Item> current = this.first;
            for (int i = 0; i < index; ++i)
            {
                current = current.next;
            }
            return current.item;
        }

        /// <summary>
        /// 返回指定下标的结点。
        /// </summary>
        /// <param name="index">要查找的下标。</param>
        /// <returns></returns>
        private DoubleNode<Item> Find(int index)
        {
            if (index >= count || index < 0)
                throw new IndexOutOfRangeException();

            DoubleNode<Item> current = this.first;
            for (int i = 0; i < index; ++i)
            {
                current = current.next;
            }
            return current;
        }

        /// <summary>
        /// 在指定位置之前插入一个元素。
        /// </summary>
        /// <param name="item">要插入的元素。</param>
        /// <param name="index">插入位置的下标。</param>
        public void InsertBefore(Item item, int index)
        {
            if (index == 0)
            {
                InsertFront(item);
                return;
            }

            if (index >= count || index < 0)
                throw new IndexOutOfRangeException();

            DoubleNode<Item> current = Find(index);
            DoubleNode<Item> node = new DoubleNode<Item>()
            {
                next = current,
                prev = current.prev,
                item = item
            };
            current.prev.next = node;
            current.prev = node;
            this.count++;
        }

        /// <summary>
        /// 在指定位置之后插入一个元素。
        /// </summary>
        /// <param name="item">要插入的元素。</param>
        /// <param name="index">查找元素的下标。</param>
        public void InsertAfter(Item item, int index)
        {
            if (index == count - 1)
            {
                InsertRear(item);
                return;
            }

            if (index >= count || index < 0)
                throw new IndexOutOfRangeException();

            DoubleNode<Item> current = Find(index);
            DoubleNode<Item> node = new DoubleNode<Item>()
            {
                prev = current,
                next = current.next,
                item = item
            };
            current.next.prev = node;
            current.next = node;
            this.count++;
        }

        /// <summary>
        /// 删除表头元素。
        /// </summary>
        /// <returns></returns>
        public Item DeleteFront()
        {
            if (IsEmpty())
                throw new InvalidOperationException("List underflow");

            Item temp = this.first.item;
            this.first = this.first.next;
            this.count--;
            if (IsEmpty())
            {
                this.last = null;
            }
            return temp;
        }

        /// <summary>
        /// 删除表尾的元素。
        /// </summary>
        /// <returns></returns>
        public Item DeleteRear()
        {
            if (IsEmpty())
                throw new InvalidOperationException("List underflow");

            Item temp = this.last.item;
            this.last = this.last.prev;
            this.count--;
            if (IsEmpty())
            {
                this.first = null;
            }
            else
            {
                this.last.next = null;
            }
            return temp;
        }

        /// <summary>
        /// 删除指定位置的元素。
        /// </summary>
        /// <param name="index">要删除元素的下标。</param>
        /// <returns></returns>
        public Item Delete(int index)
        {
            if (index < 0 || index >= this.count)
                throw new IndexOutOfRangeException();

            if (index == 0)
            {
                return DeleteFront();
            }

            if (index == count - 1)
            {
                return DeleteRear();
            }

            DoubleNode<Item> current = Find(index);
            Item temp = current.item;
            current.prev.next = current.next;
            current.next.prev = current.prev;
            count--;
            return temp;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();

            foreach (Item i in this)
            {
                s.Append(i.ToString());
                s.Append(" ");
            }

            return s.ToString();
        }

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

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

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

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

            Item IEnumerator<Item>.Current => current.item;

            object IEnumerator.Current => current.item;

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

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

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

using System;

namespace _1._3._31
{
    class Program
    {
        static void Main(string[] args)
        {
            DoubleLinkList<string> linklist = new DoubleLinkList<string>();
            linklist.InsertRear("fourth");
            linklist.InsertFront("first");
            linklist.InsertAfter("second", 0);
            linklist.InsertBefore("third", 2);

            Console.WriteLine(linklist);

            linklist.DeleteFront();
            Console.WriteLine(linklist);
            linklist.DeleteRear();
            Console.WriteLine(linklist);
            linklist.Delete(1);
            Console.WriteLine(linklist);

            Console.WriteLine(linklist.At(0)); 
        }
    }
}

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

namespace _1._3._32
{
    //API:
    //public class Steque<Item> : Ienumerable<Item>
    //    public Steque(); 默认构造函数。
    //    public bool IsEmpty(); 检查 Steque 是否为空。
    //    public int Size(); 返回 Steque 中的元素数量。
    //    public void Push(Item item); 向 Steque 中压入一个元素。
    //    public Item Pop(); 从 Steque 中弹出一个元素。
    //    public void Peek(); 返回栈顶元素（但不弹出它）。
    //    public void Enqueue(Item item); 将一个元素添加入 Steque 中。

    public class Steque<Item> : IEnumerable<Item>
    {
        private Node<Item> first;
        private Node<Item> last;
        private int count;

        private class Node<T>
        {
            public T item;
            public Node<T> next;
        }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Steque()
        {
            this.first = null;
            this.count = 0;
        }

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

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

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(Item item)
        {
            Node<Item> oldFirst = first;
            this.first = new Node<Item>();
            this.first.item = item;
            this.first.next = oldFirst;

            if (oldFirst == null)
            {
                this.last = this.first;
            }
            count++;
        }

        /// <summary>
        /// 将一个元素从栈中弹出，返回弹出的元素。
        /// </summary>
        /// <returns></returns>
        public Item Pop()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            Item item = first.item;
            first = first.next;
            count--;
            if (count == 0)
            {
                this.last = null;
            }
            return item;
        }

        /// <summary>
        /// 将一个元素加入队列中。
        /// </summary>
        /// <param name="item">要入队的元素。</param>
        public void Enqueue(Item item)
        {
            Node<Item> oldLast = this.last;
            this.last = new Node<Item>();
            this.last.item = item;
            this.last.next = null;
            if (IsEmpty())
                this.first = this.last;
            else
                oldLast.next = this.last;
            count++;
        }

        /// <summary>
        /// 返回栈顶元素（但不弹出它）。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            return first.item;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            foreach (Item n in this)
            {
                s.Append(n);
                s.Append(‘ ‘);
            }
            return s.ToString();
        }

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

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

        private class StackEnumerator : IEnumerator<Item>
        {
            private Node<Item> current;
            private Node<Item> first;

            public StackEnumerator(Node<Item> first)
            {
                this.current = new Node<Item>();
                this.current.next = first;
                this.first = this.current;
            }

            Item IEnumerator<Item>.Current => current.item;

            object IEnumerator.Current => current.item;

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

            bool IEnumerator.MoveNext()
            {
                if (this.current.next == null)
                    return false;

                this.current = this.current.next;
                return true;
            }

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

using System;

namespace _1._3._32
{
    /*
     * 1.3.32
     * 
     * Steque
     * 一个以栈为目标的队列（或称 steque），
     * 是一种支持 push、pop 和 enqueue 操作的数据类型。
     * 为这种抽象数据类定义一份 API 并给出一份基于链表的实现。
     * 
     */
    class Program
    {
        //见 Steque.cs
        static void Main(string[] args)
        {
            Steque<string> steque = new Steque<string>();
            steque.Push("first");
            steque.Push("second");
            steque.Push("third");
            steque.Enqueue("fourth");
            Console.WriteLine(steque.ToString());
            steque.Pop();
            steque.Pop();
            steque.Pop();
            steque.Pop();
            Console.WriteLine(steque.ToString());
            steque.Enqueue("first");
            steque.Push("zero");
            Console.WriteLine(steque.ToString());
        }
    }
}

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;
            }
        }
    }
}

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;
            }
        }
    }
}

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();
        }
    }
}

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

namespace _1._3._34
{
    public class RandomBag<Item> : IEnumerable<Item>
    {
        private Item[] bag;
        private int count;

        /// <summary>
        /// 建立一个随机背包。
        /// </summary>
        public RandomBag()
        {
            this.bag = new Item[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="item">要向背包中添加的元素。</param>
        public void Add(Item item)
        {
            if (this.count == this.bag.Length)
            {
                Resize(this.count * 2);
            }

            this.bag[count] = item;
            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 < this.count; ++i)
            {
                temp[i] = this.bag[i];
            }
            this.bag = temp;
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new RandomBagEnumerator(this.bag, this.count);
        }

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

        private class RandomBagEnumerator : IEnumerator<Item>
        {
            private Item[] bag;
            private int[] sequence;
            private int current;
            private int count;

            public RandomBagEnumerator(Item[] bag, int count)
            {
                this.bag = bag;
                this.current = -1;
                this.count = count;
                this.sequence = new int[count];
                for (int i = 0; i < this.count; ++i)
                {
                    this.sequence[i] = i;
                }
                Shuffle(sequence, DateTime.Now.Millisecond);
            }

            /// <summary>
            /// 随机打乱数组。
            /// </summary>
            /// <param name="a">需要打乱的数组。</param>
            /// <param name="seed">随机种子值。</param>
            private void Shuffle(int[] a, int seed)
            {
                int N = a.Length;
                Random random = new Random(seed);
                for (int i = 0; i < N; ++i)
                {
                    int r = i + random.Next(N - i);
                    int temp = a[i];
                    a[i] = a[r];
                    a[r] = temp;
                }
            }

            Item IEnumerator<Item>.Current => this.bag[this.sequence[this.current]];

            object IEnumerator.Current => this.bag[this.sequence[this.current]];

            void IDisposable.Dispose()
            {
                this.bag = null;
                this.sequence = 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;
            }
        }
    }
}

using System;

namespace _1._3._35
{
    public class RandomQueue<Item>
    {
        private Item[] queue;
        private int count;

        /// <summary>
        /// 新建一个随机队列。
        /// </summary>
        public RandomQueue()
        {
            this.queue = new Item[2];
            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)
        {
            if (capacity <= 0)
            {
                throw new ArgumentException();
            }

            Item[] temp = new Item[capacity];
            for (int i = 0; i < this.count; ++i)
            {
                temp[i] = this.queue[i];
            }

            this.queue = temp;
        }

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

            this.queue[this.count] = item;
            this.count++;
        }

        /// <summary>
        /// 从队列中随机删除并返回一个元素。
        /// </summary>
        /// <returns></returns>
        public Item Dequeue()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Random random = new Random(DateTime.Now.Millisecond);
            int index = random.Next(this.count);

            Item temp = this.queue[index];
            this.queue[index] = this.queue[this.count - 1];
            this.queue[this.count - 1] = temp;

            this.count--;

            if (this.count < this.queue.Length / 4)
            {
                Resize(this.queue.Length / 2);
            }

            return temp;
        }

        /// <summary>
        /// 随机返回一个队列中的元素。
        /// </summary>
        /// <returns></returns>
        public Item Sample()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Random random = new Random();
            int index = random.Next(this.count);

            return this.queue[index];
        }
    }
}

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

namespace _1._3._36
{
    public class RandomQueue<Item> : IEnumerable<Item>
    {
        private Item[] queue;
        private int count;

        /// <summary>
        /// 新建一个随机队列。
        /// </summary>
        public RandomQueue()
        {
            this.queue = new Item[2];
            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)
        {
            if (capacity <= 0)
            {
                throw new ArgumentException();
            }

            Item[] temp = new Item[capacity];
            for (int i = 0; i < this.count; ++i)
            {
                temp[i] = this.queue[i];
            }

            this.queue = temp;
        }

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

            this.queue[this.count] = item;
            this.count++;
        }

        /// <summary>
        /// 从队列中随机删除并返回一个元素。
        /// </summary>
        /// <returns></returns>
        public Item Dequeue()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Random random = new Random(DateTime.Now.Millisecond);
            int index = random.Next(this.count);

            Item temp = this.queue[index];
            this.queue[index] = this.queue[this.count - 1];
            this.queue[this.count - 1] = temp;

            this.count--;

            if (this.count < this.queue.Length / 4)
            {
                Resize(this.queue.Length / 2);
            }

            return temp;
        }

        /// <summary>
        /// 随机返回一个队列中的元素。
        /// </summary>
        /// <returns></returns>
        public Item Sample()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Random random = new Random();
            int index = random.Next(this.count);

            return this.queue[index];
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new RandomQueueEnumerator(this.queue, this.count);
        }

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

        private class RandomQueueEnumerator : IEnumerator<Item>
        {
            private int current;
            private int count;
            private Item[] queue;
            private int[] sequence;

            public RandomQueueEnumerator(Item[] queue, int count)
            {
                this.count = count;
                this.queue = queue;
                this.current = -1;

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

                Shuffle(this.sequence, DateTime.Now.Millisecond);
            }

            /// <summary>
            /// 随机打乱数组。
            /// </summary>
            /// <param name="a">需要打乱的数组。</param>
            /// <param name="seed">随机种子值。</param>
            private void Shuffle(int[] a, int seed)
            {
                int N = a.Length;
                Random random = new Random(seed);
                for (int i = 0; i < N; ++i)
                {
                    int r = i + random.Next(N - i);
                    int temp = a[i];
                    a[i] = a[r];
                    a[r] = temp;
                }
            }

            Item IEnumerator<Item>.Current => this.queue[this.sequence[this.current]];

            object IEnumerator.Current => this.queue[this.sequence[this.current]];

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

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

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

using System;
using Generics;

namespace _1._3._37
{
    /*
     * 1.3.37
     * 
     * Josephus 问题。
     * 在这个古老的问题中，N 个身陷绝境的人一致同意通过以下方式减少生存人数。
     * 他们围坐成一圈（位置记作 0 到 N-1）并从第一个人开始报数，
     * 报到 M 的人会被杀死，直到最后一个人留下来。
     * 传说中 Josephus 找到了不会被杀死的位置。
     * 编写一个 Queue 的用例 Josephus，从命令行接受 N 和 M 并打印出人们被杀死的顺序
     * （这也将显示 Josephus 在圈中的位置）。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int numOfPeople = 7;
            int callForDeath = 2;

            Queue<int> queue = new Queue<int>();
            for (int i = 0; i < numOfPeople; ++i)
            {
                queue.Enqueue(i);
            }

            while (!queue.IsEmpty())
            {
                for (int i = 0; i < callForDeath - 1; ++i)
                {
                    queue.Enqueue(queue.Dequeue());
                }
                Console.Write(queue.Dequeue() + " ");
            }
            Console.WriteLine();
        }
    }
}

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;
        }

    }
}

using System;

namespace _1._3._39
{
    class RingBuffer<Item>
    {
        private Item[] buffer;
        private int count;
        private int first;  //读指针
        private int last;   //写指针

        /// <summary>
        /// 建立一个缓冲区。
        /// </summary>
        /// <param name="N">缓冲区的大小。</param>
        public RingBuffer(int N)
        {
            this.buffer = new Item[N];
            this.count = 0;
            this.first = 0;
            this.last = 0;
        }

        /// <summary>
        /// 检查缓冲区是否已满。
        /// </summary>
        /// <returns></returns>
        public bool IsFull()
        {
            return this.count == this.buffer.Length;
        }

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

        /// <summary>
        /// 向缓冲区写入数据。
        /// </summary>
        /// <param name="item">要写入的数据。</param>
        public void Write(Item item)
        {
            if (IsFull())
            {
                throw new OutOfMemoryException("buffer is full");
            }

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

        /// <summary>
        /// 从缓冲区读取一个数据。
        /// </summary>
        /// <returns></returns>
        public Item Read()
        {
            if (IsEmpty())
            {
                throw new InvalidOperationException();
            }

            Item temp = this.buffer[this.first];
            this.first = (this.first + 1) % this.buffer.Length;
            this.count--;
            return temp;
        }
    }
}

using System;
using System.Text;

namespace _1._3._40
{
    class MoveToFront<Item>
    {
        private class Node<T>
        {
            public T item;
            public Node<T> next;
        }

        private Node<Item> first;
        private int count;

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

        /// <summary>
        /// 建立一个前移编码组。
        /// </summary>
        public MoveToFront()
        {
            this.first = null;
            this.count = 0;
        }

        /// <summary>
        /// 找到相应元素的前驱结点。
        /// </summary>
        /// <param name="item">要寻找的元素。</param>
        /// <returns></returns>
        private Node<Item> Find(Item item)
        {
            if (IsEmpty())
            {
                return null;
            }

            Node<Item> current = this.first;
            while (current.next != null)
            {
                if (current.next.item.Equals(item))
                {
                    return current;
                }
                current = current.next;
            }
            return null;
        }

        /// <summary>
        /// 前移编码插入。
        /// </summary>
        /// <param name="item">需要插入的元素。</param>
        public void Insert(Item item)
        {
            Node<Item> temp = Find(item);
            if (temp == null)
            {
                temp = new Node<Item>()
                {
                    item = item,
                    next = this.first
                };

                this.first = temp;
                this.count++;
            }
            else if (temp != null && this.count != 1)
            {
                Node<Item> target = temp.next;
                temp.next = temp.next.next;
                target.next = this.first;
                this.first = target;
            }
        }

        /// <summary>
        /// 查看第一个元素。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (this.first == null)
            {
                throw new InvalidOperationException();
            }

            return this.first.item;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            Node<Item> current = this.first;
            while (current != null)
            {
                s.Append(current.item.ToString());
                s.Append(" ");
                current = current.next;
            }

            return s.ToString();
        }
    }
}

/// <summary>
        /// 复制构造函数。
        /// </summary>
        /// <param name="r"></param>
        public Queue(Queue<Item> r)
        {
            foreach (Item i in r)
            {
                Enqueue(i);
            }
        }

/// <summary>
        /// 复制构造函数。
        /// </summary>
        /// <param name="s"></param>
        public Stack(Stack<Item> s)
        {
            if (s.first != null)
            {
                this.first = new Node<Item>(s.first);
                for (Node<Item> x = this.first; x.next != null; x = x.next)
                {
                    x.next = new Node<Item>(x.next);
                }
            }
            this.count = s.count;
        }

using System;
using System.IO;
using System.Linq;

namespace _1._3._43
{
    /*
     * 1.3.43
     * 
     * 文件列表。
     * 文件夹就是一列文件和文件夹的列表。
     * 编写一个程序，从命令行接受一个文件夹名作为参数，
     * 打印出该文件夹下的所有文件并用递归的方式在所有子文件夹的名下（缩进）列出其下的所有文件。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            //获取当前目录
            string path = Directory.GetCurrentDirectory();
            path = Directory.GetParent(path).FullName;
            path = Directory.GetParent(path).FullName;
            //获取文件
            Console.WriteLine(path + "中的所有文件");
            Search(path, 0);
        }

        static void Search(string path, int tabs)
        {
            string[] dirs = Directory.GetDirectories(path);
            string[] files = Directory.GetFiles(path);

            foreach (string p in dirs)
            {
                for (int i = 0; i < tabs; ++i)
                {
                    Console.Write("  ");
                }

                Console.WriteLine(p.Split(‘\\‘).Last());
                Search(p, tabs + 1);
            }

            foreach (string f in files)
            {
                for (int i = 0; i < tabs; ++i)
                {
                    Console.Write("  ");
                }

                Console.WriteLine(f.Split(‘\\‘).Last());
            }
        }
    }
}

using Generics;

namespace _1._3._44
{
    class Buffer
    {
        private Stack<char> leftside;
        private Stack<char> rightside;

        /// <summary>
        /// 建立一个文本缓冲区。
        /// </summary>
        public Buffer()
        {
            this.leftside = new Stack<char>();
            this.rightside = new Stack<char>();
        }

        /// <summary>
        /// 在光标位置插入字符 c。
        /// </summary>
        /// <param name="c">要插入的字符。</param>
        public void Insert(char c)
        {
            this.leftside.Push(c);
        }

        /// <summary>
        /// 删除并返回光标位置的字符。
        /// </summary>
        /// <returns></returns>
        public char Delete()
        {
            return this.leftside.Pop();
        }

        /// <summary>
        /// 将光标向左移动 k 个位置。
        /// </summary>
        /// <param name="k">光标移动的距离。</param>
        public void Left(int k)
        {
            for (int i = 0; i < k; ++i)
            {
                this.rightside.Push(this.leftside.Pop());
            }
        }

        /// <summary>
        /// 将光标向右移动 k 个位置。
        /// </summary>
        /// <param name="k">光标移动的距离。</param>
        public void Right(int k)
        {
            for (int i = 0; i < k; ++i)
            {
                this.leftside.Push(this.rightside.Pop());
            }
        }

        /// <summary>
        /// 返回缓冲区中的字符数量。
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.leftside.Size() + this.rightside.Size();
        }

        /// <summary>
        /// 将缓冲区的内容输出，这将使光标重置到最左端。
        /// </summary>
        /// <returns></returns>
        public string Getstring()
        {
            while (!leftside.IsEmpty())
            {
                this.rightside.Push(this.leftside.Pop());
            }

            return rightside.ToString();
        }
    }
}

using System;
using Generics;

namespace _1._3._45
{
    /*
     * 1.3.45
     * 
     * 栈的可生成性。
     * 假设我们的栈测试用例会进行一系列的入栈和出栈操作，
     * 序列中的整数 0, 1, ... , N - 1 （按此先后顺序排列）表示入栈操作，N个减号表示出栈操作。
     * 设计一个算法，判定给定的混合序列是否会使数组向下溢出
     * （你使用的空间量与 N 无关，即不能用某种数据结构存储所有整数）。
     * 设计一个线性时间算法判定我们的测试用例能否产生某个给定的排列
     * （这取决于出栈操作指令的出现位置）。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            //给定输入序列，判断是否会出现下溢出。
            string input = "- 0 1 2 3 4 5 6 7 8 9 - - - - - - - - -";
            Console.WriteLine(IsUnderflow(input.Split(‘ ‘)));//True
            input = "0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -";
            Console.WriteLine(IsUnderflow(input.Split(‘ ‘)));//False

            //给定输出序列，判定是否可能。
            int[] output = { 4, 3, 2, 1, 0, 9, 8, 7, 6, 5 };
            Console.WriteLine(IsOutputPossible(output));//True
            output = new int[]{ 4, 6, 8, 7, 5, 3, 2, 9, 0, 1};
            Console.WriteLine(IsOutputPossible(output));//False
        }

        /// <summary>
        /// 判断是否会出现下溢出。
        /// </summary>
        /// <param name="input">输入序列。</param>
        /// <returns></returns>
        static bool IsUnderflow(string[] input)
        {
            //记录栈中元素数量，如果元素数量小于 0 则会出现下溢出。
            int count = 0;

            foreach (string s in input)
            {
                if (count < 0)
                {
                    return true;
                }
                if (s.Equals("-"))
                {
                    count--;
                }
                else
                {
                    count++;
                }
            }

            return false;
        }

        /// <summary>
        /// 判断输出序列是否正确。
        /// </summary>
        /// <param name="output">输出序列。</param>
        /// <returns></returns>
        static bool IsOutputPossible(int[] output)
        {
            int input = 0;
            int N = output.Length;
            Stack<int> stack = new Stack<int>();

            foreach (int i in output)
            {
                //如果栈为空，则从输入序列中压入一个数。
                if (stack.IsEmpty())
                {
                    stack.Push(input);
                    input++;
                }

                //如果输入序列中的所有数都已经入栈过了，跳出循环。
                if (input == N && stack.Peek() != i)
                {
                    break;
                }

                //如果输出序列的下一个数不等于栈顶的数，那么就从输入序列中压入一个数。
                while (stack.Peek() != i && input < N)
                {
                    stack.Push(input);
                    input++;
                }

                //如果栈顶的数等于输出的数，弹出它。
                if (stack.Peek() == i)
                {
                    stack.Pop();
                }
            }

            return stack.IsEmpty();
        }
    }
}

/// <summary>
        /// 在当前队列之后附加一个队列。
        /// </summary>
        /// <param name="q1">需要被附加的队列。</param>
        /// <param name="q2">需要附加的队列（将被删除）。</param>
        public static Queue<Item> Catenation(Queue<Item> q1, Queue<Item> q2)
        {
            if (q1.IsEmpty())
            {
                q1.first = q2.first;
                q1.last = q2.last;
                q1.count = q2.count;
            }
            else
            {
                q1.last.next = q2.first;
                q1.last = q2.last;
                q1.count += q2.count;
            }

            q2 = null;
            return q1;
        }

/// <summary>
        /// 将两个栈连接。
        /// </summary>
        /// <param name="s1">第一个栈。</param>
        /// <param name="s2">第二个栈（将被删除）。</param>
        /// <returns></returns>
        public static Stack<Item> Catenation(Stack<Item> s1, Stack<Item> s2)
        {
            if (s1.IsEmpty())
            {
                s1.first = s2.first;
                s1.count = s2.count;
            }
            else
            {
                Node<Item> last = s1.first;
                while (last.next != null)
                {
                    last = last.next;
                }
                last.next = s2.first;
                s1.count += s2.count;
            }
            s2 = null;
            return s1;
        }

/// <summary>
        /// 将两个 Steque 连接。
        /// </summary>
        /// <param name="s1">第一个 Steque </param>
        /// <param name="s2">第二个 Steque （将被删除）</param>
        /// <returns></returns>
        public static Steque<Item> Catenation(Steque<Item> s1, Steque<Item> s2)
        {
            if (s1.IsEmpty())
            {
                s1.first = s2.first;
                s1.last = s2.last;
                s1.count = s2.count;
            }
            else
            {
                s1.last.next = s2.first;
                s1.count += s2.count;
            }
            s2 = null;
            return s1;
        }

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

namespace _1._3._48
{
    public class DeStack<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 leftcount;
        int rightcount;

        /// <summary>
        /// 默认构造函数，建立一个双端栈。
        /// </summary>
        public DeStack()
        {
            this.first = null;
            this.last = null;
            this.leftcount = 0;
            this.rightcount = 0;
        }

        /// <summary>
        /// 检查左侧栈是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsLeftEmpty()
        {
            return this.leftcount == 0;
        }

        /// <summary>
        /// 检查右侧栈是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsRightEmpty()
        {
            return this.rightcount == 0;
        }

        /// <summary>
        /// 返回左侧栈中元素的数量。
        /// </summary>
        /// <returns></returns>
        public int LeftSize()
        {
            return this.leftcount;
        }

        /// <summary>
        /// 返回右侧栈中元素的数量。
        /// </summary>
        /// <returns></returns>
        public int RightSize()
        {
            return this.rightcount;
        }

        /// <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.leftcount++;
        }

        /// <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.rightcount++;
        }

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

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

            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 (IsLeftEmpty())
            {
                throw new InvalidOperationException();
            }

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

            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;
            }
        }
    }
}

private class StackEnumerator : IEnumerator<Item>
        {
            private Stack<Item> s;
            private int popcount;
            private int pushcount;
            private Node<Item> current;

            public StackEnumerator(Stack<Item> s)
            {
                this.s = s;
                this.current = s.first;
                this.popcount = s.popcount;
                this.pushcount = s.pushcount;
            }

            Item IEnumerator<Item>.Current => current.item;

            object IEnumerator.Current => current.item;

            void IDisposable.Dispose()
            {
                this.current = null;
                this.s = null;
            }

            bool IEnumerator.MoveNext()
            {
                if (s.popcount != this.popcount || s.pushcount != this.pushcount)
                    throw new InvalidOperationException("Stack has been modified");

                if (this.current.next == null)
                    return false;

                this.current = this.current.next;
                return true;
            }

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