vps建设网站,什么是品牌型网站,无锡做网站价格,书画艺术网站建设CSDN的uu们#xff0c;大家好。这里是C语言数据结构的第八讲。 目标#xff1a;前路坎坷#xff0c;披荆斩棘#xff0c;扶摇直上。 博客主页#xff1a; 姬如祎 收录专栏#xff1a;数据结构与算法栈与队列的知识点我➡➡队列相关点我➡➡栈相关2. 用栈实现队列原题链接…· CSDN的uu们大家好。这里是C语言数据结构的第八讲。· 目标前路坎坷披荆斩棘扶摇直上。· 博客主页 姬如祎· 收录专栏数据结构与算法栈与队列的知识点我➡➡队列相关点我➡➡栈相关2. 用栈实现队列原题链接剑指 Offer 09. 用两个栈实现队列 - 力扣LeetCode232. 用栈实现队列 - 力扣Leetcode题目描述请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty实现 MyQueue 类void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false说明你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。2.1 思路分析一个队列里面包含了两个栈stack1和stack2。直讲解有点抽象我们用一个具体的例子来讲解。假设我们要向队列中插入1,2,3三个元素后将它们删除如何实现呢首先我们插入1这个元素不妨把他插入到stack1然后再依次插入23此时stack1内栈顶元素为3stack2为空见下图。这时候我们尝试从队列中删除一个元素。按照队列先入先出的规则最先入列的1应该是最先出列的故应该删除1。但是1存储在stack1中并不是在栈顶于是我们需要借助stack2如果我们把stack1中的元素依次弹出并压入到stack2中则stack2中的元素顺序正好和原来相反。因此经过三次弹出stack1和压入stack2的操作后stack1为空stack2中的元素是 3, 2, 1这时候就可以弹出栈顶的1了。在删除队头的1后队列中还剩2和3我们想要继续删除队头的元素那么应该删除2而此时2恰好又在栈顶因此直接弹出2即可。 通过例子的分析我们就可以总结如下规律添加元素的步骤直接将元素入栈到stack1即可。删除元素的步骤当stack2不为空时在栈顶的元素就是队列中先入列的元素直接弹出栈顶的元素即可当stack2为空时我们就需要将stack1中的元素依次弹出并压入到stack2中直到stack1为空。如果说stack2为空去stack1中拿元素时发现stack1也为空根据题目要求返回-1即可。销毁队列销毁两个栈即可。当然你也可以用数组模拟实现栈进而用两个栈实现队列。2.2 代码实现#define INIT_STACK_SIZE 4
typedef char STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
} ST;void StackInit(ST* st)
{assert(st);st-a (STDataType*)malloc(sizeof(STDataType) * INIT_STACK_SIZE);st-capacity INIT_STACK_SIZE;st-top 0;
}void StackPush(ST* st, STDataType x)
{assert(st);if (st-top st-capacity){STDataType* new (STDataType*)realloc(st-a, sizeof(STDataType) * st-capacity * 2);if (!new){perror(StackPush::malloc);exit(-1);}else{st-a new;st-capacity * 2;}}st-a[st-top] x;st-top;}
void StackPop(ST* st)
{assert(st);assert(st-top);st-top--;
}
bool StackEmpty(ST* st)
{assert(st);return st-top 0;
}
STDataType StackTop(ST* st)
{assert(st);assert(st-top);return st-a[st-top - 1];
}
int StackSize(ST* st)
{assert(st);return st-top;
}
void StackDestory(ST* st)
{assert(st);free(st-a);st-a NULL;st-capacity 0;st-top 0;
}typedef struct {ST pushStack;ST popStack;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* queue (MyQueue*)malloc(sizeof(MyQueue));StackInit(queue-pushStack);StackInit(queue-popStack);return queue;
}void myQueuePush(MyQueue* obj, int x) {StackPush(obj-pushStack, x);
}int myQueuePop(MyQueue* obj) {if(StackEmpty(obj-popStack)){while(!StackEmpty(obj-pushStack)){StackPush(obj-popStack, StackTop(obj-pushStack));StackPop(obj-pushStack);}}STDataType top StackTop(obj-popStack);StackPop(obj-popStack);return top;
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(obj-popStack)){while(!StackEmpty(obj-pushStack)){StackPush(obj-popStack, StackTop(obj-pushStack));StackPop(obj-pushStack);}}return StackTop(obj-popStack);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-popStack) StackEmpty(obj-pushStack);
}void myQueueFree(MyQueue* obj) {StackDestory(obj-pushStack);StackDestory(obj-popStack);free(obj);
}3. 用队列实现栈原题链接225. 用队列实现栈 - 力扣Leetcode题目描述请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。实现 MyStack 类void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 注意你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。3.1 思路分析一个栈里面包含了两个队列Queue1和Queue2直接讲解也是有点抽象我们通过例子来讲解假设我们要依次入栈1, 23首先入栈元素1同样我们不妨直接把他插入Queue1中然后再次插入2, 3到Queue1中此时Queue1中有三个元素1, 2, 3Queue2为空。 现在我们尝试从栈中删除一个元素。按照栈后进先出的规则最后入栈的元素3应该最先出栈。但是元素3并不在Queue1的队头我们不能直接把他删除。这时候我们就要借助Queue2了将元素1从Queue1中出列将它入列到Queue2中将元素2从Queue1中出列将它入列到Queue2中此时我们会发现要出栈的元素3就在Queue1的队头了直接将其出列即可。同样地我们还想删除一个元素此时2就是栈顶元素它不在Queue2的队头不能直接删除同样需要借助另一个队列Queue1将元素1从Queue2中出列入列到Queue1中此时要出栈的元素2就在Queue2的队头了直接删除即可。 还想删除栈顶的元素1时我们发现它就在Queue1的队头直接删除即可。通过以上分析我们总结出一下规律删除元素将不为空的那个队列数据的N-1N为不为空的那个队列的元素个数/队列大小个导入到为空的那个队列剩下的那个元素即为栈顶元素删除即可。添加元素将元素添加到那个不为空的队列中即可如果两个都为空随便添加到哪一个都行。查看栈顶的元素根据以上分析不为空的那个队列队尾的数据就是栈顶的元素我们直接查看队尾的元素即可。判断栈是否为空如果两个队列都为空则栈为空否则栈不为空。销毁栈销毁两个队列即可。同样地你也可以使用两个数组来模拟两个队列进而模拟实现栈。3.2 代码实现typedef int QueueDataType;typedef struct QueueNode
{struct QueueNode* next;QueueDataType data;
} QueueNode;typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
} Queue;//队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}//队列的销毁
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* cur pq-head;while (cur){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}//队尾增加元素
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode));newNode-data x;newNode-next NULL;if (!pq-head){pq-head pq-tail newNode;}else{pq-tail-next newNode;pq-tail newNode;}pq-size;
}//队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);//one way//return pq-size 0;//another wayreturn pq-head NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//one possibility//if (pq-head pq-tail)//{// free(pq-head);// pq-head pq-tail NULL;//}//else//{// QueueNode* next pq-head-next;// free(pq-head);// pq-head next;//}//pq-size--;//another wayQueueNode* next pq-head-next;free(pq-head);pq-head next;pq-size--;if (pq-head NULL)pq-tail NULL;}//队列的元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//队头元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}//队尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* stack (MyStack*)malloc(sizeof(MyStack));QueueInit(stack-q1);QueueInit(stack-q2);return stack;
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackPush(MyStack* obj, int x) {Queue* emptyQueue obj-q1, *noneEmptyQueue obj-q2;if(QueueEmpty(obj-q2)){emptyQueue obj-q2;noneEmptyQueue obj-q1;}QueuePush(noneEmptyQueue, x);
}int myStackPop(MyStack* obj) {Queue* emptyQueue obj-q1, *noneEmptyQueue obj-q2;if(QueueEmpty(obj-q2)){emptyQueue obj-q2;noneEmptyQueue obj-q1;}while(QueueSize(noneEmptyQueue) 1){QueueDataType front QueueFront(noneEmptyQueue);QueuePop(noneEmptyQueue);QueuePush(emptyQueue, front);}QueueDataType front QueueFront(noneEmptyQueue);QueuePop(noneEmptyQueue);return front;
}int myStackTop(MyStack* obj) {Queue* emptyQueue obj-q1, *noneEmptyQueue obj-q2;if(QueueEmpty(obj-q2)){emptyQueue obj-q2;noneEmptyQueue obj-q1;}return QueueBack(noneEmptyQueue);
}void myStackFree(MyStack* obj) {QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);
}4. 有效的括号原题链接20. 有效的括号 - 力扣Leetcode题目描述给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。4.1 思路分析你可能会想到用括号的数量来进行判断但是因为题目要求每个括号都应该与对应的括号进行匹配这种思路显然是行不通的。那我们该怎么做呢大致思路我们维护一个栈然后遍历所有的括号如果说遇到左括号我们就把它入栈。随后继续遍历如果遇到右括号我们就取栈顶元素出来与遍历到的括号类型进行匹配如果说与栈顶的括号类型不匹配就返回flase如果匹配呢就继续往下遍历。最后判断一下栈是否为空即可。如果说栈为空所有的左括号均与右括号进行了匹配返回true如果栈不为空说明左括号数量较多返回false即可这里值得注意的是如果说字符串的一开始就是右括号的类型那么栈显然就是空这种情况就需要我们特殊处理一下。4.2 代码实现#define INIT_STACK_SIZE 4
typedef char STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
} ST;void StackInit(ST* st)
{assert(st);st-a (STDataType*)malloc(sizeof(STDataType) * INIT_STACK_SIZE);st-capacity INIT_STACK_SIZE;st-top 0;
}void StackPush(ST* st, STDataType x)
{assert(st);if (st-top st-capacity){STDataType* new (STDataType*)realloc(st-a, sizeof(STDataType) * st-capacity * 2);if (!new){perror(StackPush::malloc);exit(-1);}else{st-a new;st-capacity * 2;}}st-a[st-top] x;st-top;}
void StackPop(ST* st)
{assert(st);assert(st-top);st-top--;
}
bool StackEmpty(ST* st)
{assert(st);return st-top 0;
}
STDataType StackTop(ST* st)
{assert(st);assert(st-top);return st-a[st-top - 1];
}
int StackSize(ST* st)
{assert(st);return st-top;
}
void StackDestory(ST* st)
{assert(st);free(st-a);st-a NULL;st-capacity 0;st-top 0;
}bool isValid(char * s){if(!s)return false;ST st;StackInit(st);int len strlen(s);for(int i 0; i len; i){if(s[i] ( || s[i] [ || s[i] {)StackPush(st, s[i]);else{if(StackEmpty(st)){StackDestory(st);return false;}else{char top StackTop(st);if(top ( s[i] ) || top { s[i] } || top [ s[i] ])StackPop(st); else{StackDestory(st);return false;}}}}bool isEmpty StackEmpty(st);StackDestory(st);return isEmpty;
}5. 设计循环队列原题链接622. 设计循环队列 - 力扣Leetcode题目描述设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。你的实现应该支持如下操作MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。5.1 循环队列的基础知识循环队列的定义我们把队列头尾相接的顺序存储结构称为循环队列。循环队列的逻辑结构大家可以看到我这里空了一个位置至于是为什么有什么作用我先卖个关子循环队列的缺点用数组实现的话队列的容量随着数组定义是就已经确定啦。循环队列的优点增加了空间的使用效率。5.2 数组OR链表大家一看到循环队列的逻辑结构肯定第一想法就是用链表实现。那么用链表实现行不行呢当然是没有问题的但是我们肯定要经过各种比较选择出一种最优秀的方法撒无论用什么什么数据结构实现我们都会面临一个问题怎么判断循环队列是否已经满了嘞这个点在设计循环队列时是相当重要的。对于链表也是同样的道理。那么我们该怎么解决这个问题呢你说我们可以一开始令rear不同head这样就可以很好的区分循环队列空和满的状态了或许你也可能会说我们可以维护一个变量来记录循环队列的大小这样也能区分循环队列空与满的状态。不错你很厉害。但是呢这里还有一个方法。不妨我们一起来看看比如我们要设计的循环队列容量为3我们的数组就开4个整型的大小。这样做也能很好的区分循环队列空与满的状态哦我们看到这样设计的话当rear的下一个位置是head时就是循环队列为满的状态当head等于rear时就是循环队列为空的时候。链表同理的哈那么到底是哪种方法好呢仁者见仁智者见智很多书都是以这种多开一个空间的方式来设计循环队列的我们这里就是讲解这种啦回到我们的正题是链表还是数组呢我们来看看链表乍一看好像没啥问题但是注意到看到题目我们是要实现获取队尾元素的这个函数的单向的循环链表显然找尾是非常麻烦的。你说我们可以用双向循环链表呀很好没有问题。只是这样做的话是不是有些复杂呢我们来看看数组取队尾元素我们只要访问rear下标减一的位置就行只是可能存在数组下标越界的问题很简单我们只需要在rear加一和rear减一的过程中对结果取模就行啦综上所述设计循环队列我们选用一个比循环队列容量大一的数组来实现。5.3 函数的实现因为在操作数据时我们要用到循环队列的容量还要维护headrear等变量所以我们将它们全部封装在一个结构体里面结构如下typedef struct {int front; //就是上面所有图中的head表示队头元素int rear; //队尾元素int size; //循环队列的容量这个一开始就是确定了的int* queue; //设计循环队列的数组
} MyCircularQueue;MyCircularQueue(k): 构造器设置队列长度为 k 。这个函数我们需要把数组开辟出来大小就是循环队列的长度加一。还需要初始化我们维护的变量。MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //开辟结构体q-front q-rear 0; //初始化front和rearq-size k; //初始化循环队列的长度q-queue (int*)malloc(sizeof(int) * (q-size 1)); //初始化我们的数组return q;
}isEmpty(): 检查循环队列是否为空。这里我们先实现这个函数因为下面的函数会用到这个函数。根据上面的知识我们只需要判断rear是不是等于front就可以判断循环队列是不是为空啦bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。插入元素也比较简单我们将rear指向的位置进行赋值然后让rear加一就行啦只不过需要注意的是rear加一的时候下标可能会越界这个时候我们就需要对rear加一的值取模。当然如果循环队列是满的状态也是不允许插入元素的。bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(((obj-rear 1) % (obj-size 1)) obj-front) //判断循环队列是否为满也需要取模return false;else{obj-queue[obj-rear] value;obj-rear (obj-rear 1) % (obj-size 1);return true;}
}
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。删除元素我们只需要让front加一进行逻辑上的删除即可当然循环队列不为空不允许删除同时也需要对加一的结果取模bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj-front (obj-front 1) % (obj-size 1);return true;}
}Front: 从队首获取元素。如果队列为空返回 -1 。这个函数我们只需要返回front指向的位置就行。当然前提是循环队列不为空啦int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-queue[obj-front];
}Rear: 获取队尾元素。如果队列为空返回 -1 。两个注意点1不为空才能获取队尾元素。2因为rear-1才是队尾元素所以注意取模int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-queue[(obj-rear - 1 obj-size 1) % (obj-size 1)];
}剩余的函数就不单独写啦直接放到后面一起的代码实现中啦5.4 代码实现typedef struct {int front; //就是上面所有图中的head表示队头元素int rear; //队尾元素int size; //循环队列的容量这个一开始就是确定了的int* queue; //设计循环队列的数组
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q (MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-front q-rear 0;q-size k;q-queue (int*)malloc(sizeof(int) * (q-size 1));return q;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj-front obj-rear;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(((obj-rear 1) % (obj-size 1)) obj-front)return false;else{obj-queue[obj-rear] value;obj-rear (obj-rear 1) % (obj-size 1);return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj-front (obj-front 1) % (obj-size 1);return true;}
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-queue[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj-queue[(obj-rear - 1 obj-size 1) % (obj-size 1)];
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return ((obj-rear 1) % (obj-size 1)) obj-front;
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-queue);free(obj);
}
