制作网站的过程是对信息的,龙海市住房和城乡建设局网站,万网商标查询,简单免费模板力扣232 用栈实现队列
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a;
实现 MyQueue 类#xff1a;
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并…力扣232 用栈实现队列
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作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.void push(int x) 将元素 x 推到队列的末尾关于进队没有具体的返回值对于系统如何进行存储也没有过多要求我们就定义一个pushst用来进队元素的栈将元素直接push即可。
2.int pop() 从队列的开头移除并返回元素这里就有讲究了出栈是将最后进入的元素返回但出队却是将最先进入的元素返回但又不能取到栈底元素所以我们需要再定义一个栈来进行出队用定义为popst出队的时候只需要将pushst里的元素全部出栈进栈到popst中再返回popst栈顶元素自然就是需要出队的元素了。
3.int peek() 返回队列开头的元素此功能与上面的思路完全一样的但先实现此功能对于上面的出队功能会非常方便稍后在代码里会进行讲解。
4.boolean empty() 如果队列为空返回 true 否则返回 false 直接判断两个栈同时为空即可。
完整代码
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
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);// 初始化栈
void StackInit(Stack* ps)
{assert(ps);ps-a NULL;ps-_capacity 0;ps-_top 0;
}// 入栈
void StackPush(Stack* ps, STDataType data)
{assert(ps);//检查是否栈满if (ps-_top ps-_capacity){int newcapacity ps-_capacity 0 ? 4 : ps-_capacity * 2;Stack* ptr realloc(ps-a, sizeof(STDataType) * newcapacity);if (ptr NULL){perror(realloc fail);return;}ps-a ptr;ps-_capacity newcapacity;}//入栈ps-a[ps-_top] data;ps-_top;
}// 出栈
void StackPop(Stack* ps)
{assert(ps);assert(ps-_top 0);ps-_top--;
}// 获取栈顶元素
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps-_top 0);return ps-a[ps-_top-1];
}// 获取栈中有效元素个数
int StackSize(Stack* ps)
{assert(ps);return ps-_top;
}
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
int StackEmpty(Stack* ps)
{assert(ps);if (ps-_top 0){return 1;}else{return 0;}
}// 销毁栈
void StackDestroy(Stack* ps)
{assert(ps);free(ps-a);ps-_capacity 0;ps-_top 0;
}//实现区typedef struct {Stack popst;Stack pushst;} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj(MyQueue*)malloc(sizeof(MyQueue));StackInit(obj-popst);StackInit(obj-pushst);return obj;
}
void myQueuePush(MyQueue* obj, int x) {StackPush(obj-pushst,x);}int myQueuePop(MyQueue* obj) {int TopmyQueuePeek(obj);//将peek的元素放到top里面StackPop(obj-popst);return Top;
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(obj-popst))//只要popst为空将pushst的数据放到popst中要考虑到push和pop同时有数据的情况{while(!StackEmpty(obj-pushst)){StackPush(obj-popst,StackTop(obj-pushst));StackPop(obj-pushst); } }return StackTop(obj-popst);//返回pop栈顶元素
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-pushst)StackEmpty(obj-popst);
}void myQueueFree(MyQueue* obj) {StackDestroy(obj-popst);StackDestroy(obj-pushst);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);
*/
