百度云建站教程,修改wordpress rss,如何自己做引流推广,网站网页制作企大家中秋节快乐#xff0c;玩了好几天没有学习#xff0c;今天分享的是栈以及队列的相关知识#xff0c;以及栈和队列相关的面试题 1.栈
1.1栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作… 大家中秋节快乐玩了好几天没有学习今天分享的是栈以及队列的相关知识以及栈和队列相关的面试题 1.栈
1.1栈的概念及结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 1.2栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
栈的接口函数
// 初始化栈
voidStackInit(Stack*ps);
// 入栈
voidStackPush(Stack*ps, STDataTypedata);
// 出栈
voidStackPop(Stack*ps);
// 获取栈顶元素
STDataTypeStackTop(Stack*ps);
// 获取栈中有效元素个数
intStackSize(Stack*ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0 intStackEmpty(Stack*ps);
// 销毁栈
voidStackDestroy(Stack*ps); 栈的实现
#include stdio.h
#include assert.h
#include stdlib.htypedef struct Stack//定义一个栈的结构体变量
{int * a;int top; // 栈顶int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{assert(ps);//断言防止为空指针ps-a NULL;//所指向的地址为空ps-capacity ps-top 0;//容量和栈中元素个数均为0
}
void StackPush(Stack* ps, int data)
{assert(ps);if (ps-capacity ps-top)//如果栈中的元素个数等于栈的容量时考虑扩容{int newcapcity ps-capacity 0 ? 4 : ps-capacity * 2;//如果刚开始时都等于0就先给4个空间大小后面如果满的话容量扩大1倍int* newnode (int*)realloc(ps-a,sizeof(int)* newcapcity);//申请空间将申请好的空间首地址传给newnode指针assert(newnode);//断言防止malloc失败ps-a newnode;//将newnode保存的申请空间的首地址传给ps-a,让ps-a指向创建好的空间ps-capacity newcapcity;//容量大小更新为新容量大小}ps-a[ps-top] data;//像存数组一样存数据ps-top;//指向下一个
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;//ps-top为栈中元素个数.0栈中无元素无元素要返回1 无元素ps-t0p0这个表达式结果是1返回1;}
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));//防止栈内无元素继续出栈ps-top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];//ps-top为栈中元素个数由于数组下标是从0开始所以栈顶元素下标为ps-top-1;}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);//free掉动态申请的内存ps-a NULL;//防止野指针ps-capacity ps-top 0;//容量和栈中元素个数置为0}栈的功能测试
int main()
{Stack st;StackInit(st);StackPush(st, 1);StackPush(st, 2);StackPush(st, 3);StackPush(st, 4);while (!StackEmpty(st)){printf(%d, StackTop(st));StackPop(st);}StackDestroy(st);}实现了栈的后入先出
2.队列
2.1队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头 队列的实现 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低 队列的接口函数
// 初始化队列
voidQueueInit(Queue*q);
// 队尾入队列
voidQueuePush(Queue*q, QDataTypedata);
// 队头出队列
voidQueuePop(Queue*q);
// 获取队列头部元素
QDataTypeQueueFront(Queue*q);
// 获取队列队尾元素
QDataTypeQueueBack(Queue*q);
// 获取队列中有效元素个数
intQueueSize(Queue*q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0 intQueueEmpty(Queue*q);
// 销毁队列
voidQueueDestroy(Queue*q);队列的实现
typedef struct QListNode
{struct QListNode* next;//保存结点的下一个结点的地址int data;//该节点的数据
}QNode;
typedef struct Queue
{QNode* front;QNode* tail;
}Queue;//定义一个队列结构体指向队列的前结点和尾结点
// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-front q-tail NULL;//头节点尾结点置为NULL}
// 队尾入队列
void QueuePush(Queue* q, int data)
{assert(q);QNode* newnode (QNode*)malloc(sizeof(QNode));//新结点申请空间assert(newnode);//防止申请失败newnode-next NULL;//新节点的下一个结点的地址为空不保存newnode-data data;//新结点的数据if (q-front NULL)//没有一个结点{q-front q-tail newnode;//就让指向头节点和指向尾结点的指针指向新结点}else//有结点{q-tail-next newnode;//新结点尾插到后面q-tail newnode;//移动指向尾结点的指针到队列末尾结点也就是新结点}}// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q)
{return q-front NULL;//如果没有结点,则q-frontNULL,表达式成立返回1表明队列为空}// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));//防止队列为空在出数据if (q-front-next NULL)//如果只有一个结点{q-front q-tail NULL;//那就把这个结点置空指向头结点指针和指向尾结点的指针指向空}else{QNode* next q-front-next;//保存下一个结点的地址free(q-front);//从头结点开始释放一个结点也就是头删q-front next;//指向头结点的指针移动到下一个位置}}
// 获取队列头部元素
int QueueFront(Queue* q)
{assert(q);assert(q-front);//防止头节点为空return q-front-data;//头结点数据}
// 获取队列队尾元素
int QueueBack(Queue* q)
{assert(q);assert(q-tail);//防止尾节点为空return q-tail-data;//尾节点数据}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{int size 0;//记录元素个数变量assert(q);QNode* cur q-front;//遍历队列的指针先指向头while (cur){size;//遍历记数cur cur-next;}return size;//返回有效数据个数
}
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-front;//遍历队列的指针while (cur){QNode* next cur-next;//保存下一个节点的地址free(cur);//释放掉当前cur指针指向当前位置的空间cur next;//指向下一个位置}q-front q-tail NULL;//防止野指针}
队列功能测试
int main()
{Queue st;QueueInit(st);QueuePush(st, 1);QueuePush(st, 2);QueuePush(st, 3);QueuePush(st, 4);while (!QueueEmpty(st)){printf(%d , QueueFront(st));QueuePop(st);}QueueDestroy(st);}3.栈和队列面试题
20.有效的括号 思路定义一个栈将之前的功能都添在前面使用栈解决这个问题就是遍历这个字符串如果是左括号的话就入栈,然后s遇到右括号的话就取出栈顶元素和这个右括号匹配匹配上了就出栈栈顶元素然后s;没匹配上说明匹配不上直接return false;当不是左括号的时候出现右括号时可能栈里还没有左括号此时也匹配不上直接return false;当遍历完s字符串后s字符串一直是左括号此时也属于匹配不上就是判断栈中是否有元素有元素都是左括号然后就判空函数返回0false(当然定义栈需要初始化栈和销毁栈)。 代码实现
typedef struct Stack
{char* a;int top; // 栈顶int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-capacity ps-top 0;
}
void StackPush(Stack* ps, int data)
{assert(ps);if (ps-capacity ps-top){int newcapcity ps-capacity 0 ? 4 : ps-capacity * 2;char* newnode (char*)realloc(ps-a,sizeof(char) * newcapcity);assert(newnode);ps-a newnode;ps-capacity newcapcity;}ps-a[ps-top] data;ps-top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;}
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-top--;
}
// 获取栈顶元素
char StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;}
// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;}bool isValid(char * s){
Stack st;
StackInit(st);
while(*s)
{if(*s[||*s(||*s{)//左括号入栈{StackPush(st,*s);s;//移动到下一个字符位置}else{if(StackEmpty(st))//可能出现无左括号return false;char topStackTop(st);//获取栈顶元素if(*s]top[||*s}top{||*s)top()//匹配上就出栈{ StackPop(st);s;//移动下一个字符位置}elsereturn false;//匹配不上直接return false}}
int retStackEmpty(st);// s字符串全是左括号全部入栈栈内不为空return 0匹配不上
StackDestroy(st);//销毁栈
return ret;}225.用队列实现栈 思路队列是先进先出而栈是后进先出要用两个队列实现栈一个队列是空的然后要出栈栈顶元素也就是队尾元素可以先将队尾元素的前面的所有元素都入另一个空的队列然后在pop这个队尾的元素就能实现后进的先出由于两个队列构成的栈将一个队列中的元素入另一个队列肯定不是出栈。 1.入栈函数的实现 如果哪个队列不为空就把元素入哪个队列中保证一个队列为空刚开始的时候两个队列都为空入哪个队列都行在第二次入队列时候就能保证元素都入不为空的队列了 2.出栈函数的实现 当保证一个队列为空的时候要实现对应的后入的先出就可以将非空队列的除队尾元素其他的都入另一个队列中当非空队列只剩一个元素时也就是后入的这个元素将这个元素出队列并且不入另一个队列就相当于出栈出队列前用一个变量存储这个队尾元素也就是栈顶元素。 3.返回栈顶元素函数 使用定义好的QueueBack函数返回队尾元素也就是栈顶元素注意肯定返回的是非空队列的队尾元素也就是栈顶元素 4.判断栈为空的函数 使用定义好的QueueEmpty函数return QueueEmpty第一个队列地址QueueEmpty第二个队列地址当两个队列都为空的时候QueueEmpty函数就返回1 return 1表示栈为空如果有一个队列不为空的话与的结果就是0 return 0就是栈不为空。 5.释放栈的函数 使用QueueDestroy销毁两个队列然后free掉动态申请来的空间。 //队列功能的实现
typedef struct QListNode
{struct QListNode* next;int data;
}QNode;typedef struct Queue
{QNode* front;QNode* tail;
}Queue;
void QueueInit(Queue* q)
{assert(q);q-front q-tail NULL;}
// 队尾入队列
void QueuePush(Queue* q, int x)
{assert(q);QNode* newnode (QNode*)malloc(sizeof(QNode));assert(newnode);newnode-data x;newnode-next NULL;if (q-tail NULL){q-tail q-front newnode;}else{q-tail-next newnode;q-tail newnode;}}
bool QueueEmpty(Queue* q)
{assert(q);return q-front NULL;}// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));if (q-front-next NULL){free(q-tail);q-tail q-front NULL;}else{QNode* next q-front-next;free(q-front);q-front next;}}
// 获取队列头部元素
int QueueFront(Queue* q)
{assert(q);assert(q-front);return q-front-data;}
// 获取队列队尾元素
int QueueBack(Queue* q)
{assert(q);assert(q-tail);return q-tail-data;}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);int size 0;QNode* cur q-front;while (cur){size;cur cur-next;}return size;}
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-front;while (cur){QNode* next cur-next;free(cur);cur next;}q-front q-tail NULL;}
//队列功能实现到这里
typedef struct {
Queue a;
Queue b; } MyStack;//定义栈MyStack* myStackCreate() {
MyStack* obj(MyStack*)malloc(sizeof(MyStack));//给栈申请动态空间
if(objNULL){perror(malloc fail);}
QueueInit(obj-a);//栈中两个队列的初始化
QueueInit(obj-b);
return obj;//返回申请栈空间的地址}void myStackPush(MyStack* obj, int x)//入栈函数{
if(!QueueEmpty(obj-a))//哪个队列不为空就入哪个队列
{QueuePush(obj-a,x);}
else
{QueuePush(obj-b,x);}}int myStackPop(MyStack* obj)
{Queue* emptyobj-a;//不知道哪个为空的队列先随便保存一个Queue* nonemptyobj-b;if(!QueueEmpty(obj-a))//如果a队列不是空的就将队列b的地址保存在空的指针里面{emptyobj-b;nonemptyobj-a;}while(QueueSize(nonempty)1)//当非空的队列只剩下一个元素时队尾元素也就是栈顶元素{QueuePush(empty,QueueFront(nonempty));//将非空队列的除队尾元素全部入到另一个空的队列中QueuePop(nonempty);//队头元素出队列}int retQueueFront(nonempty);//循环结束只剩下队尾元素将队尾元素保存在变量中QueuePop(nonempty);//队尾元素出队列并且不进另一个队列相当于出栈return ret;//返回栈顶元素
}int myStackTop(MyStack* obj) {
if(QueueEmpty(obj-a))
{return QueueBack(obj-b);}
else
{return QueueBack(obj-a);//哪个队列不为空直接使用QueueBack返回不为空队列的队尾元素}
}bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(obj-a)QueueEmpty(obj-b);}void myStackFree(MyStack* obj) {QueueDestroy(obj-a);QueueDestroy(obj-b);free(obj);}232.用栈实现队列 思路使用两个栈实现队列栈为后入先出队列为后入后出当要出队头元素也就是栈底元素时可以将栈顶元素一个接一个放入另一个栈中popst,然后栈底元素到另一个栈就变成了栈顶元素然后就可以实现队头元素也就是栈底元素先出栈。 1.入队列函数的实现 使用 StackPush函数将数据入到栈pushst中 2.出队列函数实现 将pushst栈中的栈顶元素一个接一个全部入到栈popst中将pushst栈中的元素全部pop掉此时popst栈顶的元素就是队头元素用一个变量保存他然后将popst栈顶元素pop掉return 栈顶元素。 3.返回队列开头的元素的函数 和出队列函数大致相同这个不需要pop掉队头元素 4.判断队列为空函数 使用StackEmpty函数return StackEmpty(obj-popst)StackEmpty(obj-pushst);当两个栈都为空的时候返回1 表示队列为空只要有一个不为空的话返回0表示队列不为空。 5.释放队列函数 使用StackDestroy函数销毁两个栈然后free掉动态开辟的内存。
typedef struct Stack
{int* a;int top; // 栈顶int capacity; // 容量
}Stack;
void StackInit(Stack* ps)//初始化栈
{ps-a NULL;ps-top 0;ps-capacity 0;
}
void StackPush(Stack* ps, int data)//入栈
{assert(ps);if (ps-capacity ps-top){int newcapcity ps-capacity 0 ? 4 : ps-capacity * 2;int* tmp (int*)realloc(ps-a, sizeof(int) * newcapcity);if (tmp NULL){perror(realloc fail);}else{ps-a tmp;ps-capacity newcapcity;}}ps-a[ps-top] data;ps-top;}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;}
// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));ps-top--;}
// 获取栈顶元素
int StackTop(Stack* ps)
{assert(ps);assert(!StackEmpty(ps));return ps-a[ps-top - 1];}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-top;}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;}typedef struct {
Stack popst;
Stack pushst;} MyQueue;//定义队列MyQueue* myQueueCreate() {MyQueue* obj(MyQueue*)malloc(sizeof(MyQueue));//动态给队列申请空间StackInit(obj-popst); //初始化两个栈StackInit(obj-pushst); return obj;//返回队列的地址}void myQueuePush(MyQueue* obj, int x) {StackPush(obj-pushst,x);//入队列都入到pushst栈中}int myQueuePop(MyQueue* obj) {
if(StackEmpty(obj-popst))//如果popst栈中为空的话
{while(StackSize(obj-pushst))//将pushst栈中的元素全部入到popst栈中
{StackPush(obj-popst,StackTop(obj-pushst));//栈顶元素一个接一个放到popst的栈中StackPop(obj-pushst);//栈顶元素出栈
}}
int retStackTop(obj-popst);//变量接收popst栈顶元素的值然后pop掉
StackPop(obj-popst);
return ret;//返回队列头元素也就是popst栈顶元素}int myQueuePeek(MyQueue* obj) //与上一个函数同理
{if(StackEmpty(obj-popst))
{while(StackSize(obj-pushst))
{StackPush(obj-popst,StackTop(obj-pushst));StackPop(obj-pushst);
}}
int retStackTop(obj-popst);return ret;}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-popst)StackEmpty(obj-pushst);}void myQueueFree(MyQueue* obj)
{
StackDestroy(obj-popst);
StackDestroy(obj-pushst);
free(obj);}622.设计循环队列 思路:用数组实现这个队列较简单在开辟空间大小时需要k个空间我们给他开辟k1个空间如果尾的下一个是头的话就说明队列满了如果头和尾在一个地方则队列为空获取队首元素就是返回obj-a[obj-head]即可获取队尾元素一般要找到obj-tail-1的位置因为tail是后加当存最后一个后他的tail1;插入元素就让obj-a[obj-tail]value;然后tail;删除一个元素就让head就行。 注意边界 检查队列是否满的边界处理 插入元素的边界处理 删除元素边界处理 获取尾部元素的边界处理
typedef struct {int*a;//指向队列空间的指针int k;//队列空间大小int head;//队列头下标int tail;//队列尾下标} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//给描述队列的变量创建空间
obj-a(int *)malloc(sizeof(int)*(k1));//给队列创建空间
obj-kk;//队列空间大小赋值
obj-headobj-tail0;//初始化队列队尾队头下标
return obj;//返回创建队列信息的地址
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj-headobj-tail;//空的话头下标等于尾下标
}bool myCircularQueueIsFull(MyCircularQueue* obj) {int nextobj-tail1;//记录尾下标的下一个下标if(obj-tailobj-k)//边界处理next0;return nextobj-head;//相等说明tail对应的下一个元素是head,表示已经满了}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))//满的话直接返回return false;
obj-a[obj-tail]value;//插入元素
obj-tail;//尾下标更新1
if(obj-tailobj-k1)//边界处理
obj-tail0;
return true;//插入成功
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))//空的不能删除return false
return false;
obj-head; 头下标更新1
if(obj-headobj-k1)//边界处理
obj-head0;
return true; //删除成功return true}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//空的话返回-1return -1;return obj-a[obj-head];//不空返回头下标对应的元素}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//空的话返回-1return -1; int prevobj-tail-1;//记录尾下标的上一个下标if(prev-1)//边界处理prevobj-k; return obj-a[prev];//返回队列尾元素}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);}先free掉obj的话obj-a指针中存放的队列的地址置为随机值永远free不了obj-a,存在内存泄漏所以先free obj-a,然后free obj.
