加盟网站分页怎么做seo,佛山网约车租赁公司,建立平台什么意思,网站建设及编辑岗位职责. 个人主页#xff1a;晓风飞 专栏#xff1a;LeetCode刷题|数据结构|Linux|C语言 路漫漫其修远兮#xff0c;吾将上下而求索 文章目录 题目要求#xff1a;实现 MyStack 类#xff1a;注意#xff1a;示例#xff1a;解释#xff1a;提示#xff1a; 解题核心概念数据…
. 个人主页晓风飞 专栏LeetCode刷题|数据结构|Linux|C语言 路漫漫其修远兮吾将上下而求索 文章目录 题目要求实现 MyStack 类注意示例解释提示 解题核心概念数据结构的定义初始化队列入队操作出队操作查看队列前端元素检查队列是否为空释放队列 要做题目的点击这里–栈和队列oj题——232. 用栈实现队列
题目要求 请你仅使用两个队列实现一个后入先出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 都保证栈不为空 进阶你能否仅用一个队列来实现栈。 解题核心概念
在我们的实现中我们定义了两个栈 s1 和 s2。栈 s1 负责处理入队操作而栈 s2 负责出队操作。通过这种方式我们可以保证队列的 FIFO 特性即首先入队的元素将首先出队。
数据结构的定义
首先我们定义了栈的结构体 ST它包含一个指向数组的指针、一个表示栈顶的变量和一个表示栈容量的变量。然后我们定义了队列的结构体 MyQueue它包含两个栈 s1 和 s2。
// 使用两个栈实现的队列结构体定义
typedef struct
{ST s1; // 第一个栈用于入队操作ST s2; // 第二个栈用于出队操作
} MyQueue;
初始化队列
使用 myQueueCreate 函数来初始化队列。在这个函数中我们分配内存给 MyQueue 结构体并初始化两个栈。
MyQueue* myQueueCreate()
{MyQueue* newQu (MyQueue*)malloc(sizeof(MyQueue));STInit(newQu-s1); // 初始化第一个栈STInit(newQu-s2); // 初始化第二个栈 return newQu; // 返回新创建的队列
}入队操作
入队操作非常简单我们只需将元素推入栈 s1。
// 将一个元素推入队列
void myQueuePush(MyQueue* obj, int x)
{STPush(obj-s1, x); // 将元素推入第一个栈
}出队操作
出队操作稍微复杂一些。我们需要确保队列的 FIFO 性质所以当我们想要进行出队操作时我们首先检查栈 s2。如果栈 s2 为空我们将栈 s1 中的所有元素逆序转移到栈 s2 中然后从栈 s2 中弹出元素。
// 如有必要将元素从第一个栈转移到第二个栈
void TransferIfNeeded(MyQueue* obj)
{if (STEmpty(obj-s2)) // 检查第二个栈是否为空{while (!STEmpty(obj-s1)) // 当第一个栈不为空时{// 将第一个栈的栈顶元素转移到第二个栈STPush(obj-s2, STTop(obj-s1));STPop(obj-s1); // 弹出第一个栈的栈顶元素}}
}// 从队列中弹出一个元素
int myQueuePop(MyQueue* obj)
{TransferIfNeeded(obj); // 确保所有元素都在第二个栈int Top STTop(obj-s2); // 获取第二个栈的栈顶元素STPop(obj-s2); // 弹出第二个栈的栈顶元素return Top; // 返回弹出的元素
}查看队列前端元素
查看队列前端元素的实现与出队操作类似但不移除元素。
// 查看队列的前端元素
int myQueuePeek(MyQueue* obj)
{TransferIfNeeded(obj); // 确保所有元素都在第二个栈return STTop(obj-s2); // 返回第二个栈的栈顶元素
}检查队列是否为空
队列为空的条件是两个栈都为空。
// 检查队列是否为空
bool myQueueEmpty(MyQueue* obj)
{// 如果两个栈都为空那么队列为空return STEmpty(obj-s1) STEmpty(obj-s2);
}释放队列
最后我们需要一个函数来释放队列占用的资源。
// 释放队列所占用的资源
void myQueueFree(MyQueue* obj)
{STDestroy(obj-s1); // 销毁第一个栈STDestroy(obj-s2); // 销毁第二个栈free(obj); // 释放队列结构体占用的内存
}以下是栈的实现:
typedef int STDataType;
typedef struct Stack
{STDataType* a;STDataType top; STDataType capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);// 初始化栈
void STInit(ST* pst)
{assert(pst);pst-a NULL; // 初始时数组指针为空pst-top 0; // 栈顶指针初始为0表示栈为空pst-capacity 0; // 初始容量为0
}// 销毁栈
void STDestroy(ST* pst)
{assert(pst);free(pst-a); // 释放栈内部的数组空间pst-a NULL; // 将数组指针置为空pst-top 0; // 栈顶指针重置为0pst-capacity 0; // 容量重置为0
}// 检查并扩展栈的容量
void SLCheckCapacity(ST* pst)
{assert(pst);if (pst-top pst-capacity){int newCapacity (pst-capacity 0) ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(1); // 如果内存分配失败则退出程序}pst-a tmp;pst-capacity newCapacity;}
}// 向栈中推入一个元素
void STPush(ST* pst, STDataType x)
{assert(pst);SLCheckCapacity(pst); // 检查并扩展容量pst-a[pst-top] x; // 存放元素pst-top; // 栈顶指针增加
}// 从栈中弹出一个元素
void STPop(ST* pst)
{assert(pst);assert(pst-top 0); // 确保栈不为空pst-top--; // 栈顶指针减少
}// 获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0); // 确保栈不为空return pst-a[pst-top - 1]; // 返回栈顶元素
}// 检查栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0; // 如果栈顶指针为0则栈为空
}// 获取栈的大小
int STSize(ST* pst)
{assert(pst);return pst-top; // 返回栈顶指针的位置即栈的大小
}以下是本题的实现: // 使用两个栈实现的队列结构体定义
typedef struct
{ST s1; // 第一个栈用于入队操作ST s2; // 第二个栈用于出队操作
} MyQueue;// 创建并初始化队列
MyQueue* myQueueCreate()
{MyQueue* newQu (MyQueue*)malloc(sizeof(MyQueue));STInit(newQu-s1); // 初始化第一个栈STInit(newQu-s2); // 初始化第二个栈 return newQu; // 返回新创建的队列
}// 将一个元素推入队列
void myQueuePush(MyQueue* obj, int x)
{STPush(obj-s1, x); // 将元素推入第一个栈
}// 如有必要将元素从第一个栈转移到第二个栈
void TransferIfNeeded(MyQueue* obj)
{if (STEmpty(obj-s2)) // 检查第二个栈是否为空{while (!STEmpty(obj-s1)) // 当第一个栈不为空时{// 将第一个栈的栈顶元素转移到第二个栈STPush(obj-s2, STTop(obj-s1));STPop(obj-s1); // 弹出第一个栈的栈顶元素}}
}// 从队列中弹出一个元素
int myQueuePop(MyQueue* obj)
{TransferIfNeeded(obj); // 确保所有元素都在第二个栈int Top STTop(obj-s2); // 获取第二个栈的栈顶元素STPop(obj-s2); // 弹出第二个栈的栈顶元素return Top; // 返回弹出的元素
}// 查看队列的前端元素
int myQueuePeek(MyQueue* obj)
{TransferIfNeeded(obj); // 确保所有元素都在第二个栈return STTop(obj-s2); // 返回第二个栈的栈顶元素
}// 检查队列是否为空
bool myQueueEmpty(MyQueue* obj)
{// 如果两个栈都为空那么队列为空return STEmpty(obj-s1) STEmpty(obj-s2);
}// 释放队列所占用的资源
void myQueueFree(MyQueue* obj)
{STDestroy(obj-s1); // 销毁第一个栈STDestroy(obj-s2); // 销毁第二个栈free(obj); // 释放队列结构体占用的内存
}
/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj myQueueCreate();* myQueuePush(obj, x);* int param_2 myQueuePop(obj);* int param_3 myQueuePeek(obj);* bool param_4 myQueueEmpty(obj);* myQueueFree(obj);
*/
