关于栈的那些事

1.1 栈的基本概念

栈：栈是只允许在一端进行插入或删除操作的线性表。栈是一种线性表，但限定了这种线性表只能在某一端进行插入和删除操作。

栈顶（top）：线性表允许进行插入删除的那一端
栈底（bottom）：固定的，不允许进行插入和删除的那一端
空栈：不含任何元素的空表

栈的特性：后进先出或先进后出。
栈的应用：进制转换、表达式求值、括号匹配等。

1.2 栈的顺序存储结构

1. 顺序栈的实现

采用顺序存储结构的栈称为顺序栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

栈的顺序存储结构类型描述如下：

#define MaxSize 50  //定义栈中元素的最大个数
typedef struct{
   ElemType data[MaxSize];  //存放栈中元素
   int top;  //栈顶指针
   }SqStack;  
12345

栈顶指针：S.top，初始时设置：S.top = -1，栈顶元素：S.data[S.top]
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先去栈顶元素值，再将栈顶指针减1。
栈空条件：S.top == -1，栈满条件：S.top == MaxSize-1，栈长：S.top + 1

注意：顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能会出现栈上溢出。栈和队列的判空、判断条件，根据实际给的条件不同而变化。

2. 顺序栈的基本运算

栈顶指针和栈中元素之间的关系如下图所示：
0156ba11238cf6aedc3a1d7751241d1
顺序栈常用的基本运算的代码实现如下所示：
(1)初始化

     void InitStack(SqStack &S){
         S.top = -1;  //初始化栈顶指针
     }
123

（2）判栈空

     bool StackEmpty(SqStack S){
        if(S.top == -1)  //栈空
           return true;
        else  //栈非空
           return false;
     }
123456

（3）进栈

     bool Push(SqStack &S,ElemType x){
        if(S.top == MaxSize-1) //栈满，报错
           return false;
        S.data[++S.top] = x;  //指针先加1，再入栈
        return true; 
    }
123456

（4）出栈

     bool Pop(SqStack &S,ElemType &x){
        if(S.top == -1) //栈空，报错
           return false;
        x = S.data[S.top--];  //先出栈，指针再减1
        return true; 
    }
123456

（5）读栈顶元素

      bool GetTop(SqStack S,ElemType x){
        if(S.top == -1) //栈空，报错
           return false;
         x = S.data[S.top];  // x 记录栈顶元素
        return true; 
    }
123456

仅为读取栈顶元素，并没有出栈操作，原栈顶元素依然保留在栈中。

注意：栈顶指针初始化为 S.top = -1，top 指向的是栈顶元素，进栈操作为 S.data[++S.top] = x，出栈操作为 x = S.data[S.top– ]。若栈顶指针初始化为 S.top = 0，即 top 指向栈顶元素的下一个位置，则入栈操作变为 S.data[S.top++] = x，出栈操作变为 x = S.data[- -S.top ]。相应的栈空、栈满条件也会发生变化。

4. 顺序栈示例代码

1、顺序栈的基本操作：顺序栈的初始化及其栈的入栈、出栈、查看栈中所有元素的示例代码如下所示：

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100  
#define STACKINCREMENT 10    
typedef int Status;
typedef int SElemType;
typedef struct{
    SElemType *base; 
    SElemType *top;  
    int stacksize;  
}SqStack;
Status InitStack(SqStack &S)
{
    S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base)
		exit(OVERFLOW); 
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status DestroyStack(SqStack &S)
{
    if(!S.base)
    {
        printf("不存在该栈\n");
        return OK;
    }
    free(S.base);
    return OK;
}
Status GetTop(SqStack S,SElemType &e)
{
    if(S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;
}
Status Push(SqStack &S,SElemType e)
{
    if(S.top - S.base >= S.stacksize)
    {
        S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
        if(!S.base) 
			exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
    if(S.top == S.base) return ERROR;
    e = * --S.top;
    return OK;
}
Status displayStack(SqStack S)
{
    if(S.top == S.base)
    {
        printf("该栈为空\n");
        return OK;
    }
    for(;S.top != S.base;)
    {
        printf("%d\t",*(--S.top));
    }
    printf("\n");
    return OK;
}
int main()
{
    SqStack S;
    int e;
    InitStack(S);
	printf("数据入栈:\n");
    Push(S,10);
    Push(S,20);
    Push(S,30);
	displayStack(S);
	printf("显示栈中的数据:\n");
    displayStack(S);
    GetTop(S,e);
    printf("栈顶的元素是:\n%d\n",e);
    Pop(S,e);
    printf("栈顶元素出栈:\n%d\n",e);
	printf("显示栈中的数据:\n");
    displayStack(S);
    return 0;
}

运行结果如下图所示：
在这里插入图片描述
2、顺序栈的应用：实现两个多项式的相加运算。

#include<stdio.h>  
#include<stdlib.h>   
typedef int ElemType;  

typedef struct PolynNode{  
    int coef; 
    int expn; 
    struct PolynNode *next;  
}PolynNode,*PolynList;  
void CreatePolyn(PolynList &L,int n)  
{  
    int i;  
    PolynList p,q;  
    L=(PolynList)malloc(sizeof(PolynNode));
    L->next=NULL;  
    q=L;  
    printf("成对输入%d个数据\n",n);  
    for(i=1;i<=n;i++)  
    {  
        p=(PolynList)malloc(sizeof(PolynNode));  
        scanf("%d%d",&p->coef,&p->expn);   
        q->next=p;  
        q=q->next;  
    }  
    p->next=NULL;  
}  
void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType))  
{  
    PolynList p=L->next;  
    while(p)  
    {  
        vi(p->coef, p->expn);  
        if(p->next)  
        {  
            printf(" + ");  
        }  
        p=p->next;  
    }  
    printf("\n");  
}  
void visit(ElemType c, ElemType e)   
{  
    if(c != 0)  
    {  
        printf("%dX^%d",c,e);  
    }  
}  
PolynList MergeList(PolynList La, PolynList Lb)  
{  
    PolynList pa, pb, pc, Lc;  
    pa = La->next;  
    pb = Lb->next;  
    Lc = pc = La;   
    while(pa&&pb)  
    {  
        if(pa->expn < pb->expn)          
        {                                
            pc->next = pa;             
            pc = pa;  
            pa = pa->next;             
        }  
        else if (pa ->expn > pb->expn )      
        {  
            pc->next = pb;                
            pc = pb;  
            pb = pb->next;               
        }  
        else  
        {  
            pa->coef = pa->coef + pb->coef;      
            pc->next = pa;  
            pc = pa;  
            pa = pa->next;             
            pb = pb->next;  
        }  
    }  
   
    pc->next = pa ? pa:pb;  
   
    return Lc;  
}  
   
void main()  
{  
    PolynList ha,hb,hc;  
    printf("非递减输入多项式A， ");  
    CreatePolyn(ha,5);   
   
    printf("非递减输入多项式B， ");  
    CreatePolyn(hb,5);    
   
    printf("多项式A :");  
    PolynTraverse(ha, visit);  
    printf("\n");  
    printf("多项式B :");  
    PolynTraverse(hb, visit);  
    printf("\n");  
   
    hc = MergeList(ha,hb);  
    PolynTraverse(hc, visit);  
}

在这里插入图片描述

1.3 栈的链式存储结构

采用链式存储结构的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都在单链表的表头进行。规定链栈没有头结点，LHead 指向栈顶元素，栈的链式存储结构如下图所示：
在这里插入图片描述
栈的链式存储结构类型描述如下：

typedef struct Linknode{
   ElemType data;  //数据域
   struct Linknode *next;  //指针域
}*LiStack;  //栈定义类型

采用链式存储，便于结点的插入和删除。链栈的操作和链表类似，入栈和出栈的操作都在链表的表头进行。对于带头结点和不带头结点的连载，具体的实现会有所不同。

示例代码：链栈的初始化、入链栈、获取链栈顶元素以及输出链栈所有元素的代码如下：

#include<stdio.h>
#include<stdlib.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;

typedef int Status;
typedef int ElemType;

typedef struct LinkNode
{
	ElemType data;
	struct LinkNode *next;
}*LiStack;

Status InitStack(LiStack &L)
{
	L=(struct LinkNode *)malloc(sizeof(LinkNode));
	L->next=NULL;
	return OK;
}

Status InputStack(LiStack &L,ElemType e)
{
	LiStack p;
	p=(struct LinkNode *)malloc(sizeof(LinkNode));
	p->data=e;
	p->next=L->next;
	L->next=p;
	return OK;
}

Status PrintStack(LiStack &L)
{
	LiStack p=L->next;
	while(p!=NULL)
	{
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
	return OK;
}

Status DestoryStack(LiStack &L)
{
	LiStack p;
	p=L->next;
	while(!p)
	{
		p=p->next;
		free(p);
	}
	return OK;
}

Status GetTop(LiStack &L,ElemType &e)
{
	LiStack p=L->next;
	if(p==NULL)
		return ERROR;
	e=p->data;
	return OK;
}

int main()
{
	LiStack L;
	int e;
	int e1,e2,e3;
	InitStack(L);
	printf("输入三个数据进入链栈");
	InputStack(L,10);
	InputStack(L,20);
	InputStack(L,30);
    printf("\n链栈中的数据为:\n");
	PrintStack(L);
	printf("获取栈顶数据:\n");
	GetTop(L,e);
	printf("栈顶数据为e=%d\n",e);
	printf("\n输出链栈中全部数据:\n");
	PrintStack(L);
    printf("\n初始化链栈:\n");
	DestoryStack(L);
	printf("\n");
	return OK;
}

运行结果如下图所示：
在这里插入图片描述

栈和队列