系统认识栈和队列

1.背景知识

1.栈是后进先出的，它既可以用数组，也可以用单向链表实现。
2.队列是先进先出，它既可以靠顺序表也可以用链表实现。
讲到这，我们也回顾一下顺序表和链表的对比：

有关于缓存的了解：

CPU的运行次数是非常快的，它不会直接从内存中读取数据，而会在缓存区里读取数据，所以读取数据过程是：内存中数据先加载一部分到缓存，然后CPU在缓存中读取数据。如果CPU读取的数据在缓存中，叫缓存命中，直接访问；如果不在缓存中，要要再从内存中往缓存中加载数据。而这加载数据的过程中，它会一次加载一块连续内存的数据，因此数组比链表的缓存利用率高。

2.栈

栈就是一种实现数据后进先出的数据结构，是一种特殊的线性表。
栈的实现：

下面是用数组实现栈的接口：

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>//用数组实现栈typedefintDataType;//静态栈#defineN20typedefstructStaticStack{DataType a[N];//存储数据的数组inttop;//数组栈顶元素下标的下一位intcapacity;//数组容量}StaticStack;//静态栈意义不大//动态栈typedefstructStack2{DataType*a;//存储数据的数组inttop;//数组栈顶元素下标的下一位intcapacity;//数组容量}ST;//栈的初始化voidSTInit(ST*obj);//栈的销毁voidSTDestroy(ST*obj);//栈顶进数据voidSTPush(ST*obj,DataType x);//栈顶出数据voidSTPop(ST*obj);//取出栈顶数据DataTypeSTTop(ST*obj);//栈判空boolSTEmpty(ST*obj);//栈判满boolSTFull(ST*obj);//获取数据个数intSTNum(ST*obj);

用链表实现栈：

#define_CRT_SECURE_NO_WARNINGS1#include"Stack2.h"//栈的初始化voidSTInit(ST*obj){assert(obj);obj->top=NULL;obj->size=0;}//栈的销毁voidSTDestroy(ST*obj){assert(obj);Node*cur=obj->top;while(cur){Node*next=cur->next;free(cur);cur=next;}obj->top=NULL;obj->size=0;}//栈顶进数据voidSTPush(ST*obj,DataType x){assert(obj);Node*newnode=(Node*)malloc(sizeof(Node));{if(newnode==NULL){perror("malloc");return;}}newnode->data=x;newnode->next=obj->top;obj->top=newnode;obj->size++;}//栈顶出数据voidSTPop(ST*obj){assert(obj);assert(obj->size>0);Node*ret=obj->top;free(ret);ret=NULL;obj->top=obj->top->next;obj->size--;}//取出栈顶数据DataTypeSTTop(ST*obj){assert(obj);assert(obj->size>0);returnobj->top->data;}//栈判空boolSTEmpty(ST*obj){returnobj->size==0;}////栈判满//bool STFull(ST* obj)//{// assert(obj);// return obj->top == obj->capacity;//}//获取数据个数intSTNum(ST*obj){assert(obj);returnobj->size;}

3.队列

队列是只允许在一端插入数据，在另一端删除数据的特殊线性表，先进先出。
用链表实现队列：

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//用链表实现队列typedefintDataType;//定义节点结构体typedefstructListNode{DataType data;structListNode*next;}ListNode;//定义队列结构体typedefstructQueue{ListNode*front;//头结点ListNode*rear;//尾结点}Queue;//队列初始化voidQueueInit2(Queue*obj);//队列的销毁voidQueueDestroy2(Queue*obj);//队列进数据voidQueuePush2(Queue*obj,DataType x);//队列出数据voidQueuePop2(Queue*obj);//取出队列队头元素DataTypeQueueTop2(Queue*obj);//取出队列队尾元素DataTypeQueueBack2(Queue*obj);//队列判空boolQueueEmpty2(Queue*obj);//队列数据个数intQueueNum2(Queue*obj);

#define_CRT_SECURE_NO_WARNINGS1#include"Queue2.h"//队列初始化voidQueueInit2(Queue*obj){assert(obj);obj->front=obj->rear=NULL;}//队列的销毁voidQueueDestroy2(Queue*obj){assert(obj);ListNode*cur=obj->front;while(cur){ListNode*next=cur->next;free(cur);cur=next;}obj->front=obj->rear=NULL;}//队列进数据voidQueuePush2(Queue*obj,DataType x){//尾插assert(obj);ListNode*newnode=(ListNode*)malloc(sizeof(ListNode));if(newnode==NULL){perror("malloc::QueuePush");return;}newnode->data=x;newnode->next=NULL;if(obj->front==NULL){obj->front=obj->rear=newnode;}obj->rear->next=newnode;obj->rear=newnode;}//队列出数据voidQueuePop2(Queue*obj){//头删assert(obj);assert(obj->rear);ListNode*ret=obj->front;obj->front=obj->front->next;free(ret);}//取出队列队头元素DataTypeQueueTop2(Queue*obj){returnobj->front->data;}//取出队列队尾元素DataTypeQueueBack2(Queue*obj){returnobj->rear->data;}//队列判空boolQueueEmpty2(Queue*obj){returnobj->front==NULL;}//队列数据个数intQueueNum2(Queue*obj){returnobj->rear-obj->front+1;}