C#数据结构：顺序栈的两栈共享（双端栈）

栈的应用非常广泛，经常会出现在一个程序中需要同时使用多个栈的情况。若使用顺序栈，会因为对栈空间大小难以准确估计，从而产生有的栈溢出、有的栈空间还很空闲的情况。
为了解决这个问题，可以让多个栈共享一个足够大的数组空间，通过利用栈的动态特性来使其存储空间互相补充，这就是 多栈共享技术。

在顺序栈的共享技术中最常用的是两个栈的共享技术即 双端栈：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间 S[M]，将两个栈的栈底分别放在一维数组的两端，分别是 0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享要比两个栈分别申请 M/2 的空间利用率要高。

两个栈共享空间的示意如下图所示:

img.jpg

两栈共享定义:

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

/// <summary>
/// 顺序栈的两栈共享（双端栈）
/// </summary>
public class DqStack<T>
{
    private T[] data;//数据存储区

    private int[] top = new int[2]; ///*top[0]和 top[1]分别为两个栈顶指示器*/

   
    //初始化
    public DqStack(int size) //size:为最大容量
    {
        data = new T[size];
        top[0] = -1;  //0号栈的栈顶初值
        top[1] = size;//1号栈的栈顶初值
    }

    public DqStack() : this(10) //默认构造函数，最大容量10
    {

    }

    //最大容量
    public int MaxSize
    {
        get
        {
            return data.Length;
        }
    }

    /// <summary>
    ///  双栈整体判空
    /// </summary>
    public bool IsEmpty()
    {
        return (top[0] == -1) && (top[1] == MaxSize);
    }


    /// <summary>    
    /// 单栈判空    
    /// </summary>
    /// <param name="i">栈号:0,1</param>
    /// <returns></returns>
    public bool IsEmpty(int i) //i：栈号
    {
        bool isEmpty = false;
        switch (i)
        {
            case 0:
                isEmpty = top[0] == -1 ? true : false;
                break;
            case 1:
                isEmpty = top[1] == MaxSize ? true : false;
                break;
            default:
                throw new System.Exception(i + " 号栈不存在");
        }
        return isEmpty;
    }

    //判满
    public bool IsFull()
    {
        return top[0] + 1 == top[1];
    }



    /// <summary>
    /// 进栈
    /// </summary>
    /// <param name="item">数据</param>
    /// <param name="i">栈号</param>
    public void Push(T item, int i)
    {
        if (IsFull())
        {
            throw new System.Exception("栈已满，无法进栈！");
        }
        switch (i)
        {
            case 0:
                data[++top[0]] = item;
                break;
            case 1:
                data[--top[1]] = item;
                break;
            default:
                throw new System.Exception(i + " 号栈不存在");
        }
    }

    /// <summary>
    /// 出栈
    /// </summary>
    /// <param name="i">栈号</param>
    /// <returns></returns>
    public T Pop(int i)
    {
        if(IsEmpty(i))
        {
            throw new System.Exception(i+" 号栈空，无法出栈！");
        }

        return i == 0 ? data[top[0]--] : data[top[1]++];     
        
    }

    /// <summary>
    /// 访问栈顶元素
    /// </summary>
    /// <param name="i">栈号</param>
    /// <returns></returns>
    public T Peek(int i)
    {
        if (IsEmpty(i))
        {
            throw new System.Exception(i + " 号栈空，无法访问栈顶！");
        }

        return i == 0 ? data[top[0]] : data[top[1]];
    }

    //双栈整体的元素个素
    public int Count()
    {
        return (top[0] + 1) + (MaxSize - top[1]);
    }

    /// <summary>
    /// 单个栈的元素个数
    /// </summary>
    /// <param name="i">栈号</param>
    /// <returns></returns>
    public int Count(int i)
    {
        if(i<0||i>1)
        {
            throw new System.Exception(i + " 号栈，不存在！");
        }

        return i == 0 ? top[0] + 1 : MaxSize - top[1];
    }

    //双栈整体清空
    public void Clear()
    {
        top[0] = -1;
        top[1] = MaxSize;
    }

    /// <summary>
    /// 单个栈清空
    /// </summary>
    /// <param name="i">栈号</param>
    public void Clear(int i)
    {
        if (i < 0 || i > 1)
        {
            throw new System.Exception(i + " 号栈，不存在！");
        }
        if(i==0)
        {
            top[0] = -1;
        }
        else
        {
            top[1] = MaxSize;
        }

        
    }

}

输出结果：

img.jpg

注：

1、双栈性需要两个top索引，初始化时 top[0] = -1 ; top[1] = maxsize;

2、双栈判满条件：top[0] + 1 == top[1]

3、双栈总的元素个数：(top[0] + 1) + (maxsize - top[1])