栈以及队列的详细讲解

1.栈的定义以及实现栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。一般情况下实现栈有两种分为用数组实现以及用链表实现由于用数组实现可以更小代价的进行出栈以及入栈操作所以这里我们使用的是数组实现的方式。使用数组实现分为静态实现以及动态实现静态实现不太实用所以这里使用的是动态实现的栈动态栈的定义以及要实现的功能typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; //初始化 void StackInit(ST* ps); //进栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //获取栈顶元素 STDataType Stacktop(ST* ps); //获取栈的大小 int StackSize(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); //销毁栈 void StackDestroy(ST* ps);这里的top指向的是栈里面最后一个元素的后面一个位置1.1栈的初始化以及进栈和出栈操作代码如下//初始化 void StackInit(ST* ps) { ps-a NULL; ps-capacity ps-top 0; } //进栈 void StackPush(ST* ps,STDataType x) { assert(ps); if (ps-capacity ps-top) { int Newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity; STDataType* tmp realloc(ps-a, Newcapacity*sizeof(STDataType)); if (tmp NULL) { perror(realloc fail!); exit(1); } else ps-a tmp; ps-capacity Newcapacity; } ps-a[ps-top] x; } //出栈 void StackPop(ST* ps) { assert(ps ps-top0);//必须保证栈不为空才可以进行删除操作 ps-top--; }1.2获取栈顶元素获取栈的大小判断是否为空以及销毁的代码如下图//获取栈顶元素 STDataType Stacktop(ST* ps) { assert(psps-top!0); return ps-a[ps-top-1];//保证返回正确值的同时也不会改变ps-top的值 } //获取栈的大小 int StackSize(ST* ps) { assert(ps); return ps-top; } //判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps-top 0; } //销毁栈 void StackDestroy(ST* ps) { assert(ps); STDataType* tmp ps-a; free(tmp); ps-a NULL; ps-capacity ps-top 0; }2.队列的定义以及实现队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头在这里我们先定义一个结构体用于表示队列中的节点typedef struct QueueNode { struct QueueNode* next; QEDataType data; }QueueNode;然后我们再定义一个结构体用于表示这个队列typedef struct Queue { QueueNode* phead;//队头指针 QueueNode* ptail;//队尾指针 int size;//表示队列中有多少个元素 }Queue;需要实现的功能如下//初始化 void QueueInit(Queue*p); //入队 void QueuePush(Queue* p,QEDataType x); //出队 void QueuePop(Queue* p); //返回队头元素 QEDataType QueueFront(Queue* p); //返回队尾元素 QEDataType QueueBack(Queue* p); //返回队列的大小 int QueueSize(Queue* p); //判断队列是否为空 bool QueueEmpty(Queue* p); //销毁队列 void QueueDestroy(Queue* p);2.1队列的初始化入队以及出队代码实现如下//初始化 void QueueInit(Queue* p) { p-phead p-ptail NULL; p-size 0; } //入队 void QueuePush(Queue* p, QEDataType x) { assert(p); QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode)); if (newnode NULL) { perror(malloc fail!); exit(1); } newnode-data x; newnode-next NULL; if (p-phead NULL p-ptail NULL) { p-phead p-ptail newnode; } else { p-ptail-next newnode; p-ptail p-ptail-next; } p-size; } //出队 void QueuePop(Queue* p) { assert(p); assert(p-size ! 0); if (p-phead p-ptail) { free(p-phead); p-phead p-ptail NULL; p-size--; } else { QueueNode* tmp p-phead-next; free(p-phead); p-phead tmp; p-size--; } }2.2队列的返回首尾元素判空队列大小以及销毁代码//返回队头元素 QEDataType QueueFront(Queue* p) { assert(p); assert(p-size ! 0); return p-phead-data; } //返回队尾元素 QEDataType QueueBack(Queue* p) { assert(p); assert(p-size ! 0); return p-ptail-data; } //返回队列的大小 int QueueSize(Queue* p) { assert(p); return p-size; } //判断队列是否为空 bool QueueEmpty(Queue* p) { assert(p); return p-size 0; } void QueueDestroy(Queue*p) { assert(p); QueueNode* tmp; while (p-phead) { tmp p-phead-next; free(p-phead); p-phead tmp; } p-phead p-ptail NULL; p-size 0; }由于栈以及队列部分的内容比较简单需要强调的部分较少所以这一片就到这里了