稳重大气的公司名字_上虞网络推广_800元做小程序网站_太仓网站制作

1. 栈（Stack）

1.1 栈的概念与结构

• 栈是一种特殊的线性表，其只允许固定的一段插入和删除操作；进行数据插入和删除的一段叫做栈顶，另一端叫栈底；栈中的元素符合后进先出LIFO（Last In First Out）的原则。
• 入栈：入栈就是往栈里放入数据；
• 出栈：出栈就是从栈里拿出数据；（注意这两个操作都是对栈顶的数据进行操作）；

• 栈底层结构选型：栈的实现选用的是数组；选用链表也可以，但在插入和删除操作更方便一些；因为链表尾插需要遍历找到尾结点，那么尾插的操作时间复杂度就为O(N)，不过我们可以优化一下，拿链表的头部作为栈顶，插入和删除就为O(1)了，但是由于我们可能还需要创建多个指针进行操作，所以最优还是选择数组，因为数据的尾插和尾删时间复杂度都为O(1)，而且找到尾部的位置不需要创建什么指针啥的，因为顺序表里本身就有一个size代表数组的大小，而最后一个位置则是下标为size-1的位置；

1.2 栈的实现

       --定义栈的模型

        由于栈底层可以使用顺序表实现，那就和之前顺序表一样，需要一个计算总空间有多大的capacity和一个储存有效元素个数的top（在顺序表其实就是size，但这里为了符合栈所以用top），还有一个储存整型类型的数组，但后面会出现增容的操作所以使用指针，STDateType* arr；如下代码所示：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDatetype;typedef struct Stack
{STDatetype* arr;int capacity;  //栈空间大小int top;       //栈顶
}ST;

---

        --栈的初始化和销毁

void STInit(ST* st)
{assert(st);st->arr = NULL;st->capacity = st->top = 0;
}void STDestory(ST* st)
{assert(st);if(st->arr)free(st->arr);st->arr = NULL;st->capacity = st->top = 0;
}

---

        --入栈操作的实现

        入栈的实现：首先我们要判空间是否足够，而判断空间是否足够的条件就是栈顶是不是等于整个数组空间的容量，如果等于就需要使用realloc进行扩容，那么我们就需要创建一个Newcapacity作为扩容的空间，我们按2倍进行扩容则：2* capacity， 但是如果说capacity为0的话那么就无法进行扩容，因为0 * 任何数都等于0，所以我们写一个三目运算符，如果说capacity等于0的话就让Newcapacity等于4，否则等于2* capacity；后面我们就需要创建一个新的指针指向扩容的空间，因为如果说扩容失败的话就会对整块空间造成影响，所以我们需要创建一个新的空间进行扩容；而入栈的实现其实就是在数组最后面插入元素；代码实现如下：

void StackPush(ST* ps, STDatetype x)
{assert(ps);if (ps->capacity == ps->top  ){int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDatetype* temp = (STDatetype*)realloc(ps->arr, Newcapacity *sizeof(STDatetype) );if (temp == NULL){perror("realloc fail!");exit(1);}ps->arr = temp;ps->capacity = Newcapacity;}ps->arr[ps->top++] = x;
}

---

      

          --判断栈是否为空

        判空实现：其实就是看看栈顶是否为0，当栈顶都为0，那肯定就是没有数据了；代码实现如下：

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

---

        --出栈操作的实现

        出栈的实现：实际上其实就是顺序表进行尾删操作，那我们就直接让数组内的有效元素减少一个就可以，即size--；但是我们还需要判断栈是否为空，如果为空那就没有元素可以出；代码如下：

void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}

---

        --取栈顶元素

        取栈顶元素：取栈顶元素则是直接返回数组的尾部元素即是：ps->arr[ps->top-1]；为什么要-1？因为top是有效元素的个数，但下标的起始位置是0，所以要-1；如下代码所示：

//取栈顶元素
STDatetype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top-1];
}

---

        --获得栈中有效元素的个数

        由上可知，有效元素的个数其实就是top，所以直接返回即可；如下代码所示：

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

---

1.3 栈的完整代码

Stack.h

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDatetype;typedef struct Stack
{STDatetype* arr;int capacity;  //栈空间大小int top;       //栈顶
}ST;//首先创建这些都是要实现初始化
void STInit(ST* st);
void STDestory(ST* st);//栈顶---入数据、出数据
void StackPush(ST* ps, STDatetype x);
void StackPop(ST* ps);//取栈顶元素
STDatetype StackTop(ST* ps);bool StackEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);

Stack.cpp

#include"Stack.h"void STInit(ST* st)
{assert(st);st->arr = NULL;st->capacity = st->top = 0;
}
void STDestory(ST* st)
{assert(st);if(st->arr)free(st->arr);st->arr = NULL;st->capacity = st->top = 0;
}void StackPush(ST* ps, STDatetype x)
{assert(ps);if (ps->capacity == ps->top  ){int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDatetype* temp = (STDatetype*)realloc(ps->arr, Newcapacity *sizeof(STDatetype) );if (temp == NULL){perror("realloc fail!");exit(1);}ps->arr = temp;ps->capacity = Newcapacity;}ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
STDatetype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top-1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

---

 

2. 队列（Queue）

2.1 队列的概念与结构

• 概念：只允许在一端插入数据和从另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）；
• 入队列：进行插入操作的一端称为队尾；
• 出队列：进行删除操作的一端称为队头；
• 队列的底层结构选型：队列底层结构选的是链表，因为要进行入队列和出队列的操作，如果说用顺序表的话，在进行出队列的操作的时候删除了头部数据那就得让后面数据往前走，那时间复杂度就为O(N)，所以我们使用链表；但使用链表的时候要注意，我们需要头结点出数据实现出队列操作，尾结点入数据实现入队列操作，不然的话我们要遍历到尾结点删除数据实现出队列 时间复杂度又为O(N)了；

2.2 队列的实现

        --定义队列的模型

        队列的底层实现就是用链表来实现，那么我们就要定义结点还有队列的模型；为什么要定义两个呢？因为我们还需要一个指向头结点和指向尾结点的指针，还有一个整型size记录队列内的数据；

#pragma once
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;typedef int QDataType;
//每个结点
typedef struct QueueNode
{QDataType data;QueueNode* next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* phead;QueueNode* tail;int size;
}Queue;

---

        --队列的初始化和销毁

        队列的销毁其实就和链表的销毁一样，首先创建一个指向头结点下一个节点的next指针，然后把头结点销毁掉，在让头结点指针指向next指针，next指针再走向头结点的下一个指针，一直循环到头结点为NULL的时候结束‘；代码如下：

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->tail = NULL;pq->size = 0;
}

        --入队列的实现

        入队列的实现：需要结合链表的buynode（动态申请一个结点空间）来实现，首先我们先申请一个newnode的空间，让其指向空，data = x；再就要判断队列是否为空，如果说队列为空的话那就说明队列里面没有结点，那就需要让phead和ptail指针指向该结点，如果有结点的话就让ptail->next指针指向newnode，再让ptail走到newnode的位置，最后还要记得size++，因为size是计算队列内有效元素的个数；如下图和代码所示：

队列为空：

队列不为空：

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//说明链表为空if (pq->phead == NULL){pq->phead = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++;
}

---

        --队列判空操作

        队列判空其实就是看头结点和尾结点的指针是否都指向NULL，如果都指向NULL就为空；代码如下：

//队列判空
bool QueueEmpty(Queue* pq)
{return pq->phead == NULL && pq->tail == NULL;
}

---

        --出队列的操作

        出队列的操作本质上就是链表删除头结点；我们只需要定义一个Del指针指向当前的头结点pcur，再让当前的头结点走到头结点的下一个结点pcur = pcur->next，然后free掉Del结点即可；图和代码如下：

// 出队列，队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq->tail == pq->phead){free(pq->phead);pq->phead = NULL;pq->tail = NULL;}else{QueueNode* Del = pq->phead;pq->phead = pq->phead->next;free(Del);}--pq->size;
}

注意！！！我们还需要单独判断只有一个结点的时候，当ptail和phead都指向同一个空间的时候就代表队列中只有一个结点，那么这时候我们还进行phead = phead->next就是让phead走向一块未知的空间，进行非法访问；

---

        --取队头和队尾数据

        因为有指针指向队头和队尾，就不过多阐述了；注意一点就是我们要判断队列是否为空；代码如下所示：

//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

---

        --取队列有效元素个数

        因为我们一开始就已经创建了一个size 对队列的有效元素个数进行记录，所以直接返回size即可；如下代码所示：

//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

---

2.3 队列的完整代码

Queue.h

#pragma once
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;typedef int QDataType;
//每个结点
typedef struct QueueNode
{QDataType data;QueueNode* next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* phead;QueueNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

Queue.cpp

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//说明链表为空if (pq->phead == NULL){pq->phead = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++;
}//队列判空
bool QueueEmpty(Queue* pq)
{return pq->phead == NULL && pq->tail == NULL;
}// 出队列，队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq->tail == pq->phead){free(pq->phead);pq->phead = NULL;pq->tail = NULL;}else{QueueNode* Del = pq->phead;pq->phead = pq->phead->next;free(Del);}--pq->size;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->tail = NULL;pq->size = 0;
}

---

3.栈和队列的OJ题

3.1 有效的括号

原题链接：20. 有效的括号 - 力扣（LeetCode）

思路：我们可以创建一个栈，先把开口向右的括号全部入栈里面，当栈不为空的时候取栈顶元素；这步的操作其实就是实现当有｛【（ 这三个括号的时候能直接取到(，然后再和左开口的括号进行比较，如果说取出的栈顶元素是“(”，并且数组的下一个元素是“）”的话就是匹配上了，然后pos++；当不符合的时候直接返回false；如果不返回false一直到循环结束的时候就返回true，因为这说明全部括号都匹配上了；如下图和代码所示：

#include<stdbool.h>
typedef char STDateType;
typedef struct Stack
{STDateType* arr;int top ;int capacity;
}ST;void STInit(ST* st)
{st->arr=NULL;st->top = 0;st->capacity = 0;
}void STPush(ST* st, STDateType x)
{if(st->capacity==st->top){int Newcapacity = st->capacity==0?4:2*st->capacity;STDateType* temp = (STDateType*)realloc(st->arr, Newcapacity* sizeof(STDateType));if(temp==NULL){perror("realloc fails!");exit(1);}st->arr = temp;st->capacity = Newcapacity;}st->arr[st->top++] = x;
}bool STempty(ST* st)
{return st->top==0;
}STDateType StackTop(ST* st)
{return st->arr[st->top-1];
}void STPop(ST* st)
{assert(!STempty(st));--st->top;
}void STDestory(ST* st)
{free(st->arr);st->arr = NULL;st->capacity = 0;st->top = 0;
}bool isValid(char* s) 
{ST st;STInit(&st);char* ps = s;while(*ps!='\0'){if(*ps=='('||*ps=='{'||*ps=='['){STPush(&st, *ps);}else{if(STempty(&st)){return false;}char ch = StackTop(&st);if((*ps==')'&&ch=='(')||(*ps==']'&&ch=='[')||(*ps=='}'&&ch=='{')){STPop(&st);}else{STDestory(&st);return false;}}ps++;}bool ret = STempty(&st)==true;STDestory(&st);return ret;
}

这里还有几个需要注意的点是：

1. 当栈为空的时候就代表没有开口向右的括号，那就没有意义再进行下去了，因为没有括号可以匹配；
2. 在我们取栈顶元素比较完后要删除比较过的元素，因为取栈顶元素只是取值，并没有实现取并删；
3. 到最后我们需要判断栈是否为空，栈不为空则说明多出了一个开口向右的括号例如"{ [ ( ) ]"这样是不符合的；

---

3.2 用队列实现栈

原题链接：225. 用队列实现栈 - 力扣（LeetCode）

思路：首先我们先分析，队列是先进先出，栈是后进先出，那我们就先来使用1234进行模拟；如果把1234放到栈里面再取出来的话就是4321；

那么如果说我们想用两个队列来实现的话就得换一种思路，因为队列是先进先出，那么我们就可以尝试先把数据放到一个队列里面，然后把size-1个数据放到另一个空队列里面，再把剩下的那个数据取出来，一直这样循环；如下图所示：

typedef int QDataType;
typedef struct QueueNode 
{QDataType data;struct QueueNode* next;
}QueueNode;//队列
typedef struct Queue
{QueueNode* phead;QueueNode* tail;int size;
}Queue;
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//说明链表为空if (pq->phead == NULL){pq->phead = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->size++;
}//队列判空
bool QueueEmpty(Queue* pq)
{return pq->phead == NULL && pq->tail == NULL;
}// 出队列，队头
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//只有一个结点if (pq->tail == pq->phead){free(pq->phead);pq->phead = NULL;pq->tail = NULL;}else{QueueNode* Del = pq->phead;pq->phead = pq->phead->next;free(Del);}--pq->size;
}//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->tail = NULL;pq->size = 0;
}typedef struct 
{Queue q1;Queue q2;
} MyStack;//初始化
MyStack* myStackCreate() 
{MyStack* temp = (MyStack*)malloc(sizeof(MyStack));QueueInit(&temp->q1);QueueInit(&temp->q2);return temp;
}void myStackPush(MyStack* obj, int x) 
{//首先我们找哪个队列为空if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}elseQueuePush(&obj->q2,x);
}int myStackPop(MyStack* obj) 
{Queue* empQ = &obj->q1;Queue* noneQ = &obj->q2;if(!QueueEmpty(&obj->q1)){noneQ = &obj->q1;empQ = &obj->q2;}while(QueueSize(noneQ)>1) //大于1的原因是要留一个数据{int front = QueueFront(noneQ);QueuePush(empQ, front);QueuePop(noneQ);}int pop = QueueFront(noneQ);QueuePop(noneQ);return pop;
}int myStackTop(MyStack* obj) 
{if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) 
{   return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);   
}void myStackFree(MyStack* obj) 
{QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;}

3.3 用栈实现队列

原题链接：232. 用栈实现队列 - 力扣（LeetCode）

思路：首先我们分析，用两个栈实现队列的话，栈是先进后出，而队列是先进先出，我们使用1234来进行模拟；

队列是怎么进怎么出，1234进1234出；

那么我们来看一下首先是堆，如果说我们直接把1234放进去，再取出来的话那就是4321，但是我们通过两个堆可以改变这个先让1234入一个名为pushST的堆，然后再让pushST堆的数据堆顶数据入一个名为popST的堆，这时候popST的堆的数据就为1234了；再取出来即可；那么用栈实现队列push数据到队列末尾的则只需要直接把数据放到堆顶即可；删除数据就如刚刚上面所说，取堆顶然后把最后一个数据留下来再把该数据删除就可以实现；取队头元素的实现也是如此；判空则是看两个堆是否都为空，都为空返回1即可；如下图和代码所示：

typedef int STDatetype;typedef struct Stack
{STDatetype* arr;int capacity;  //栈空间大小int top;       //栈顶
}ST;void STInit(ST* st)
{st->arr = NULL;st->capacity = st->top = 0;
}
void STDestory(ST* st)
{if(st->arr)free(st->arr);st->arr = NULL;st->capacity = st->top = 0;
}void StackPush(ST* ps, STDatetype x)
{if (ps->capacity == ps->top  ){int Newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDatetype* temp = (STDatetype*)realloc(ps->arr, Newcapacity *sizeof(STDatetype) );if (temp == NULL){perror("realloc fail!");exit(1);}ps->arr = temp;ps->capacity = Newcapacity;}ps->arr[ps->top++] = x;
}bool StackEmpty(ST* ps)
{return ps->top == 0;
}void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
STDatetype StackTop(ST* ps)
{return ps->arr[ps->top-1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{return ps->top;
}typedef struct 
{ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pst->pushST);STInit(&pst->popST);return pst;
}void myQueuePush(MyQueue* obj, int x) 
{StackPush(&obj->pushST, x);
}int myQueuePop(MyQueue* obj) 
{if(StackEmpty(&obj->popST)){//为空就把pushST的数据放到popST里面来while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}int top = StackTop(&obj->popST);StackPop(&obj->popST);return top;
}int myQueuePeek(MyQueue* obj) 
{if(StackEmpty(&obj->popST)){while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);
}bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&obj->pushST) &&  StackEmpty(&obj->popST);
}void myQueueFree(MyQueue* obj) 
{STDestory(&obj->pushST);STDestory(&obj->popST);free(obj);obj = NULL;
}

---

END!