数据结构--栈和队列

1 栈1.1 栈的结构和概念栈:一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端、称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶1.2 栈的实现//Stack.h #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef char STACKData; typedef struct Stack { STACKData* a; int top; int capacity; }ST; // 栈的初始化 void StackInit(ST* ps); //栈的销毁 void StackDestroy(ST* ps); //栈的插入 void StackPush(ST* ps, STACKData x ); //栈的弹出 void StackPop(ST* ps); //获取栈顶元素 STACKData StackTop(ST* ps); //获取栈中有效元素个数 int StackSize(ST* ps); //检测栈是否为空 bool StackEmpty(ST* ps ); //Stack.c #include Stack.h // 栈的初始化 void StackInit(ST* ps) { assert(ps); ps-a NULL; ps-capacity 0; ps-top 0; } //栈的销毁 void StackDestroy(ST* ps) { assert(ps); free(ps-a); ps-a NULL; ps-capacity ps-top 0; } //栈的插入 void StackPush(ST* ps, STACKData x) { if (ps-top ps-capacity) { int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2; ps-a(STACKData*)realloc(ps-a,sizeof(STACKData) * newcapacity); ps-capacity newcapacity; } ps-a[ps-top] x; ps-top; } //栈的弹出 void StackPop(ST* ps) { assert(ps); assert(ps-top); ps-top--; } //获取栈顶元素 STACKData StackTop(ST* ps) { assert(ps); assert(ps-top0); return ps-a[ps-top-1]; } //获取栈中有效元素个数 int StackSize(ST* ps) { assert(ps); return ps-top; } //检测栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps-top 0; }注:栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小2 队列2.1队列的结构和概念队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头2.2队列的实现//Queue.h #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int QueneData; typedef struct QueneNode { QueneData x; struct QueneNode* next; }QuNode; typedef struct Quene { QuNode* phead; QuNode* ptail; int size; }Qu; //队列初始化 void QueneInit(Qu* pq); //队尾入队列 void QuenePush(Qu* pq, QueneData x ); //队头出队列 void QuenePop(Qu* pq); //获取队列尾部元素 QueneData QueneTail(Qu* pq); //获取队列头部元素 QueneData QueneFront(Qu* pq); //获取队列里的有效个数 int QueneSize(Qu* pq); //检测队列是否为空 bool QueneEmpty (Qu* pq); //销毁队列 void QueneDestroy(Qu* pq); //Queue.c #include Quene.h //队列初始化 void QueneInit(Qu* pq) { assert(pq); pq-phead NULL; pq-ptail NULL; pq-size 0; } //队尾入队列 void QuenePush(Qu* pq, QueneData x) { QuNode* newnode (QuNode*)malloc(sizeof(QuNode)); newnode-x x; newnode-next NULL; if (pq-phead NULL) { pq-phead pq-ptail newnode; } else { pq-ptail-next newnode; pq-ptail newnode; } pq-size; } //队头出队列 void QuenePop(Qu* pq) { assert(pq); assert(pq-phead); if (pq-phead-next NULL) { free(pq-phead); pq-phead pq-ptail NULL; } else { QuNode* next pq-phead-next; free(pq-phead); pq-phead next; } pq-size--; } //获取队列尾部元素 QueneData QueneTail(Qu* pq) { assert(pq); return pq-ptail-x; } //获取队列头部元素 QueneData QueneFront(Qu* pq) { assert(pq); return pq-phead-x; } //获取队列里的有效个数 int QueneSize(Qu* pq) { assert(pq); return pq-size; } //检测队列是否为空 bool QueneEmpty(Qu* pq) { assert(pq); return pq-size 0; } //销毁队列 void QueneDestroy(Qu* pq) { assert(pq); QuNode* cur pq-phead; while (cur) { QuNode* next cur-next; free(cur); cur next; } pq-phead pq-ptail NULL; pq-size 0; }注:队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。2.3 环形队列(了解)另外扩展了解一下实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现buf[0] buf[1] buf[2] buf[3] buf[4] ↑tail ↑head 可读tail ~ head‑1 head下一次写 head1tail下一次读 tail取模% N实现环形当下标走到数组末尾回到 0。我这里直接使用定长数组来写了要是想更完美一点可以换成顺序表或者链表#pragma once #include iostream #define SIZE 1024 templateclass T struct ring_buffer { T _buffer[SIZE]; int _pw; int _pr; ring_buffer() :_pw(0) ,_pr(0) { } void RbWrite(const T val) { int i (_pw 1) % SIZE; if (i ! _pr) { _buffer[_pw] val; _pw (_pw 1) % SIZE; } else { return; } } T RbRead() { if (_pw !_pr) { T ret _buffer[_pr]; _pr (_pr 1) % SIZE; return ret; } else { return T(); } } };