c#栈和队列习题

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

3.1 比较线性表、栈和队列这三种数据结构的相同点和不同点。

栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。
队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的"限定"。

栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按"后进先出"的规则进行操作，而队列必须按"先进先出"的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。

3.2 如果进栈的元素序列为1,2,3,4，则可能得到的出栈序列有多少种？写出全部的可能序列。

首先这是个卡特兰数，有2n个人排成一队进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票可找零，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)。

对于这个例子，剧院要想总有零钱可找，那么目前进入剧院的人数中，揣着10元钞票的人数必须少于等于揣着5元钞票的，不然肯定在某个人那出现没零钱找的情况。

现在回到正题上来对于一个给定入栈序列，怎么求它的出栈序列呢？

我们可以把入栈记为1，出栈记为0.那么前缀子序列中1的个数必须大于等于0的个数，即入栈次数要大于等于出栈次数,如1 1 0 1 0 0，它的任意前缀序列中1的个数是大于等于0的个数的。

我们来看个例子:对于1 2 3这个入栈序列，1 1 0 1 0 0就是一个入栈出栈序列，第一个1代表元素1入栈，然后第二个1代表元素2入栈，然后第三个是0，代表出栈，即元素2出栈，然后第四个是1，代表元素3入栈，然后第五个是0，代表出栈，即元素3出栈，然后第六个是0，代表元素1出栈。最后1 1 0 1 0 0就代表了出栈序列2 3 1。

那么现在的问题就转换为如何求出所有符合条件的0 1序列了。其实这和以下问题相同:给定括号对数，输出所有符合要求的序列。如2对括号，输出有()()或者(())两种。1可以看成'('，0可以看成‘)’。

卡特兰数

首先是卡特兰数的定义：令h(0)=1,h(1)=1，catalan数满足递推式：

h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)。

可以根据上面的递推公式，写出递归的计算方案。

public static int Catalan(int n)
        {
            int nCount = 0;
            if ( n < 0 )
            {
                return 0;
            }
            if ( 0 == n || 1 == n )
            {
                return 1;
            }
            for (int i = 0; i < n; ++i )
            {
                nCount += Catalan(i) * Catalan(n - i - 1);
            }
            return nCount;
        }

3.3 如果进栈的元素序列为A,B,C,D,E,F，能否得到D,C,E,F,A,B和A,C,E,D,B,F的出栈序列？并说明为什么不能得到或如何得到。

D,C,E,F,A,B 不能得到，把A 和B的位置换一下可以

A,C,E,D,B,F 可以。A进栈A出栈 B进，C进，C出，D进E进，E出，D出，B出，F进F出

3.4 写出例题3-3中的precede函数和Operate函数。
3.5 写一算法将一顺序栈的元素依次取出，并打印元素值。

将栈的元素倒置呗，我们考虑将栈元素弹出后放入另一个栈，然后输出

 //  写一算法将一顺序栈的元素依次取出，并打印元素值。
        public static void ReverseStack(int _n)
        {
            if ( _n < 0 )
            {
                return;
            }
            SeqStack<int> stack = new SeqStack<int>(_n);
            SeqStack<int> revStack = new SeqStack<int>(_n);
            for (int i = 0; i < _n; ++i)
            {
                stack.Push(i+1);
            }

            for (int i = 0; i < _n; ++i )
            {
                revStack.Push(stack.Pop());
                
            }

            for (int i = 0; i < _n; ++i)
            {
                Console.WriteLine("栈的元素依次为" + revStack.Pop());
            }
        }

3.6 在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列通常都采用循环顺序队列结构？

当有数据元素入队时，队尾指示器rear加1，当有数据元素出队时，队头指示器front加1。当front=rear时，表示队列为空，队尾指示器rear到达数组的上限处而front为-1时，队列为满。

如上图再有一个数据元素入队就会出现溢出。但事实上队列中并未满，还有空闲空间，把这种现象称为“假溢出”。这是由于队列“队尾入队头出”的操作原则造成的。解决假溢出的方法是将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列。

//求循环顺序队列的长度
public int GetLength() 
{ 
    return (rear-front+maxsize) % maxsize; 
} 
//清空循环顺序队列
public void Clear() 
{ 
    front = rear = -1; 
} 
//判断循环顺序队列是否为空
public bool IsEmpty() 
{ 
    if (front == rear) 
    { 
        return true; 
    } 
    else 
    { 
        return false; 
    } 
} 
//判断循环顺序队列是否为满
public bool IsFull() 
{ 
    if ((rear + 1) % maxsize==front) 
    { 
        return true; 
    } 
    else 
    { 
        return false; 
    } 
}

View Code

//入队
        public void Enqueue(T item)
        {
            if (IsFull())
            {
                Console.WriteLine("队列已满");
                return;
            }
            data[++rear] = item;
        }
        //出队
        public T Dequeue()
        {
            T tmp = default(T);
            if (IsEmpty())
            {
                Console.WriteLine("队列为空");
                return tmp;
            }
            tmp = data[++front];
            return tmp;
        }
        //获取队头数据元素
        public T GetFront()
        {
            if (IsEmpty())
            {
                Console.WriteLine("Queue is empty!");
                return default(T);
            }
            return data[front + 1];
        }

View Code

3.7 写一算法将一链队列的元素依次取出，并打印元素值。

 public static void PrintLinkQueue(int _n)
        {
            LinkQueue<int> queue = new LinkQueue<int>();
            for (int i = 0; i < _n; ++i)
            {
                queue.Enqueue(i + 1);
                Console.WriteLine("队列的元素依次为" + queue.Dqueue());
            }
        }