三、栈：顺序栈和链式栈 java语言详解_链栈的入栈与出栈操作算法思想

（总结源自《大话数据结构》和极客时间“数据结构与算法之美”专栏，初学数据结构推荐此书，进阶学习推荐该专栏）

目录

栈

栈的顺序存储结构（JAVA语言实现）

入栈操作

出栈操作

栈的链式存储结构（C语言实现）

入栈操作

出栈操作

两栈共享空间

 

 

栈

栈（stack）是限定仅在表尾进行插入和删除操作的线性表

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。

栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

也就是说“栈”是一个有限制条件的线性表，那为什么我们不直接用数组和链表，而用这个功能更加受限制的数据结构呢？

当某个数据集合只涉及在⼀端插⼊和删除数据，并且满⾜后进先出、先进后出的特性，我们就应该⾸选“栈”这种数据结构。 

出栈只能是栈顶元素。

栈的顺序存储结构（JAVA语言实现）

既然栈只能由一端进行插入和删除，那么用哪一段呢？

下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以它作栈底。

 

//	基于数组实现的顺序栈 
public	class	ArrayStack	{
        private	String[]	items;		//数组
        private	int	count;	        	//栈中元素个数
        private	int	n;			//栈的⼤⼩
 
        //	初始化数组，申请⼀个⼤⼩为n的数组空间
        public	ArrayStack(int	n)	{
                this.items = new String[n];
                this.n = n;
                this.count = 0;
		}
    
        //入栈操作
        public	boolean	push(String item)	{下面再写}
        
        //出栈操作
        public	String	pop()	{下面在写}
 
}

 

入栈操作

进栈操作的思想就是：①将item放到下标为count的位置，②count++,指向下一个可用放入元素的位置。

// ⼊栈操作
public	boolean	push(String item){
    //数组空间不够了，直接返回false，⼊栈失败。
    if(count==n) return	false;
    //将item放到下标为count的位置，并且count加⼀
    items[count]=item;
    ++count;
    return true;
}

出栈操作

出栈操作的思想很简单：count--即可。因为再出栈的话，再取出数据以后往下减即可，而入栈的时候，会覆盖掉之前的数据。

//出栈操作
public String pop()	{
//栈为空，则直接返回null
    if (count == 0)
        return null;
//返回下标为count-1的数组元素，并且栈中元素个数count减⼀
    String tmp = items[count-1];
    --count;
    return tmp;
}

动态扩容的顺序栈：即底层采用了一个动态扩容的数组：入栈时，若数组空间不够，我们就重新申请⼀块更⼤的内存，将原来数组中数据统统拷⻉过去。由于动态扩容这个动作不时常发生，均摊了时间成本。故时间复杂度不变，为O（1）。

 

 

栈的链式存储结构（C语言实现）

我们把栈顶放在单链表的头部，删去头结点，因为栈的链式结构中不需要头结点，没有意义。

//链栈结构代码如下
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;
 
typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

入栈操作

入栈的思路：既然栈顶指针代替了头结点，那么栈顶指针肯定是要发挥作用的。

开辟一个新的结点，数据域放新的数据元素，再让它的next指向现在的栈顶指针所指的元素，随后再让栈顶指针指向新结点即可。

Status Push(LinkStack *s,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top;
    S->top=s;
    S->count++;
    return OK;
}

出栈操作

出栈思路：用一个变量p指向栈顶空间，栈顶指针下移，free掉p

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr P;
 
    if(StackEmpty(*S))
        return ERROR;
 
    *e=S->top->data;
    p=S->top;
 
    S->top=S->top->next;
    free(p);
    S->count--;
    return OK;
}

 

顺序栈与链栈的进栈和出栈都是O（1）的时间复杂度，O(1)的空间复杂度。【有人可能会问：这不是用到了内存空间么，怎么会是O（1）的空间复杂度呢？ 我们说空间复杂度，是指除了原本的数据存储空间外，算法运⾏还需要额外的存储空间。而这里的数组也好，链表也好，所占空间都是必须的，所以不能算进空间复杂度里去。】

而顺序栈长度固定，链栈有指针域，二者都存在内存空间浪费问题。

若栈的使用过程中，元素变化不可预料，时大时小，最好用链栈，若变化在可控范围内，建议用顺序栈。

 

 

两栈共享空间

栈很方便，因为不存在线性表的插入和删除时需要移动元素的问题。但它同样有缺陷，因为必须事先确定数组存储空间的大小。对于两个相同类型的栈，我们可以最大限度的利用开辟的存储空间，怎么用呢？就是我们的两栈共享！

怎么个共享法呢？共享共享，一定是多个对象共同使用同一个对象。我们知道，数组有两端，而栈只有一个栈底，那么能不能两端各安一个栈底，往数组之间延伸呢？这就是我们的两栈共享。

typedef struct
{
    SElemType data[MAXSIZE];
    int top1;  //栈1的栈顶指针
    int top2;  //栈2的栈顶指针
}SqDoubleStack;

ok,现在两个栈共享一个数组空间，那插入的时候如何知道插入到哪个栈呢？所以我们需要有个小东西来执行一个职能：插入之前告诉我，你这个元素要插入到哪个栈，即stackNumber

//插入操作
Status Push(SqDoubleStack *s,SElemType e,int stackNumber)
{
    if(S->top1+1==S->top2)
        return ERROR;  //此时栈满
 
    if(stackNumber==1)
        S->data[++S->top1]=e;   //往top1+1位置处插入元素
    else if(stackNumber==2)
        S->data[--S->top2]=e;    //往top2-1位置处插入元素
    return OK;
}

//删除操作
//若栈不空，删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
Status Pop(SqDoubleStack *S, SElemType *e,int stackNumber)
{
    if(stackNumber==1)    
    {
        if(S->top1 ==-1)
            retrun ERROR;
        *e=S->data[S->top1--];
    }
 
    if(stackNumber==2)    
    {
        if(S->top2 ==MAXSIZE)
            retrun ERROR;
        *e=S->data[S->top2++];
    }
    return OK;
}

那么有个问题来了：共享归共享，它还是在数组里面，数组还是固定大小的呀，那有什么用呢？所以呀，这种数据结构一般用于两个栈的空间需求有相反关系时，即一个增长时另一个在缩短，若两个都在不停增长，那很快就会因为栈满而溢出。