一、栈
1、栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
把允许插入和删除的一端称为栈顶（top)，另一端称为栈底（bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out)的线性表,简称LIFO结构。
2、栈的插入操作：叫作进栈,也称压栈、入栈示。
栈的删除操作：叫作出栈,也有的叫作弹栈。
满栈、空栈：栈顶所在位置是否存有元素
增栈、减栈：栈的增长方向
#include<head.h>
#include"stack.h"/*创建链表*/
Stack_t *create_stack()
{ Stack_t *pstack = malloc(sizeof(Stack_t));if(NULL == pstack){perror("malloc fail");return NULL;}pstack->ptop = NULL;pstack->clen = 0;return pstack;
}/*插入节点*/
int push_stack(Stack_t *pstack, Datatype data)
{SNode_t *pnode = malloc(sizeof(SNode_t));if(NULL == pnode){perror("malloc fail");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = pstack->ptop;pstack->ptop = pnode;pstack->clen++;return 0;
}/*判空*/
int is_empty_stack(Stack_t *pstack)
{return NULL == pstack->ptop;
}
/*遍历*/
void printf_stack(Stack_t *pstack)
{SNode_t *p =pstack->ptop;while(p){printf("%d",p->data);p=p->pnext;}printf("\n");
}
/*获得栈顶*/
int get_stack_top(Stack_t *pstack,Datatype *pdata)
{if(is_empty_stack(pstack)){return 0;}if(pdata != 0){*pdata = pstack->ptop->data;return 1;}return 0;
}
/*删除栈顶*/
int pop_stack(Stack_t *pstack,Datatype *pdata)
{if(is_empty_stack(pstack)){return 0;}SNode_t *p = pstack->ptop;pstack->ptop = p->pnext;if(pdata != NULL){*pdata = p->data;}free(p);pstack->clen--;return 0;}
/*清空栈*/
void clear_stack(Stack_t *pstack)
{while(!is_empty_stack(pstack)){pop_stack(pstack,NULL);}
}
/*销毁*/
void destory_stack(Stack_t *pstack)
{clear_stack(pstack);free(pstack);
}
/***********************************stack.h*********************************************/
#ifndef _STACK_H
#define _STACK_Htypedef int Datatype;typedef struct snode
{Datatype data;struct snode *pnext;
}SNode_t;typedef struct stack
{SNode_t *ptop;int clen;
}Stack_t;extern Stack_t *create_stack();
extern int push_stack(Stack_t *pstack, Datatype data);
extern int get_stack_top(Stack_t * pstack,Datatype *pdata);
extern int pop_stack(Stack_t *pstack,Datatype *pdata);
extern void clear_stack(Stack_t *pstack);
extern void destory_stack(Stack_t *pstack);
extern int is_empty_stack(Stack_t *pstack);
extern void printf_stack(Stack_t *pstack);#endif/***********************************main.c**********************************************/
#include<stdio.h>
#include"stack.h"int main(int argc, const char *argv[])
{Datatype data;Stack_t *pstack = create_stack();if(NULL == pstack){return -1;}push_stack(pstack,1);push_stack(pstack,2);push_stack(pstack,3);push_stack(pstack,4);printf_stack(pstack);get_stack_top(pstack,&data);printf("%d\n",data);printf_stack(pstack);pop_stack(pstack,&data);printf("%d\n",data);printf_stack(pstack);destory_stack(pstack);return 0;
}二、队列
1、 队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的-端称为队尾，允许删除的一端称为队头。
2、队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已,我们把它简称为链队列。 将队头指针指向链队列的头结点,队尾指针指向终端节点。
Queue_t *create_queue()
{Queue_t *pqueue = malloc(sizeof(Queue_t));if(NULL == pqueue){perror("malloc fail");return NULL;}pqueue->pfront = NULL;pqueue->prear = NULL;pqueue->clen = 0;pthread_mutex_init(&(pqueue->mutex),NULL);return pqueue;
}int is_empty_queue(Queue_t *pqueue)
{return NULL == pqueue->pfront;
}int push_queue(Queue_t *pqueue,QDataType data)
{QNode_t *pnode = malloc(sizeof(QNode_t));if(NULL == pnode){perror("malloc fail");return -1;}pnode->data = data;pnode->pnext = NULL;if(is_empty_queue(pqueue)){pqueue->pfront = pnode;pqueue->prear = pnode;}else{pqueue->prear->pnext = pnode;pqueue->prear = pnode;}pqueue->clen++;return 0;
}void printf_queue(Queue_t *pqueue)
{QNode_t *p =pqueue->pfront;while(p != NULL){printf("%3d",p->data);p = p->pnext;}printf("\n");
}int pop_queue(Queue_t *pqueue,QDataType *pdata)
{if(is_empty_queue(pqueue)){return 0;}QNode_t *p = pqueue->pfront;pqueue->pfront =p->pnext;if(pdata != NULL){*pdata = p->data;}free(p);if(NULL == pqueue->pfront){pqueue->prear = NULL;}pqueue->clen--;return 0;
}int get_queue_front(Queue_t *pqueue, QDataType *pdata)
{if(is_empty_queue(pqueue)) {return 0;}if(pdata != 0){*pdata = pqueue->pfront->data;return 1;}return 0;
}void clear_queue(Queue_t *pqueue)
{while(!is_empty_queue(pqueue)){pop_queue(pqueue,NULL);}
}
void destory_queue(Queue_t *pqueue)
{clear_queue(pqueue);free(pqueue);
}
