做网站需要哪些,百度搜索指数的数据来源,演出公司网站建设,wdcp备份网站. 个人主页#xff1a;晓风飞 专栏#xff1a;LeetCode刷题|数据结构|Linux 路漫漫其修远兮#xff0c;吾将上下而求索 文章目录 题目要求#xff1a;实现 MyStack 类#xff1a;注意#xff1a;示例#xff1a;解释#xff1a;提示#xff1a; 解题核心数据结构的定义…
. 个人主页晓风飞 专栏LeetCode刷题|数据结构|Linux 路漫漫其修远兮吾将上下而求索 文章目录 题目要求实现 MyStack 类注意示例解释提示 解题核心数据结构的定义初始化栈入栈Push操作出栈Pop操作获取栈顶元素Top检查栈是否为空Empty销毁栈Free以下是队列的实现:以下是本题的实现: 要做题目的点击这里–栈和队列oj题——225. 用队列实现栈
题目要求 请你仅使用两个队列实现一个后入先出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 都保证栈不为空 进阶你能否仅用一个队列来实现栈。 myStackCreate - 创建栈 解题核心
这个问题的核心思路在于使用两个队列Queue来模拟一个栈Stack的行为。栈是一种后进先出LIFO, Last In First Out的数据结构而队列是一种先进先出FIFO, First In First Out的数据结构。要用队列模拟栈的行为关键在于如何实现栈的两个主要操作入栈push和出栈pop。
数据结构的定义
初始化两个队列这两个队列将用于模拟栈的行为。
// 定义一个使用两个队列模拟的栈的结构体
typedef struct
{Queue q1; // 第一个队列Queue q2; // 第二个队列
} MyStack;初始化栈
动态分配内存给新的栈,如果内存分配失败输出错误信息并退出。
// 创建一个新的栈
MyStack* myStackCreate()
{// 动态分配内存给新栈MyStack* newStack (MyStack*)malloc(sizeof(MyStack));if (!newStack){perror(malloc fail); // 如果内存分配失败输出错误信息并退出exit(-1);}// 初始化两个队列QInit((newStack-q1));QInit((newStack-q2));return newStack;
}入栈Push操作
在栈中最新添加的元素总是被存储在栈的顶部。在使用两个队列模拟栈时入栈操作相对直接 选择一个非空队列进行操作如果两个队列都是空的可以选择任意一个队列进行操作。如果有一个非空队列总是将新元素入队到这个非空队列。
// 将一个元素推入栈中
void myStackPush(MyStack* obj, int x)
{assert(obj); // 确保栈对象非空// 总是将元素推入非空队列中if(!QueueEmpty(obj-q1)){QPush(obj-q1, x);}else{QPush(obj-q2, x);}
}出栈Pop操作
确定非空队列和空队列首先识别出哪个队列是非空的存有栈元素的队列哪个队列是空的。
// 从栈中弹出一个元素
int myStackPop(MyStack* obj)
{ assert(obj); // 确保栈对象非空Queue* empty obj-q1; // 一个指向可能为空的队列的指针Queue* noEmpty obj-q2; // 一个指向非空队列的指针// 确定哪个队列是空的哪个是非空的if(!QueueEmpty(empty)){empty obj-q2;noEmpty obj-q1;}// 将元素从非空队列转移到空队列直到只剩下一个元素while(QueueSize(noEmpty) 1){QPush(empty, QueueFront(noEmpty));QPop(noEmpty);}// 弹出并返回最后一个元素int top QueueFront(noEmpty);QPop(noEmpty);return top;
}获取栈顶元素Top
栈顶元素对应于最后进入非空队列的元素。可以通过查看非空队列的尾部元素来得知栈顶元素。
// 获取栈顶元素
int myStackTop(MyStack* obj)
{assert(obj); // 确保栈对象非空// 返回非空队列的尾部元素栈顶元素if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}检查栈是否为空Empty
如果两个队列都为空那么栈为空。
// 检查栈是否为空
bool myStackEmpty(MyStack* obj)
{ assert(obj); // 确保栈对象非空// 如果两个队列都为空栈为空return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}
销毁栈Free
释放栈所使用的资源包括两个队列和栈本身的内存。
// 释放栈所占用的资源
void myStackFree(MyStack* obj)
{assert(obj); // 确保栈对象非空// 销毁两个队列QDestroy(obj-q1);QDestroy(obj-q2);// 释放栈对象所占用的内存free(obj);
}以下是队列的实现:
typedef int QDataType; // 定义队列数据类型为int// 队列节点的结构体定义
typedef struct QueueNode
{QDataType val; // 节点存储的数据struct QueueNode* next; // 指向下一个节点的指针
} QNode;// 队列的结构体定义
typedef struct Queue
{QNode* phead; // 指向队列头部的指针QNode* ptail; // 指向队列尾部的指针int size; // 队列的大小
} Queue;// 函数声明
void QInit(Queue* pq); // 初始化队列
void QDestroy(Queue* pq); // 销毁队列void QPush(Queue* pq, QDataType x); // 向队列中添加元素
void QPop(Queue* pq); // 从队列中移除元素QDataType QueueFront(Queue* pq); // 获取队列头部元素
QDataType QueueBack(Queue* pq); // 获取队列尾部元素bool QueueEmpty(Queue* pq); // 检查队列是否为空
int QueueSize(Queue* pq); // 获取队列的大小// 初始化队列
void QInit(Queue* pq)
{assert(pq); // 断言队列指针非空pq-phead pq-ptail NULL; // 将头指针和尾指针都设为NULLpq-size 0; // 将队列大小设置为0
}// 销毁队列
void QDestroy(Queue* pq)
{assert(pq); // 断言队列指针非空QNode* cur pq-phead;while (cur){QNode* next cur-next; // 保存下一个节点free(cur); // 释放当前节点cur next; // 移动到下一个节点}pq-phead NULL; // 将头指针设为NULLpq-ptail NULL; // 将尾指针设为NULLpq-size 0; // 将队列大小设置为0
}// 向队列中添加元素
void QPush(Queue* pq, QDataType x)
{assert(pq); // 断言队列指针非空QNode* newNode (QNode*)malloc(sizeof(QNode)); // 分配新节点内存if (newNode NULL){perror(malloc fail); // 内存分配失败处理exit(-1);}newNode-val x; // 设置新节点的值newNode-next NULL; // 新节点的下一个节点为NULLif (pq-ptail NULL) // 如果队列为空{pq-phead pq-ptail newNode; // 队列头尾都指向新节点}else{pq-ptail-next newNode; // 将新节点接到队列尾部pq-ptail newNode; // 更新尾指针}pq-size; // 队列大小增加
}// 从队列中移除元素
void QPop(Queue* pq)
{assert(pq); // 断言队列指针非空assert(pq-phead); // 断言队列不为空QNode* Del pq-phead; // 保存要删除的节点pq-phead pq-phead-next; // 更新头指针free(Del); // 释放节点内存if (pq-phead NULL) // 如果队列变空{pq-ptail NULL; // 更新尾指针}pq-size--; // 队列大小减少
}// 获取队列头部元素的值
QDataType QueueFront(Queue* pq)
{assert(pq); // 断言队列指针非空assert(pq-phead); // 断言队列不为空return pq-phead-val; // 返回头部元素的值
}// 获取队列尾部元素的值
QDataType QueueBack(Queue* pq)
{assert(pq); // 断言队列指针非空assert(pq-ptail); // 断言队列不为空return pq-ptail-val; // 返回尾部元素的值
}// 检查队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq); // 断言队列指针非空return pq-phead NULL; // 如果头指针为NULL则队列为空
}// 获取队列的大小
int QueueSize(Queue* pq)
{return pq-size; // 返回队列的大小
}以下是本题的实现:
// 定义一个使用两个队列模拟的栈的结构体
typedef struct
{Queue q1; // 第一个队列Queue q2; // 第二个队列
} MyStack;// 创建一个新的栈
MyStack* myStackCreate()
{// 动态分配内存给新栈MyStack* newStack (MyStack*)malloc(sizeof(MyStack));if (!newStack){perror(malloc fail); // 如果内存分配失败输出错误信息并退出exit(-1);}// 初始化两个队列QInit((newStack-q1));QInit((newStack-q2));return newStack;
}// 将一个元素推入栈中
void myStackPush(MyStack* obj, int x)
{assert(obj); // 确保栈对象非空// 总是将元素推入非空队列中if(!QueueEmpty(obj-q1)){QPush(obj-q1, x);}else{QPush(obj-q2, x);}
}// 从栈中弹出一个元素
int myStackPop(MyStack* obj)
{ assert(obj); // 确保栈对象非空Queue* empty obj-q1; // 一个指向可能为空的队列的指针Queue* noEmpty obj-q2; // 一个指向非空队列的指针// 确定哪个队列是空的哪个是非空的if(!QueueEmpty(empty)){empty obj-q2;noEmpty obj-q1;}// 将元素从非空队列转移到空队列直到只剩下一个元素while(QueueSize(noEmpty) 1){QPush(empty, QueueFront(noEmpty));QPop(noEmpty);}// 弹出并返回最后一个元素int top QueueFront(noEmpty);QPop(noEmpty);return top;
}// 获取栈顶元素
int myStackTop(MyStack* obj)
{assert(obj); // 确保栈对象非空// 返回非空队列的尾部元素栈顶元素if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}// 检查栈是否为空
bool myStackEmpty(MyStack* obj)
{ assert(obj); // 确保栈对象非空// 如果两个队列都为空栈为空return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}// 释放栈所占用的资源
void myStackFree(MyStack* obj)
{assert(obj); // 确保栈对象非空// 销毁两个队列QDestroy(obj-q1);QDestroy(obj-q2);// 释放栈对象所占用的内存free(obj);
}
