3.5 链栈的表示和实现

链栈的表示

• 链栈是运算受限的单链表，只能在链表头部进行操作

  typedef struct StackNode{
   	SElemType data;
    Struct StackNode *next;
  }StackNode,*LinkStack;
  
  LinkStack S;
  

  我们是在头部进行操作，类似与头插法，也就是说我们将S指向栈顶元素。

1. 链表的头指针就是栈顶
2. 不需要头结点
3. 基本不存在站栈满的情况
4. 空栈相当于头指针指向空
5. 插入和删除仅在栈顶处执行

链栈的初始化

• 【算法描述】

  void InitStack(LinkStack &S){
    	// 构造一个空栈，栈顶指针置为空
    	S=null;
    	return OK;
  }
  

判断链栈是否为空

• 【算法描述】

  Status StackEmpty(LinkStack S){
    	if(S==null)
        	return TRUE;
    	else 
        	return FALSE;
  }
  

链栈的入栈

• 【算法思想】将元素压入栈中

• 【算法步骤】
  1、开辟一个新的空间，然后将数据域进行赋值
  2、将新节点的指针域指向头结点
  3、将S指向新节点即可。

• 【算法描述】

  Status  Push(LinkStack &S,SElemType &e){
    	StackNode p=new StackNode();
    	p->data=e;
    	p->next=S;
    	S=p;
    	return OK;
  }
  

链栈的出栈

• 【算法思想】将栈顶元素进行出栈

• 【算法步骤】
  1、将栈顶赋值给参数e，进行返回
  2、将S指向下一个节点
  3、将空节点进行删除

• 【算法描述】

  Status Pop(LinkStack &S,SElemType &e){
    	// 首先是要判断栈是否为空
    	if(S==null)
        	return ERROR;
    	StackNode p=S;
    	e=S->data;
    	S=S->next;
    	delete p;
    	return OK;
  }
  

取栈顶元素的值

• 【算法思想】取出栈顶元素的值

• 【算法描述】

  SElemType GetTop(LinkStack S){
    	if(!S){
        return S->data;
      }
    	return null;
  }