做违法网站程序员犯法吗,杭州网站建设制作,衡阳公司做网站,衡阳市城市建设投资有限公司网站前言 上一篇博客已经讲到了栈和队列的数据结构#xff0c;概括一下#xff1a;栈后进先出#xff08;Last In First Out#xff09;、队列先进先出#xff08;First In First Out#xff09;。那么#xff0c;接下来就来讲讲#xff0c;关于栈和队列的相关练习题#…前言 上一篇博客已经讲到了栈和队列的数据结构概括一下栈后进先出Last In First Out、队列先进先出First In First Out。那么接下来就来讲讲关于栈和队列的相关练习题进一步掌握栈和队列的使用。
一. 用队列实现栈
1. 题目描述 请你仅使用两个队列实现一个后入先出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双端队列来模拟一个队列 , 只要是标准的队列操作即可。
示例
输入
[MyStack, push, push, top, pop, empty]
[[], [1], [2], [], [], []]
输出
[null, null, null, 2, 2, false]解释
MyStack myStack new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False提示
1 x 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空
进阶你能否仅用一个队列来实现栈。
2. 解题思路 根据上述题目描述我们需要用两个队列来模拟栈后进先出Last In First Out那么问题就在于达到先进后出的效果怎么如数据和出数据。 首先队列出数据的话是从队头出为了达到后出的效果需要把其他的数据暂时存储起来这个时候我们的第二个队列的作用就出现了可以把在其他的数据转移到第二个队列记录第一个队列头数据最后清空第一个队列达到这样的效果。如图1-1所示 图1-1 双队列模拟栈读取删除数据 输入的话就将所有数据录入到非空的队列确保顺序性。 关于进阶——用一个队列模拟栈队列里入数据还是一样入出数据的话就先把队列中前面的数据尾插到原队列按照这个思路我们需要知道需要尾插多少次就在模拟栈的结构里增加一个记录数据总数的整形变量每次删除数据都尾插数据总数减一次。如图1-2所示 图1-2 单队列模拟栈出数据
3. 解题代码 解题代码采用两个队列模拟栈的思路有兴趣的小伙伴可以尝试单队列模拟。
3.1. 基础代码 因为需要用队列模拟栈而C语言不像C那样能够直接使用库中的队列所以这里直接提供给大家队列的代码。代码如下 typedef int QDataType;
// 链式结构表示队列
typedef struct QListNode
{ struct QListNode* _next; QDataType _data;
}QNode; // 队列的结构
typedef struct Queue
{ QNode* _front; QNode* _rear;
}Queue; // 初始化队列
void QueueInit(Queue* q)
{assert(q);q-_front q-_rear NULL;
}// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q)
{assert(q);return q-_front NULL;
}// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);if(QueueEmpty(q)){return 0;}else{QNode* cur q-_front;int count 0;while(cur){count;cur cur-_next;}return count;}
}// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode (QNode*)malloc(sizeof(QNode));if(newnode NULL){perror(QueuePush malloc fail);return;}newnode-_data data;newnode-_next NULL;if(q-_front NULL){q-_front q-_rear newnode;}else{q-_rear-_next newnode;q-_rear q-_rear-_next;}
}// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(!QueueEmpty(q));if(q-_front q-_rear){free(q-_front);q-_front q-_rear NULL;}else{QNode* next q-_front-_next;free(q-_front);q-_front next;}
}// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q-_front-_data;
}// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q-_rear-_data;
}// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);//用cur遍历链表QNode* cur q-_front;//遍历while(cur){//保存下一个位置节点QNode* next cur-_next;free(cur);//释放内存//移动cur next;}//队列中指针置为NULLq-_front q-_rear NULL;
}3.2. 题目要求的函数实现
3.2.1. 栈的结构 栈里面包含两个队列如下所示
typedef struct {Queue q1;Queue q2;
} MyStack;
3.2.2. 初始化栈 为栈的结构开辟空间并将队列初始化代码如下
MyStack* myStackCreate() {MyStack* st (MyStack*)malloc(sizeof(MyStack));QueueInit((st-q1));QueueInit((st-q2));return st;
}
3.2.3. 销毁栈 首先释放栈中队列所开辟的空间然后释放栈开辟的空间代码如下
void myStackFree(MyStack* obj) {QueueDestroy((obj-q1));QueueDestroy((obj-q2));free(obj);
}
3.2.4. 判断栈是否为空 检查两个队列里是否存在数据都没有栈就为空这里直接调用队列为空的函数即可代码如下
bool myStackEmpty(MyStack* obj) {return QueueEmpty((obj-q1)) QueueEmpty((obj-q2));
}
3.2.5. 入栈 向非空的队列入数据代码如下
void myStackPush(MyStack* obj, int x) {assert(obj);//如果队列1不为空则向队列1中录入数据if(!QueueEmpty((obj-q1))){QueuePush((obj-q1), x);}else//反之就录入数据到队列2{QueuePush((obj-q2), x);}
}
3.2.6. 出栈 根据2.解题思路代码如下
int myStackPop(MyStack* obj) {assert(obj);//假设非空的队列为队列2Queue* emp (obj-q1);Queue* noemp (obj-q2);//如果队列2为空就交换队列指针if(QueueEmpty(noemp)){emp (obj-q2);noemp (obj-q1);}//将非空队列前面的数据储存到另一个队列while(QueueSize(noemp) 1){int x QueueFront(noemp);QueuePop(noemp);QueuePush(emp, x);}//记录最后一个队列并输出int ret QueueFront(noemp);QueuePop(noemp);return ret;
}
3.2.7. 访问栈顶数据 向非空的队列访问最后储存的数据代码如下
int myStackTop(MyStack* obj) {assert(obj);//如果队列1为空就访问队列1末尾if(QueueEmpty((obj-q1))){return QueueBack((obj-q2));}else//反之访问队列2末尾{return QueueBack((obj-q1));}
}
3.3. 运行结果 判题无误 图1-3 队列模拟栈题解结果
二. 用栈实现队列
1. 题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作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双端队列来模拟一个栈只要是标准的栈操作即可。
示例 1
输入
[MyQueue, push, push, peek, pop, empty]
[[], [1], [2], [], [], []]
输出
[null, null, null, 1, 1, false]解释
MyQueue myQueue new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示
1 x 9最多调用 100 次 push、pop、peek 和 empty假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作
进阶
你能否实现每个操作均摊时间复杂度为 O(1) 的队列换句话说执行 n 个操作的总时间复杂度为 O(n) 即使其中一个操作可能花费较长时间。
2. 解题思路 用两个栈模拟队列的先进先出First In First Out因为栈只能从末尾读取数据如果要像队列那样保持数据进入的顺序就需要找到队头数据问题就相当于有两个杯子怎么喝到水杯底部的水。 所以我们将栈分为入数据的栈和出数据的栈需要入数据的时候就把出数据的栈的数据放到入数据的栈中然后入数据反之亦然。如图2-1所示 图2-1 栈模拟队列1 这样每次进入数据都需要倒弄栈中的数据时间复杂度为ON那么如何降低时间复杂度呢其实我们不难发现没必要一直倒弄两个栈中的数据如果出队列的时候出数据的栈没有数据在将数据倒入出栈栈即可。这样入队列不需要把出栈的数据倒回去了。如图2-2所示 图2-2 栈模拟队列2
3. 解题代码 本题解法直接采用进阶解法。
3.1. 基础代码 因为需要使用栈的结构所以这里提供栈的相关代码
#define INIT 4// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 栈顶int _capacity; // 容量
}Stack;// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps); // 初始化栈
void StackInit(Stack* ps)
{assert(ps);STDataType* newnode (STDataType*)malloc(sizeof(STDataType) * INIT);if(newnode NULL){perror(StackInit malloc fail);exit(1);}ps-_a newnode;ps-_top 0;ps-_capacity INIT;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//容量不足扩容if(ps-_top ps-_capacity){STDataType* newnode (STDataType*)realloc(ps-_a, sizeof(STDataType) * ps-_capacity * 2);if(newnode NULL){perror(StackInit malloc fail);exit(1);}ps-_a newnode;ps-_capacity * 2;}//入栈ps-_a[ps-_top] data;ps-_top;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);if(!StackEmpty(ps)){--ps-_top;}
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);return ps-_a[ps-_top - 1];//栈顶元素在top的上一位
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{return ps-_top;
}// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(Stack* ps)
{assert(ps);return ps-_top 0;
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-_a);ps-_a NULL;ps-_capacity ps-_top 0;
}
3.2. 题目要求的函数实现
3.2.1. 队列结构
typedef struct {Stack st_push;Stack st_pop;
} MyQueue;
3.2.2. 队列初始化
MyQueue* myQueueCreate() {//开辟队列结构的空间MyQueue* qu (MyQueue*)malloc(sizeof(MyQueue));if(qu NULL){perror(malloc fail);return NULL;}//初始化两个栈StackInit((qu-st_pop));StackInit((qu-st_push));//返回队列空间指针return qu;
}
3.2.3. 销毁队列
void myQueueFree(MyQueue* obj) {//分别释放栈开辟的空间StackDestroy((obj-st_pop));StackDestroy((obj-st_push));//释放队列的空间free(obj);
}
3.2.4. 队列判空
bool myQueueEmpty(MyQueue* obj) {//两个栈都没数据队列才为空return StackEmpty((obj-st_pop)) StackEmpty((obj-st_push));
}
3.2.5. 队列入数据
void myQueuePush(MyQueue* obj, int x) {assert(obj);//记录入队列的栈指针也可以不计这里方便读者理解简化了Stack* _push (obj-st_push);//将数据录入入栈StackPush(_push, x);
}
3.2.6. 队列出数据
int myQueuePop(MyQueue* obj) {//记录入队列的栈指针也可以不计这里方便读者理解简化了Stack* _pop (obj-st_pop);Stack* _push (obj-st_push);//如果出数据的栈为空就将入数据的栈中数据导入到出数据的栈if(StackEmpty(_pop)){while(!StackEmpty(_push)){int tmp StackTop(_push);StackPop(_push);StackPush(_pop, tmp);}}//记录需要出队列的数据删除并输出int ret StackTop(_pop);StackPop(_pop);return ret;
}
3.2.7. 队列获取头数据 直接从出数据的栈中获取栈顶元素没有元素就将入数据栈中元素导入代码如下
int myQueuePeek(MyQueue* obj) {Stack* _pop (obj-st_pop);Stack* _push (obj-st_push);//如果出数据的栈为空就将入数据的栈中数据导入到出数据的栈if(StackEmpty(_pop)){while(!StackEmpty(_push)){int tmp StackTop(_push);StackPop(_push);StackPush(_pop, tmp);}}//输出出数据栈头数据int ret StackTop(_pop);return ret;
}
3.3. 运行结果 结果无误 图2-3 栈模拟队列的结果
三. 设计循环队列
1. 题目描述 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
你的实现应该支持如下操作
MyCircularQueue(k): 构造器设置队列长度为 k 。Front: 从队首获取元素。如果队列为空返回 -1 。Rear: 获取队尾元素。如果队列为空返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
示例
MyCircularQueue circularQueue new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4提示
所有的值都在 0 至 1000 的范围内操作数将在 1 至 1000 的范围内请不要使用内置的队列库。
2. 解题思路
2.1. 顺序表模拟 如果用循序表模拟循环队列则需要两个指针指针一指向队列的头一个指向数组的尾部。入数据从数组尾部进入队列头用来删除数据数组开辟的大小为顺序链表的容量。如果循环队列悟空用两个指针指向同一位置来表示那么想要表示队列为满有两种方式1在队列中增加一个变量记录数组中存在的数据个数。2开辟数组大小的时候多开一个空出的空间那么数组为满的表示为尾指针加一等于头指针。 图3-1 顺序表模拟循环队列
2.2. 链表模拟 如果用链表模拟就比较麻烦需要先将链表的空间全部开好那么剩下的各种操作与顺序表模拟循环队列相同。相比较起来单向链表模拟如果需要读取队尾数据会比较麻烦需要将尾指针遍历到尾指针之前的节点所以使用双向链表模拟会更好但是那从空间上来说不如顺序表模拟。如果找一个变量记录数据个数插入的时候按照双向链表尾插只是限制最后插入的节点个数未必不可行。
3. 解题代码
3.1. 题目要求的函数实现 根据2.1.的解题思路。
3.1.1. 循环队列的结构
//定义存储数据的类型
typedef int QueueDataType;typedef struct {QueueDataType* a; //顺序表位置int pcur; //头指针int ptail; //尾指针int size; //限制的循环队列大小
} MyCircularQueue;
3.1.2. 循环队列初始化 包括开辟空间各项指针置为0记录队列容量代码如下
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(cq NULL){perror(malloc fail);return NULL;}cq-a (QueueDataType*)malloc(sizeof(QueueDataType) * (k 1));cq-pcur cq-ptail 0;cq-size k;return cq;
}
3.1.3. 判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);return obj-ptail obj-pcur;
}
3.1.4. 判断队列中数据是否满了 向这总增加的都需要用总容量取模防止溢出。
bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);return (obj-ptail 1) % (obj-size 1) obj-pcur;
}
3.1.5. 向队列中增加数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);//队列满员了就无法添加if(myCircularQueueIsFull(obj)){return false;}else{obj-a[obj-ptail] value;obj-ptail % (obj-size 1);return true;}
}
3.1.6. 从队列中删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);//如果队列为空则删除失败if(myCircularQueueIsEmpty(obj)){return false;}else{obj-pcur;obj-pcur % (obj-size 1);return true;}
}
3.1.7. 从队头获取数据
int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);//队列为空返回-1if(myCircularQueueIsEmpty(obj)){return -1;}else//反之返回数据{return obj-a[obj-pcur];}
}
3.1.8. 从队尾获取数据
int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);//为空返回-1if(myCircularQueueIsEmpty(obj)){return -1;}else//队尾指针-1k1最后取模得到后一位的地址{return obj-a[(obj-ptail obj-size) % (obj-size 1)];}
}
3.2. 运行结果 结果无误 图3-2
作者结语 虽然说代码能够解开谜题但是用文本的方式真的很难把题目短时间说清楚。具体细节还需要读者自己体会这里最多算是抛了一个砖。 感谢大家看到这里那也说明写博客的时间没有白费。
文章转载自： http://www.morning.rdlong.com.gov.cn.rdlong.com http://www.morning.xhklb.cn.gov.cn.xhklb.cn http://www.morning.xflzm.cn.gov.cn.xflzm.cn http://www.morning.hotlads.com.gov.cn.hotlads.com http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.rbkdg.cn.gov.cn.rbkdg.cn http://www.morning.jwtjf.cn.gov.cn.jwtjf.cn http://www.morning.grjh.cn.gov.cn.grjh.cn http://www.morning.cfrz.cn.gov.cn.cfrz.cn http://www.morning.tdxnz.cn.gov.cn.tdxnz.cn http://www.morning.btlmb.cn.gov.cn.btlmb.cn http://www.morning.fbqr.cn.gov.cn.fbqr.cn http://www.morning.jpkhn.cn.gov.cn.jpkhn.cn http://www.morning.sjmxh.cn.gov.cn.sjmxh.cn http://www.morning.ksjmt.cn.gov.cn.ksjmt.cn http://www.morning.caswellintl.com.gov.cn.caswellintl.com http://www.morning.nlcw.cn.gov.cn.nlcw.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.xqjrg.cn.gov.cn.xqjrg.cn http://www.morning.rpzth.cn.gov.cn.rpzth.cn http://www.morning.rjhts.cn.gov.cn.rjhts.cn http://www.morning.rfyk.cn.gov.cn.rfyk.cn http://www.morning.rhkmn.cn.gov.cn.rhkmn.cn http://www.morning.mxhys.cn.gov.cn.mxhys.cn http://www.morning.wlqbr.cn.gov.cn.wlqbr.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.rfrxt.cn.gov.cn.rfrxt.cn http://www.morning.gzgwn.cn.gov.cn.gzgwn.cn http://www.morning.pjrgb.cn.gov.cn.pjrgb.cn http://www.morning.qdxwf.cn.gov.cn.qdxwf.cn http://www.morning.lmrcq.cn.gov.cn.lmrcq.cn http://www.morning.rccpl.cn.gov.cn.rccpl.cn http://www.morning.pqhfx.cn.gov.cn.pqhfx.cn http://www.morning.mhcft.cn.gov.cn.mhcft.cn http://www.morning.qwqzk.cn.gov.cn.qwqzk.cn http://www.morning.kkzwn.cn.gov.cn.kkzwn.cn http://www.morning.npmcf.cn.gov.cn.npmcf.cn http://www.morning.dgmjm.cn.gov.cn.dgmjm.cn http://www.morning.qlznd.cn.gov.cn.qlznd.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.lcmhq.cn.gov.cn.lcmhq.cn http://www.morning.fcxt.cn.gov.cn.fcxt.cn http://www.morning.sbwr.cn.gov.cn.sbwr.cn http://www.morning.hphfy.cn.gov.cn.hphfy.cn http://www.morning.qxgmp.cn.gov.cn.qxgmp.cn http://www.morning.jzlfq.cn.gov.cn.jzlfq.cn http://www.morning.clbsd.cn.gov.cn.clbsd.cn http://www.morning.zztmk.cn.gov.cn.zztmk.cn http://www.morning.gsjfn.cn.gov.cn.gsjfn.cn http://www.morning.stsnf.cn.gov.cn.stsnf.cn http://www.morning.rnnwd.cn.gov.cn.rnnwd.cn http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.nzmhk.cn.gov.cn.nzmhk.cn http://www.morning.byrlg.cn.gov.cn.byrlg.cn http://www.morning.gcqkb.cn.gov.cn.gcqkb.cn http://www.morning.zmpsl.cn.gov.cn.zmpsl.cn http://www.morning.pbygt.cn.gov.cn.pbygt.cn http://www.morning.vtbtje.cn.gov.cn.vtbtje.cn http://www.morning.tnnfy.cn.gov.cn.tnnfy.cn http://www.morning.rttxx.cn.gov.cn.rttxx.cn http://www.morning.smzr.cn.gov.cn.smzr.cn http://www.morning.frxsl.cn.gov.cn.frxsl.cn http://www.morning.yjfzk.cn.gov.cn.yjfzk.cn http://www.morning.rgwrl.cn.gov.cn.rgwrl.cn http://www.morning.lxmks.cn.gov.cn.lxmks.cn http://www.morning.lclpj.cn.gov.cn.lclpj.cn http://www.morning.zlfxp.cn.gov.cn.zlfxp.cn http://www.morning.zxzgr.cn.gov.cn.zxzgr.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.srnth.cn.gov.cn.srnth.cn http://www.morning.fylsz.cn.gov.cn.fylsz.cn http://www.morning.qnkqk.cn.gov.cn.qnkqk.cn http://www.morning.pgfkl.cn.gov.cn.pgfkl.cn http://www.morning.ksqyj.cn.gov.cn.ksqyj.cn http://www.morning.xfwnk.cn.gov.cn.xfwnk.cn http://www.morning.trffl.cn.gov.cn.trffl.cn http://www.morning.stxg.cn.gov.cn.stxg.cn http://www.morning.bnrnb.cn.gov.cn.bnrnb.cn http://www.morning.bsrp.cn.gov.cn.bsrp.cn http://www.morning.hrpbq.cn.gov.cn.hrpbq.cn
