《数据结构》学习记录（6）：链栈

1、链栈

采用链表存储的栈。

1、定义链栈

#define elemType char
struct linkStNode
{     
    elemType data;		//数据域
    linkStNode *next;	//指针域
};

2、初始化链栈

void InitStack(linkStNode *&s)
{      
    s = new linkStNode;
    s->next = nullptr;
}

3、销毁链栈

void DestroyStack(linkStNode *&s)
{
    linkStNode *p = s,*q = s->next;
    while (q)
    {	
        delete p;
        p = q;
        q = p->next;
    }
    delete p;	//此时p指向尾结点，释放其空间
}

4、链栈是否为空

bool StackEmpty(linkStNode *s)
{
    return s->next == nullptr;
}

5、进栈

void Push(linkStNode *&s,elemType e)
{      
    linkStNode * p = new linkStNode;
    p->data = e;		//新建元素e对应的结点*p
    p->next = s->next;	//插入*p结点作为开始结点
    s->next = p;
}

6、出栈

bool Pop(linkStNode *&s,elemType &e)
{     
    if (!s->next)		//栈空的情况
        return false;
    linkStNode * p = s->next;			//p指向开始结点
    e = p->data;
    s->next = p->next;		//删除*p结点
    delete p;               //释放*p结点
    return true;
}

7、取栈顶元素

bool GetTop(linkStNode *s,elemType &e)
{      
    if (!s->next)	//栈空的情况
        return false;
    e = s->next->data;
    return true;
}

即“(”符号进栈，如果遇到“）”时获取栈顶元素，对比是否匹配。

bool Match(char exp[],int n)
{     
    linkStNode *st;
    InitStack(st);		      	//初始化栈
    int i = 0; 
    char e;  
    bool match = true; 
      
    while (i < n && match)	//扫描exp中所有字符
    { 
        if (exp[i] == '(')
        {
            Push(st,exp[i]);
        }
        else if (exp[i] == ')') 		//当前字符为右括号
        {      
            if (GetTop(st,e))
            {    
                if (e != '(')	   	//栈顶元素不为'('时表示不匹配
                    match = false;
                else
                    Pop(st,e);    	//将栈顶元素出栈
            }
            else 
            {
                match = false;  	//无法取栈顶元素时表示不匹配
            }
        }
        i++;			//继续处理其他字符
    }
    if (!StackEmpty(st))	
        match = false;
    
    DestroyStack(st);	     	//销毁栈
    return match;
}