1、设计链式栈类，实现IStack<T>接口。 2、设计链式队列类，实现IQueue<T>接口 3、（附加题）编写一个程序判别读入的字符序列是否为“回文”，所谓回文就是正读和反读都相同的字符序列，例如: abcdedcba 或 abccba 是回文。

1. 设计链式栈类（IStack<T>接口实现）:

public class LinkedStack<T> : IStack<T>
{
    private Node<T> top;

    public class Node<T>
    {
        public T Value;
        public Node<T> Next;

        public Node(T value)
        {
            Value = value;
            Next = null;
        }
    }

    public void Push(T item)
    {
        var newNode = new Node<T>(item);
        newNode.Next = top;
        top = newNode;
    }

    public T Pop()
    {
        if (top == null)
            throw new InvalidOperationException("Stack is empty");
        T item = top.Value;
        top = top.Next;
        return item;
    }

    public bool IsEmpty()
    {
        return top == null;
    }

    // 其他接口方法如 Peek() 可以类似地添加，这里不再赘述
}

2. 设计链式队列类（IQueue<T>接口实现）:

public class LinkedListQueue<T> : IQueue<T>
{
    private Node<T> front;
    private Node<T> rear;

    public class Node<T>
    {
        public T Value;
        public Node<T> Next;
        public Node<T> Prev;

        public Node(T value)
        {
            Value = value;
            Next = null;
            Prev = null;
        }
    }

    public void Enqueue(T item)
    {
        var newNode = new Node<T>(item);
        if (rear == null)
        {
            front = newNode;
            rear = newNode;
        }
        else
        {
            newNode.Prev = rear;
            rear.Next = newNode;
            rear = newNode;
        }
    }

    public T Dequeue()
    {
        if (front == null)
            throw new InvalidOperationException("Queue is empty");
        T item = front.Value;
        if (front == rear) // 如果只有一个元素，同时调整 front 和 rear
            front = rear = null;
        else
        {
            front = front.Next;
            front.Prev = null;
        }
        return item;
    }

    // 其他接口方法如 Peek() 和 Count() 可以依此实现
}

3. （附加题）判断输入字符序列是否为回文：

public static bool IsPalindrome(string input)
{
    int start = 0, end = input.Length - 1;
    while (start < end)
    {
        if (input[start] != input[end])
            return false;
        start++;
        end--;
    }
    return true;
}

// 示例用法:
string sequence = "abcdedcba";
bool isPalindrome = IsPalindrome(sequence);
if (isPalindrome)
    Console.WriteLine($"'{sequence}' is a palindrome.");
else
    Console.WriteLine($"'{sequence}' is not a palindrome.");