网站开发的基本流程和步骤,怎么把视频制作成链接,中国网站访问量排行,动易网站制作教程1. 前言
通过前面栈的实现和详解大家对队列应该有一定熟悉了#xff0c;现在上强度开始做题吧
栈详解#xff1a;http://t.csdnimg.cn/9Fsbs
本体的做题思路也可以参考上一篇文章#xff0c;就是有一点点不同。 用队列实现栈#xff1a;http://t.csdnimg.cn/V2qjW
2. …1. 前言
通过前面栈的实现和详解大家对队列应该有一定熟悉了现在上强度开始做题吧
栈详解http://t.csdnimg.cn/9Fsbs
本体的做题思路也可以参考上一篇文章就是有一点点不同。 用队列实现栈http://t.csdnimg.cn/V2qjW
2. OJ题目训练 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双端队列来模拟一个栈只要是标准的栈操作即可。 题目解析
本体的大概思路与上题类似通过两个栈互相调换数据来实现队列。
方法
假设放入的数据为1234如果要实现队列那么我们第一个拿出的数据就应该是1先进先出而如果是栈第一个拿出的数据则是4后进先出
再将数据导出到另一个栈就能实现队列的结构了 特殊情况
当第二个栈还有数据而有需要添加数据的情况该怎么处理呢 不要慌当第二个栈不为空我们把所有数据都导出再把第一个栈里的数据导入就依然可以实现队列的结构了。 导出所有的数据 所以得出结论当栈2非空时就可以导出数据直到为空再将栈1全部导到栈2再导出栈2的数据
注意要点
需要先实现栈的各种操作详见文章头在导出队列的函数时可以实现复用运用栈2的数据
附源代码
#include stdio.h
#includestdlib.h
#include assert.h
#includestdbool.htypedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);int STSize(ST* ps);
bool STEmpty(ST* ps);void STInit(ST* ps)
{ assert(ps);ps-a NULL;ps-capacity 0;ps-top 0;
}void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}void STPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;}int STSize(ST* ps)
{assert(ps);return ps-top;}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;}STDataType STTop(ST* ps)
{assert(ps);assert(ps-top0);return ps-a[ps-top - 1];}typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);
}int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-popst)){while(!STEmpty(obj-pushst)){STPush(obj-popst,STTop(obj-pushst)); //将输入栈的数据导入到输出栈中STPop(obj-pushst);}}return STTop(obj-popst); //输出输出栈的头节点也就是队列
}int myQueuePop(MyQueue* obj) {int front myQueuePeek(obj);STPop(obj-popst);return front;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-pushst)STEmpty(obj-popst);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-pushst);STDestroy(obj-popst);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);
*/
