当前位置: 首页 > news >正文

怎么做营销型网站设计如何找做网站的公司

怎么做营销型网站设计,如何找做网站的公司,三星网站建设内容,网站建设 需求调研题目一 用队列实现栈 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。 实现 MyStack 类: void push(int x) 将元素 x 压入栈顶。 int pop() 移除…

题目一 用队列实现栈

请你仅使用两个队列实现一个后入先出(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(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/implement-stack-using-queues

 

我们先来分析下题目

要求用两个队列实现一个栈 并且实现四种操作

我们来看第一个Push操作

栈的特点是什么? 先进后出

队列的特点是什么? 先进先出

来看图

有思路了 

图上是两个队列

我们假设 注意啊 是假设

第一行的图 它就是一个栈

那么我们可以判断出 它的数据插入顺序就是 1 2 3 4 

这个时候队列的头就是栈的尾

如果我们这个时候需要删除栈的头数据应该怎么办呢?

我们都知道队列的数据只能是从头开始出

也就是说 比如要将队列前面的1 2 3 全部出完之后才能开始出 4

但是我们不可能会抛弃之前的数据啊

这个时候我们就想到了第二个队列的用处了

只需要将我Pop的数据使用第二个队列来接受就可以

实现起来的图大概是这样子

 

这个时候我们就能删除掉头数据了

如果需要再删除一个怎么办呢?

那么只需要将上面的操作再重复一次就好了

这个时候的插入数据只需要往不为空的队列插入数据就可以了

要求首元素就是返回队列的尾

要求尾元素就是返回队列的头

也就是两个步骤

1.保持一个队列为空,一个队列存数据

2.出栈,把前面的数据倒入空队列

接下来我们来实现代码

把所有的队列代码以及接口函数拷贝进去

第一步 定义结构体

我们来看这个 我们应该怎么定义我们的Stack结构体呢?

既然是两个队列的实现的

那么是不是可以放两个队列的结构在里面?

仔细一想好像可行

我们来试试

typedef struct {Queue q1;Queue q2;
} MyStack;

画个图方便大家理解

三个结构体的关系一目了然

 第二步 实现创建(初始化)

MyStack* myStackCreate() {MyStack*pst = ( MyStack*)malloc(sizeof( MyStack));if(pst==NULL){perror("malloc fail");return NULL;}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}

第三步 插入数据

这里要判断队列是否为空,不为空就插入数据,两个都为空就随机一个队列插入数据

看代码:

void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

第四步 删除数据

这是最难的部分,需要我们倒数据

我们先写出两个指针来判断空和非空

如果说我们的判断不正确的话 那么我们就将这两个指针翻转一下就好了

代码整体表现不变

int myStackPop(MyStack* obj) {Queue*emptyQ = &obj->q1;Queue*nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQ = &obj->q2;nonemptyQ=&obj->q1;}//倒数据while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//记录删除值 删掉int top = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}

第五步 返回头的值

这里我们可以分两种情况讨论

如果1不为空就返回1的尾值

如果2不为空就返回2的尾值

int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

第六步 判空

这步就很简单,只需要判断1和2是否都为空,都为空即空

bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

第七步 释放

这里要依次释放销毁,类似套娃

void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

源码

typedef int QDateType;
typedef struct QueueNode
{struct QueueNode* next;QDateType date;
}QNode;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//队进
void QueuePush(Queue* pq, QDateType x);
//队出
void QueuePop(Queue* pq);
//判断为空
bool QueueEmpty(Queue* pq);
//个数
int QueueSize(Queue* pq);
//队尾
QDateType QueueBack(Queue* pq);
//对头
QDateType QueueFront(Queue* pq);
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//两个结构体依次销毁 先销毁QNodeQNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}//再置空Queuepq->head = pq->tail = NULL;pq->size = 0;
}
//队进
void QueuePush(Queue* pq, QDateType x)
{assert(pq);//开辟新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}//赋值newnode->next = NULL;newnode->date = x;//判断是否为空if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}//个数要++pq->size++;
}
//队出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head!=NULL);//只有一个节点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{//保存下一位QNode* next = pq->head->next;free(pq->head);pq->head = next;//迭代}//个数要--pq->size--;
}
//判断为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
//大小
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//队尾
QDateType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->date;
}
//对头
QDateType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->date;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack*pst = ( MyStack*)malloc(sizeof( MyStack));if(pst==NULL){perror("malloc fail");return NULL;}QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue*emptyQ = &obj->q1;Queue*nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){emptyQ = &obj->q2;nonemptyQ=&obj->q1;}//倒数据while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//记录删除值 删掉int top = QueueFront(nonemptyQ);QueuePop(nonemptyQ);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

http://www.zhongyajixie.com/news/16099.html

相关文章:

  • 如何制作手机版网站怎样创建网页
  • 移动网站建设方面泉州seo培训
  • 我想帮别人做网站有这样的平台吗个人接外包的网站
  • 网站制作公司一站式服务2021年网络十大关键词
  • java在线阅读小说网站开发网站搭建谷歌seo
  • 永川网站制作联系电话广州头条新闻最新
  • 怎样做网站刷qq会员永久上海网络优化seo
  • 做网站用微软雅黑产品推广软文200字
  • 怎样做机械租赁的网站如何推广普通话的建议6条
  • 阿里云服务器搭建网站深圳搜索引擎优化推广便宜
  • 免费网站管理软件域名注册信息查询
  • 云南火电建设公司网站百度软件商店
  • wordpress调用评论抚顺seo
  • b2b模式网站洛阳市网站建设
  • 宁波网站建设多少钱windows优化大师免费
  • wordpress 目录 导航站万网官网
  • 淘宝客商城网站建设网络服务提供者收集和使用个人信息应当符合的条件有
  • 汕头网站建设网页设计网站
  • 那个平台能免费做网站外贸网站都有哪些
  • 做网站的步骤培训心得体会500字
  • 单页面网站如何优化引流代写文章兼职
  • 开发一个网站需要多长时间郑州网络推广代理
  • 有没有一些帮做名片的网站沈阳全网推广公司哪家好
  • 做淘宝联盟网站公司网站的推广方案
  • cms资源石景山区百科seo
  • 济南网站设计开发唯尚广告联盟
  • 商城网站建设协议百度关键字排名软件
  • 专业外包网站建设公司搜索引擎优化是做什么
  • 如何做同城信息网站韩国比分预测
  • 设计专业宜昌网站seo收费