数据结构-DAY05

一、栈的概念
1.栈是限定仅在表尾进行插入和删除操作的线性表。先进后出、后进先出
        栈顶:允许操作的一端
        栈底:不允许操作的一端入栈，出栈。
        栈分为：顺序栈 链式栈
2.栈结构是在堆区创建的
3.优先级就是通过栈来解决的
先进后出，后进先出。

二、队列的概念
1.队列是只允许在一段进行插入，而在另一端进行删除操作的线性表。
        允许插入的称谓队尾，允许删除的一端队头。
        队列分为：顺序队列，循环队列，
        常用操作：出队、入队。
        先进先出，FIFO
2.满队：尾 + 1 = 头
3.空队：尾 = 头
4.队列又叫缓冲

三、练习与例题
1.创建栈

LinkStack *CreateLinkStack()
{LinkStack *ls = (LinkStack *)malloc(sizeof(LinkStack));if(NULL == ls){fprintf(stderr, "CreateLinkStack malloc");return NULL;}ls->top = NULL;ls->clen = 0; return ls;
}

2.入栈（头插法）

int PushLinkStack(LinkStack *ls, DATATYPE *data) //入栈
{LinkStackNode *newnode = (LinkStackNode *)malloc(sizeof(LinkStackNode));if(NULL == ls){fprintf(stderr, "CreateLinkStack malloc");return 1;}int len = GetSizeLinkStack(ls);memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->next = ls->top;ls->top = newnode;ls->clen++;return 0;
}

3.销毁栈区

int DestoryLinkStack(LinkStack *ls)
{LinkStackNode *tmp = ls->top;while(tmp){ls->top = ls->top->next;free(tmp);tmp = ls->top;}free(ls);return 0;
}

4.获取栈区的内容

DATATYPE *GetTopLinkStack(LinkStack *ls)
{if(IsEmptyLinkStack(ls)){return NULL;}return &ls->top->data;
}

5.出栈（头删）

int PopSeqStack(LinkStack *ls) // 头删
{if(IsEmptyLinkStack(ls)){return 1;}LinkStackNode *tmp = ls->top;ls->top = ls->top->next;free(tmp);ls->clen--;return 0;
}

6.主函数运行

int main(int argc, char *argv[])
{LinkStack *ls = CreateLinkStack();DATATYPE data[] = {{"maodan", 'F', 20, 80},  {"xiaofan", 'M', 21, 83},{"jett", 'F', 22, 83},   {"viper", 'M', 40, 90},{"runa", 'M', 41, 92}, {"gpw", 'F', 32, 63},};int i;for(i = 0; i < 6; ++i){PushLinkStack(ls, &data[i]);} int len = GetSizeLinkStack(ls);for(i = 0; i < len; ++i){DATATYPE *tmp = GetTopLinkStack(ls);printf("%s %c %d %d\n",tmp->name,tmp->sex,tmp->age,tmp->score);PopSeqStack(ls);}DestoryLinkStack(ls);ls = NULL;return 0;
}

7.队列为空

int IsEmptySeqQue(SeqQueue *sq)
{ return sq->head == sq->tail; 
}

8.队列为满

int IsFullSeqQue(SeqQueue *sq) 
{ return (sq->tail + 1) % sq->tlen == sq->head; 
}

9.入队

int EnterSeqQue(SeqQueue *sq, DATATYPE *data) 
{if (IsFullSeqQue(sq)) {fprintf(stderr, "EnterSeqQue full\n");return 1;}memcpy(&sq->array[sq->tail], data, sizeof(DATATYPE));sq->tail = (sq->tail + 1) % sq->tlen;return 0;
}

10.销毁队列

int DestroySeqQue(SeqQueue *sq) 
{free(sq->array);free(sq);return 0;
}

11.创建队列

SeqQueue *CreateSeqQue(int len) 
{SeqQueue *sq = (SeqQueue *)malloc(sizeof(SeqQueue));if (NULL == sq) {fprintf(stderr, "CreateSeqQue malloc\n");return NULL;}sq->array = malloc(sizeof(DATATYPE) * len);if (NULL == sq->array) {fprintf(stderr, "CreateSeqQue malloc\n");return NULL;}sq->head = 0;sq->tail = 0;sq->tlen = len ;return sq;
}