一、背景

栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈）。允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”

特点 ：后进先出（LIFO）。 

链式栈：
插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针。 

二、链式栈的数据结构

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef  int  data_t ;			/*定义栈中数据元素数据类型*/
     
    
   

    

     

    
    

     

      typedef  struct  node_t
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
     data_t data ;			/*数据域*/
     
    
   

    

     

    
    

     
    struct  node_t  *next ; 		/*链接指针域*/
     
    
   

    

     

    
    

     

      }  linkstack_t ; 			                /*链栈类型定义*/
     
    
  
 

三、链式栈的相关操作

1.创建一个栈

  

   

    

     

    
    

     

      linklist stack_create()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	linklist s;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	if((s=(linklist)malloc(sizeof(listnode)))==NULL){
     
    
   

    

     

    
    

     
		puts("malloc failed");
     
    
   

    

     

    
    

     
		return NULL;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	s->next=NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return s;
     
    
   

    

     

    
    

     

      }
     
    
  
 

2.将一个元素压入(push)栈

  

   

    

     

    
    

     

      int stack_push(linklist s,datatype value)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	linklist p;
     
    
   

    

     

    
    

     
	if((p=(linklist)malloc(sizeof(listnode)))==NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		puts("malloc failed");
     
    
   

    

     

    
    

     
		return -1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	p->data = value;
     
    
   

    

     

    
    

     

      	p->next=s->next;
     
    
   

    

     

    
    

     

      	s->next = p;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

3.将一个元素从栈中弹出(pop)

  

   

    

     

    
    

     

      datatype stack_pop(linklist s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	linklist p;
     
    
   

    

     

    
    

     

      	datatype ret;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	p=s->next;
     
    
   

    

     

    
    

     

      	s->next=p->next;
     
    
   

    

     

    
    

     

      	ret=p->data;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	free(p);
     
    
   

    

     

    
    

     

      	p=NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return ret;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4.释放栈结构

  

   

    

     

    
    

     

      void stack_free(linklist s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	linklist p;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("free:");
     
    
   

    

     

    
    

     

      	p=s;
     
    
   

    

     

    
    

     
	while(p)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		s=s->next;
     
    
   

    

     

    
    

     
		printf("%d ",p->data);
     
    
   

    

     

    
    

     
		free(p);
     
    
   

    

     

    
    

     

      		p=s;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	putchar(10);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

5.其他操作(判断栈空、清空栈)

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int stack_empty(linklist s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	return (s->next==NULL ? 1:0);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void stack_free(linklist s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	linklist p;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("free:");
     
    
   

    

     

    
    

     

      	p=s;
     
    
   

    

     

    
    

     
	while(p)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		s=s->next;
     
    
   

    

     

    
    

     
		printf("%d ",p->data);
     
    
   

    

     

    
    

     
		free(p);
     
    
   

    

     

    
    

     

      		p=s;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	putchar(10);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/81088019