数据结构----栈

一丶概念

          只能在一端进行插入和删除操作的线性表（又称为堆栈），进行插入和删除操作的一端称为栈顶，另一端称为栈底

二丶特点

        先进后出 FILO first in last out
        后进先出 LIFO last in first out

三丶顺序栈

     逻辑结构：线性结构
     存储结构：顺序存储
     操作：入栈、出栈

1.创建一个空的栈

2.入栈

3.出栈

       

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct seqstack
{int maxlen;     // 数组中元素总个数datatype *data; // 指向数组的指针int top;        // 栈顶元素的下表
} seqstack_t;
seqstack_t *CreateEplist(int len)//创建一个空表
{seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));//先对结构体指针开辟堆区空间if (NULL == p)//判错{printf("Create err");return NULL;}p->maxlen = len;p->top = -1;//初始化结构体p->data = (int *)malloc(sizeof(int) * len);//对指向数组的指针开辟堆区空间if (NULL == p->data)//判错{printf("DATA err");return NULL;}return p;
}
int Isfull(seqstack_t *p)//判断结构体是否为满
{return p->top + 1 == p->maxlen;
}
int IsEmpty(seqstack_t *p)//判断结构体是否为空
{return p->top == -1;
}
int Pushdata(seqstack_t *p, int data)//输入数据，入栈
{if (Isfull(p)){printf("Seqstack is full");return -1;}p->top++;p->data[p->top] = data;return 0;
}
int show(seqstack_t *p)//输出数据，出栈
{if (IsEmpty(p)){printf("Seqstack is empty");return -1;}while (!IsEmpty(p)){p->top--;printf("%d ",p->data[p->top + 1]);}printf("\n");
}
void Clearlist(seqstack_t *p)//清空栈
{p->top = -1;
}
int main(int argc, char const *argv[])
{seqstack_t *p = CreateEplist(10);Pushdata(p, 1);Pushdata(p, 2);Pushdata(p, 3);Pushdata(p, 4);Pushdata(p, 5);show(p);printf("%d\n", p->top);printf("%d\n", p->maxlen);return 0;
}

练习：
 

1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )

      A. 1,4,3,2                B. 2,3,4,1               C. 3,1,4,2              D. 3,4,2,1

2. 下列叙述正确的是( )

     A. 线性表是线性结构
     B. 栈与队列是非线性结构 //栈只能在一端进行插入和删除操作的线性表
     C. 线性链表是非线性结构
     D. 二叉树是线性结构 //树形结构 层次关系

3. 下列关于栈叙述正确的是( )

      A.在栈中只能插入数据//栈只能在一端进行插入和删除操作的线性表，插入和删除端称为栈顶 ，另一端是栈底
      B.在栈中只能删除数据
      C.栈是先进先出的线性表
      D.栈是先进后出的线性表

四丶链式栈

        逻辑结构：线性结构

        存储结构：链式存储
        操作：入栈、出栈

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;//重定义数据类型
typedef struct seqlist
{datatype data;//数据域struct seqlist *next;//指针域
} seqlist_t;
void CreateList(seqlist_t **p)//创建一个空表
{*p = NULL;
}
int Isempty(seqlist_t *p)//判断链表是否为空
{return p == NULL;
}
int Pushlist(seqlist_t **p_top, int data)//进栈，由于需要一直让p_top指向栈的最顶端，所以需要传二级指针
{seqlist_t *p_new = (seqlist_t *)malloc(sizeof(seqlist_t));//开辟一个新的堆区空间if (NULL == p_new)//开辟失败报错{printf("push err");return -1;}p_new->data = data;//数据域等于数据p_new->next = *p_top;//指针域等于原来的栈顶*p_top = p_new;//更新栈顶return 0;
}
int Popdata(seqlist_t **p_top)//出栈
{if (Isempty(*p_top))//判断栈是否为空{printf("pushdata err\n");return -1;}seqlist_t *p_new = NULL;while (!Isempty(*p_top))//循环判断条件{p_new=*p_top;//保存地址printf("%d ", p_new->data);//出栈*p_top=p_new->next;//让p_top指向下一个地址free(p_new);//释放空间p_new=NULL;}printf("\n");
}
int Lenlinklist(seqlist_t *p)//求栈的长度
{int len=0;while(p){p=p->next;len++;}printf("栈的长度为%d\n",len);
}
void ClearList(seqlist_t **p_top)//清空栈
{while(*p_top){seqlist_t *q_del=*p_top;*p_top=(*p_top)->next;free(q_del);q_del=NULL;}
}
void GettopList(seqlist_t *p)//求栈顶的数据
{if(!Isempty(p))printf("栈顶的数据为%d\n",p->data);
}
int main(int argc, char const *argv[])
{seqlist_t *p_top;CreateList(&p_top);Pushlist(&p_top,1);Pushlist(&p_top,2);Pushlist(&p_top,3);Pushlist(&p_top,4);Pushlist(&p_top,5);Lenlinklist(p_top);GettopList(p_top);Popdata(&p_top);ClearList(&p_top);Popdata(&p_top);return 0;
}

总结：

顺序栈和链式栈的区别是什么？

     (1)存储结构不同，顺序栈相当于数组，连续的，链式栈 链表非连续的
     (2)顺序栈的长度受限制，而链栈不会