九一人才网找工作赣州,杭州网站推广优化公司,建设 网站,网站建设需求分析的实施文章目录 栈的概念和结构栈的实现栈的数据结构栈的初始化和销毁出栈和入栈获取栈顶、大小#xff0c;判空 队列的概念和结构队列的实现队列的数据结构队列的初始化和销毁队列的插入 队列的删除获取队头和队尾的数据获取队列长度和判空 栈和队列的一些题目1.有效的括号2.用队列… 文章目录 栈的概念和结构栈的实现栈的数据结构栈的初始化和销毁出栈和入栈获取栈顶、大小判空 队列的概念和结构队列的实现队列的数据结构队列的初始化和销毁队列的插入 队列的删除获取队头和队尾的数据获取队列长度和判空 栈和队列的一些题目1.有效的括号2.用队列实现栈3.用栈实现队列4.设计循环队列 栈的概念和结构
栈是一种常见的数据结构它遵循后进先出LIFOLast In First Out的原则。进行数据插入和操作的一端称为栈顶另一端称为栈底。 压栈栈的插入操作被称为压栈/进栈/入栈入数据在栈顶。 出栈栈的删除操作。出数据也在栈顶
栈的实现
栈可以用数组或者是链表来实现这里将使用数组来实现因为数组在插入删除时消耗代价较小对于链表由于Top放在尾删除时还需要由头指针循环遍历找到尾结点前一个
栈的数据结构
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;a为存储数据的数组top表示栈顶capacity表示当前数组的存储容量 栈的初始化和销毁
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void STDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;}assertps验证的是传过来的地址地址为NULL那就无法进行操作 free完ps-a记得置空 出栈和入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//满扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp realloc(ps-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(Stack fail);exit(-1);}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;}这里的Top是放在最后一位元素之后的 当出栈时不用管那个位置的内容和空间是否被删除当下次入栈到这个位置内容会被顶替而如果用free掉这一块空间会造成只释放部分空间的错误 获取栈顶、大小判空
STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top0;
}对于数据结构来说即使是简单的操作也要用函数进行封装这样做的原因能够找出一些错误的操作能够方便别人的操作 例如你在主函数创建的栈为空然后给到别人使用别人不知道栈为空别人没有用函数判断栈的大小出来的栈的大小无法辨别是对的还是错误的而创建函数就能够避免一些极端问题 接下来我们简单的验证一下
void Test1()
{ST st;STInit(st);STPush(st, 1);STPush(st, 2);STPush(st, 3);STPush(st, 4);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}printf(\n);STDestory(st);
}int main()
{Test1();return 0;
}队列的概念和结构
队列只允许在一端进行插入操作在另一端删除数据操作的特殊线性表具有先进先出FIFO(First In First Out) 入队列在队尾进行插入的操作 出队列在队头进行删除的操作
队列的实现
队列的实现可以用数组和链表来实现这里将使用链表来实现因为如果使用数组的结构在数组头进行删除出数据效率比较低
队列的数据结构
typedef int QDataType;
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;这里先用一个结构体将一个结点的类型进行封装然后再用一个结构体进行队列的封装因为这里我们将会使用队头和队尾如果使用这两个进行传参将会用到二级指针比较麻烦所以就使用一个结构体进行封装用结构体进行传参用到队头和队尾只需调用结构体的成员 队列的初始化和销毁
void QueneInit(Quene* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
void QueneDestory(Quene* pq)
{assert(pq);QNode* cur pq -head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}初始化将head和tail都置空size统计多少个结点 销毁用循环遍历逐渐将结点释放最后将指针置空 队列的插入
void QuenePush(Quene* pq, QDataType x)
{assert(pq);//扩容QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;//第一个插入if (pq-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}首先是每插入一次就扩容一个结点接着是判断是否为第一个结点的插入如果是需要将head和tail都等于新节点最后将size加加 队列的删除
void QuenePop(Quene* pq)
{assert(pq);//判断是否没有数据assert(!QueneEmpty(pq));QNode* next pq-head-next;//只有一个数据if (pq-head-next NULL){free(pq-head);pq-head pq-tail next;}else{free(pq-head);pq-head next;}pq-size--;}我们需要判断有没有结点可以删除然后记住头结点的下一个结点删除头结点后将头结点指针等于下一个结点如果只有一个结点可以删除那么还要将tail置空 获取队头和队尾的数据
QDataType QueneFront(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq-head-data;
}
QDataType QueneBack(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq-tail-data;
}获取队列长度和判空
int QueneSize(Quene* pq)
{assert(pq);return pq-size;
}
bool QueneEmpty(Quene* pq)
{assert(pq);return pq-head NULL;
}最后做一下简单的验证
void Test1()
{Quene q;QueneInit(q);QuenePush(q, 1);QuenePush(q, 2);QuenePush(q, 3);QuenePop(q);while (QueneSize(q)0){printf(%d , QueneBack(q));QuenePop(q);}QueneDestory(q);}int main()
{Test1();return 0;
}栈和队列的一些题目
1.有效的括号 思路这道题可以采用栈这种结构来解决问题满足后进先出的原理 我们可以这么做分为左括号和右括号遇到左括号就放入栈中一旦遇到右括号我们可以将栈顶取出进行判断这是我们的大体思路 这道题我们还需要考虑一些极端情况 第一种字符串中只有右括号或者说一开始就是右括号那么这种就相当于栈为空当遇到右括号时需要先进行判断 第二种字符串只有左括号那么表明栈中的元素没有进行匹配出栈栈不为空 所以把特殊情况弄好后就可以进行操作了我们可以把我们写的栈结构复制到程序中然后创建一个栈来进行操作最后记得释放空间避免内存泄漏 代码
#define _CRT_SECURE_NO_WARNINGS 1typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void STDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp realloc(ps-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(Stack fail);exit(-1);}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;}STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top0;
}bool isValid(char * s){ST st;//栈初始化STInit(st);while(*s){//左括号就入栈if(*s(||*s[||*s{){STPush(st,*s);}//右括号就出栈判断else{栈空表明没有左括号if(STEmpty(st)){STDestory(st);return false;}char valSTTop(st);STPop(st);//不符合if((*s)val!()||(*s]val![)||(*s}val!{)){return false;}}s;}if(!STEmpty(st)){return false;}STDestory(st);return true;
}2.用队列实现栈 思路我们可以在纸上模拟一下入栈和出栈的操作 由于入栈的时候和队列的性质一样都在尾插入所以不需要执行什么操作出栈时总需要进行转移才能删除最后一个元素那么可以先判断那个队列空与不为空然后将不为空的进行转移到空的队列那么就可以完成出栈同时由于这样的操作入栈时如果有一个队列不为空需要将元素插入不为空的后面方便出栈的操作 代码
#includeassert.h
#includestdbool.htypedef int QDataType;
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;void QueneInit(Quene* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
void QueneDestory(Quene* pq)
{assert(pq);QNode* cur pq -head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}
void QuenePush(Quene* pq, QDataType x)
{assert(pq);//扩容QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;//第一个插入if (pq-head NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}
bool QueneEmpty(Quene* pq)
{assert(pq);return pq-headNULL;
}
int QueneSize(Quene* pq)
{assert(pq);return pq-size;
}
void QuenePop(Quene* pq)
{assert(pq);//判断是否没有数据assert(!QueneEmpty(pq));//只有一个数据if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
QDataType QueneFront(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq-head-data;
}
QDataType QueneBack(Quene* pq)
{assert(pq);assert(!QueneEmpty(pq));return pq-tail-data;
}typedef struct {Quene q1;Quene q2;
} MyStack;
//创建一个自己的栈//用一个结构体进行包装
MyStack* myStackCreate() {MyStack* objmalloc(sizeof(MyStack));QueneInit(obj-q1);QueneInit(obj-q2);return obj;
}//插入判断哪个队列不为空
void myStackPush(MyStack* obj, int x) {if(!QueneEmpty(obj-q2)){QuenePush(obj-q2,x);}else{QuenePush(obj-q1,x);}
}//将队列分为空队列和不空队列
int myStackPop(MyStack* obj) {Quene* emptyobj-q1;Quene* nonemptyobj-q2;if(!QueneEmpty(obj-q1)){emptyobj-q2;nonemptyobj-q1;}//数据转移while(QueneSize(nonempty)1){QuenePush(empty,QueneFront(nonempty));QuenePop(nonempty);}//删除数据并返回int TopQueneFront(nonempty);QuenePop(nonempty);return Top;
}int myStackTop(MyStack* obj) {if(!QueneEmpty(obj-q2)){return QueneBack(obj-q2);}else{return QueneBack(obj-q1);}
}bool myStackEmpty(MyStack* obj) {return QueneEmpty(obj-q1)QueneEmpty(obj-q2);
}void myStackFree(MyStack* obj) {QueneDestory(obj-q1);QueneDestory(obj-q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj myStackCreate();* myStackPush(obj, x);* int param_2 myStackPop(obj);* int param_3 myStackTop(obj);* bool param_4 myStackEmpty(obj);* myStackFree(obj);
*/3.用栈实现队列 思路一样的我们先在纸上模拟 如果再继续删除那么可以删除到栈2为空然后就将栈1的内容全部转移到栈2如果栈2没空再插入栈1会发现没有任何影响 所以我们总结得出将栈1表示为插入的栈栈2表示为删除的栈如果要删除栈2为空就将栈1的内容转移到栈2 代码
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-top 0;ps-capacity 0;
}void STDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0;}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp realloc(ps-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(Stack fail);exit(-1);}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;}STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top0;
}//栈分为插入栈和输出栈
typedef struct {ST instack;ST outstack;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* objmalloc(sizeof(MyQueue));STInit(obj-instack);STInit(obj-outstack);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-instack,x);
}int myQueuePop(MyQueue* obj) {//先判断输出栈是否为空if(STEmpty(obj-outstack)){while(STSize(obj-instack)){STPush(obj-outstack,STTop(obj-instack));STPop(obj-instack);}}int headSTTop(obj-outstack);STPop(obj-outstack);return head;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-outstack)){while(STSize(obj-instack)){STPush(obj-outstack,STTop(obj-instack));STPop(obj-instack);}}return STTop(obj-outstack);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-instack)STEmpty(obj-outstack);
}void myQueueFree(MyQueue* obj) {STDestory(obj-instack);STDestory(obj-outstack);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj myQueueCreate();* myQueuePush(obj, x);* int param_2 myQueuePop(obj);* int param_3 myQueuePeek(obj);* bool param_4 myQueueEmpty(obj);* myQueueFree(obj);
*/4.设计循环队列 我们先根据题意确定我们将选择数组来存储固定长度然后考虑怎么让这个数组能够循环着走我们可以设置两个指针来判断由于是数组可以利用下标来进行代表指针分别为头和尾假设队列长度为k一开始头和尾下标都为0表示这个队列为空 那么当插入一个元素后尾向后走一步 删除一个元素头向后走一步 当数组填满后会发现头尾又重叠在一起与一开始队列为空情况是一样的这样就无法判断空与满了 所以我们可以再增加一个多出来的空间 当尾走到最后一个多出来的空间时就表示满 循环的尾走到最后时我们用取模来进行返回到下标为0的位置这样子就能完成我们循环的目的。 代码
typedef struct {int* a;int head;int rear;int k;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* objmalloc(sizeof(MyCircularQueue));obj-amalloc(sizeof(int)*(k1));obj-headobj-rear0;obj-kk;return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-headobj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//当rear超过k1时归0return (obj-rear1)%(obj-k1)obj-head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj-a[obj-rear]value;obj-rear;//限制在0-kobj-rear%(obj-k1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj-head;//限制在0-kobj-head%(obj-k1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj-a[obj-head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}//考虑rear-1等于-1的情况return obj-a[(obj-rearobj-k)%(obj-k1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj myCircularQueueCreate(k);* bool param_1 myCircularQueueEnQueue(obj, value);* bool param_2 myCircularQueueDeQueue(obj);* int param_3 myCircularQueueFront(obj);* int param_4 myCircularQueueRear(obj);* bool param_5 myCircularQueueIsEmpty(obj);* bool param_6 myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/这里需要注意的就是取模的问题需要记住尾和头是不断增加的是由于取模k1才限制在0-k的下标中 第一个就是在删除和插入数据的时候当头尾超出范围时需要进行取模k1的操作返回到第一个元素 第二个是判断满时尾1相当于返回到头当尾刚好处于最后下标时需要进行取模 最后一个是取尾的问题当尾刚好处于第一个下标时由于尾需要进行-1的操作才能得到尾元素所欲在第一个下标-1会导致下标变为-1所以可以多加一轮K1进行取模的操作避免这个问题
