学网站建设难吗,网页设计制作教程:一个页面的完全制作,郑州做网站的公司哪些,wordpress注册页制作文章目录 栈和队列的回顾#x1f4bb;栈#x1fa73;队列#x1f45f; 栈和队列经典笔试题#x1f50b;有效的括号#x1f3b8;用队列实现栈 #x1f56f;用栈实现队列#x1f52d;设计循环队列#x1f9fc; 安静的夜晚 你在想谁吗 栈和队列的回顾#x1f4bb;
栈栈队列 栈和队列经典笔试题有效的括号用队列实现栈 用栈实现队列设计循环队列 安静的夜晚 你在想谁吗 栈和队列的回顾
栈 栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 一般使用数组实现栈 物理图表示入栈和出栈后进先出
队列 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出。FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头。 物理图表示入队和出队先进先出
栈和队列经典笔试题
有效的括号
力扣题目链接有效的括号 给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 下面是几个示例
题目分析 本题通俗的来讲就是判断括号是否是匹配的即括号的类型是否匹配和数量是否匹配。我们可以使用栈的知识来解决这道题从给定序列的第一个字符开始遍历如果遍历遇到左括号就入栈如果遍历遇到右括号则先取栈顶元素再出栈因为合适的匹配必须是栈判断栈顶元素与这个右括号是否匹配。 需要注意的点有尽量每次循环只遍历一个元素或只对一个元素进行判断这样可以保证数量匹配的正确性。当遍历一个元素不是左括号的时候就判断栈中是否为空如果栈为空则说明数量是不匹配的如果栈不为空则要对这个右括号是否和栈顶的左括号匹配进行判断。 其实本题比较复杂的还是结构的问题毕竟不用C的这个栈的功能需要我们自己去实现。 力扣代码含栈结构
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STtop(ST* ps);
int STsize(ST* ps);
bool STEmpty(ST* ps);
void STInit(ST* ps)
{ps-a NULL;ps-top 0;ps-capacity 0;
}
void STDestroy(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(realloc 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-top0);return ps-a[ps-top-1];
}int STsize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return (ps-top 0);
}bool isValid(char * s){ST st;STInit(st);char stack_top;while(*s){if(*s(||*s[||*s{){STPush(st,*s);} else{if(STEmpty(st)){STDestroy(st);return false;}stack_topSTtop(st);STPop(st);if(*s)stack_top!(||*s]stack_top![||*s}stack_top!{){STDestroy(st);return false;}}s;}if(!STEmpty(st)){STDestroy(st);return false;}return true;
}当代码在所有不满足的情况下依旧没有返回 false 的时候则说明它是满足括号的有效性的。
用队列实现栈
力扣题目链接用队列实现栈 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。
范例 题目分析及思路 队列是先进先出要实现一个后进先出的栈一个队列肯定是不行的必须使用两个队列来互相导着来实现。例如我现在要对这个数据结构入4个元素1 2 3 4 队列只能 pop 先 push 的元素而要达到将最后进入的元素 pop 的目的就需要另一个队列来帮忙了先将所有元素都push到队列1取 队列1 头位置的元素将它 push 到 队列2 中后再将 队列1 中这个元素 pop 掉。如此往复直到 队列1 中只剩下一个元素这就是栈结构中需要 pop 的元素。 再将最后这个元素pop掉就相当于将栈结构里的栈顶元素pop掉了。这样就实现了栈的pop功能。 在上面的例子中我们可以总结出队列实现栈的一般规律实现push数据就往空的队列里push实现pop数据先将费控队列的前n-1个元素导入空队列并pop这n-1个元素最后将剩下的那个元素pop掉即可实现栈的pop功能。 力扣代码含结构
typedef int QDataType;
typedef struct QueueNode {QDataType data;struct QueueNode* next;
}QNode;
typedef struct Queue {QNode* head;QNode* tail;int size;
}Que;
void QueueInit(Que*pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}
}
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* nownode (QNode*)malloc(sizeof(QNode));if (nownode NULL){perror(malloc fail);exit(-1);}nownode-data x;nownode-next NULL;if (pq-tail NULL){pq-head pq-tail nownode;}else{pq-tail-next nownode;pq-tail nownode;}pq-size;
}
void QueuePop(Que* pq)
{assert(pq);assert(pq-head ! NULL);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 QueueFront(Que* pq)
{assert(pq);assert(pq-head ! NULL);return pq-head-data;
}
QDataType QueueBack(Que* pq)
{assert(pq);assert(pq-head!NULL);return pq-tail-data;}
bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}
int QueueSize(Que* pq)
{assert(pq);return pq-size;
}typedef struct {Que q1,q2;
} MyStack;MyStack* myStackCreate() {MyStack*pst(MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);//-的优先级高于其实是(pst-q1)将定义的结构体变量的地址传过去QueueInit(pst-q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj) {Que*emptyobj-q1;Que*nonEmptyobj-q2;if(!QueueEmpty(obj-q1)){emptyobj-q2;nonEmptyobj-q1;}//把非空队列的前size-1个元素push到空队列while(QueueSize(nonEmpty)1){QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int topQueueFront(nonEmpty);QueuePop(nonEmpty);return top;
}int myStackTop(MyStack* obj) {if(QueueEmpty(obj-q1)){return QueueBack(obj-q2);}else{return QueueBack(obj-q1);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1)QueueEmpty(obj-q2);}void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(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);
*/用栈实现队列
力扣题目链接用栈实现队列 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。 范例 题目分析及思路 题目要求只使用栈的基本操作实现一个队列这就需要两个栈进行‘合作’来完成。 例如现在要往队列中 push 四个数据1234。 创建两个栈一个pushst一个popst如图先将这四个数据push到 pushst 这个栈中。 现在如果要实现队列的 pop 操作就要将数据1 删除但栈只能pop栈顶元素所以只能先将pushst中的‘上面’的三个数据先导过来取栈顶元素再pop然后数据1 就变成了 pushst 的栈顶元素直接pop即可。 接下来如果队列还需要 pop 数据的话只需要在 popst 中 pop 即可。 如果要 push 数据直接push 到pushst中再次push后如果要pop数据需要将popst中的数据pop完后直接取栈顶元素将 pushst 中新push 的 n-1 个数据先导过去再用上面的方式出popst中的数据即可。 总结定义两个栈队列需要push数据的时候先往pushst中push数据此时栈popst中为空首次需要pop数据的时候先将pushst中push的n-1个数据导入popst中然后将最后一个元素pop掉这就是队列要pop的头。当将n-1个数据导入popst中后如果队列再要pop数据就直接使用栈 popst 进行pop数据入数据的时候就继续在pushst中压栈当popst中的数据pop完了直接还要pop的话就需要再将pushst中的n-1个元素导过去如此往复… 力扣代码含结构
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶位置int capacity;//栈空间大小
}ST;
void STInit(ST* ps);
void STPush(ST* ps,STDataType x);
void STPrint(ST* ps);
void STPop(ST* ps);
void STDestroy(ST* ps);
STDataType STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-capacityps-top){int newcapacity (ps-capacity 0) ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, newcapacity * sizeof(ps-a));if (tmp NULL){perror(realloc fail);exit(-1);}ps-capacity newcapacity;ps-a tmp;}ps-a[ps-top] x;ps-top;
}
void STPrint(ST* ps)
{assert(ps);int i 0;for (i 0; i ps-top; i){printf(%d , ps-a[i]);}printf(\n);
}
void STPop(ST* ps)
{assert(ps);assert(ps-top0);(ps-top)--;
}
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;
}
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-top 0;
}typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);
}int myQueuePop(MyQueue* obj) {int frontmyQueuePeek(obj);STPop(obj-popst);return front;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-popst)){while(STSize(obj-pushst)0){STPush(obj-popst,STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-popst)STEmpty(obj-pushst);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}设计循环队列
力扣题目链接设计循环队列 范例 个人理解当我们使用数组顺序表来实现队列的时候随着出数据的时候队头不断前移那么队列的容量队头到队尾将会越来越小如下图 所以可以采用循环队列的方式来维持队列容量的恒定。 此题需要的空间固定为k并且要将这些空间重复利用所以采用用数组实现最为合适。 思路 开辟数组空间的时候‘多开一个’利用数组的下标来控制队尾和队头的位置。 比如当队列的长度为4的时候就开辟5块空间的地址最后一块空间用来把握队列长度来防止越界。当队头和队尾相等的时候说明队列为空当队尾1%k1等于队头的时候说明队头和队尾之间只有一块空间的地址说明队列已满。 力扣代码
typedef struct {int*a;int k;int front;int rear;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj-a(int*)malloc(sizeof(int)*(k1));obj-kk;obj-frontobj-rear0;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-frontobj-rear;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj-rear1)%(obj-k1)obj-front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj-a[obj-rear]value;obj-rear;obj-rear%obj-k1;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj-front;obj-front%obj-k1;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj-a[(obj-rearobj-k)%(obj-k1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);obj-aNULL;free(obj);objNULL;
}/*** 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);
*/
