电子报 网站开发,股票软件定制,本地网站建设的步骤过程,网站开发技术标准Leetcode Leetcode -225.用队列实现栈Leetcode -232.用栈实现队列 Leetcode -225.用队列实现栈
题目#xff1a;仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#xff09;。 … Leetcode Leetcode -225.用队列实现栈Leetcode -232.用栈实现队列 Leetcode -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 都保证栈不为空
思路思路是先写一个队列的数据结构我们知道栈的结构是先进后出而队列的结构是先进先出所以我们可以用两个队列一个队列的数据导到另外一个队列中然后留最后一个这最后一个就是要出栈的数据出栈就是这样实现而入栈就是直接找到非空的队列入即可
例如两个队列实现入栈如果两个都为空就随便进一个 入栈完成后如果要出栈就将q1的5个数据的前4个导入q2中 再出q1中的数据即可 下面参考代码的实现
创建队列的数据结构以及实现队列的基本操作 typedef int QDataType;typedef struct QueueNode{struct QueueNode* next;QDataType data;}QNode;typedef struct Queue{QNode* phead;QNode* ptail;QDataType size;}Queue;//初始化队列void QueueInit(Queue* pq){assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;}//入队void QueuePush(Queue* pq, QDataType x){assert(pq);//新节点QNode* newnode (QNode*)malloc(sizeof(QNode));assert(newnode);newnode-data x;newnode-next NULL;//队列为空if (pq-ptail NULL){assert(pq-phead NULL);pq-phead pq-ptail newnode;}//队列不为空else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;}//判断队列是否为空bool QIsEmpty(Queue* pq){assert(pq);return pq-phead NULL pq-ptail NULL;}//出队void QueuePop(Queue* pq){assert(pq);assert(!QIsEmpty(pq));//一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}//多个节点else{//头删QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;}//获取队头QDataType QueueFront(Queue* pq){assert(pq);assert(!QIsEmpty(pq));return pq-phead-data;}//获取队尾QDataType QueueBack(Queue* pq){assert(pq);assert(!QIsEmpty(pq));return pq-ptail-data;}//获取队列的长度int Qsize(Queue* pq){assert(pq);return pq-size;}//释放队列void QueueDestroy(Queue* pq){assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;}定义两个队列 typedef struct{Queue q1;Queue q2;} MyStack;初始化两个队列 MyStack* myStackCreate(){MyStack* obj (MyStack*)malloc(sizeof(MyStack));QueueInit(obj-q1);QueueInit(obj-q2);return obj;}两个队列实现入栈 void myStackPush(MyStack* obj, int x){//哪个队列不为空就入哪个队列if (!QIsEmpty(obj-q1)){QueuePush(obj-q1, x);}else{QueuePush(obj-q2, x);}}两个队列实现出栈 int myStackPop(MyStack* obj){//假设q1为空q2不空Queue* pEmpty obj-q1;Queue* pNonEmpty obj-q2;//如果假设错误就改正if (!QIsEmpty(obj-q1)){pNonEmpty obj-q1;pEmpty obj-q2;}//导数据将非空队列中的数据导入空的队列中非空队列留最后一个数据即是栈顶的数据while (Qsize(pNonEmpty) 1){QueuePush(pEmpty, QueueFront(pNonEmpty));QueuePop(pNonEmpty);}//记录栈顶的数据然后出栈最后返回这个数据int top QueueFront(pNonEmpty);QueuePop(pNonEmpty);return top;}获取两个队列实现的栈顶数据 int myStackTop(MyStack* obj){//获取栈顶的数据即是获取非空队列的队尾数据//我们上面实现了获取队列的队尾的数据所以直接调用函数即可if (!QIsEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}}判断两个队列是否是空队列即是否是空栈 bool myStackEmpty(MyStack* obj){return QIsEmpty(obj-q1) QIsEmpty(obj-q2);}释放两个队列的内存 void myStackFree(MyStack* obj){QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);}Leetcode -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 输入 [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [], [], []] 输出 [null, null, null, 1, 1, false]
解释 MyQueue myQueue new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
提示 1 x 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作
思路思路是先写一个栈的数据结构再定义两个栈一个pushst用来实现入队另一个popst用来实现出队
例如实现入队 将数据入栈到pushst中 需要出队列的时候如果popst为空就将pushst的数据入栈到popst中 此时的1就是队头1234就是入队的顺序 下面参考代码的实现
实现栈的数据结构以及栈的基本操作 typedef int STDataType;typedef struct Stack{STDataType* stack;int top;int capacity;}ST;//初始化void STInit(ST* pst){assert(pst);pst-stack NULL;pst-top 0;pst-capacity 0;}//判断是否为空栈bool STIsEmpty(ST* pst){return pst-top 0;}//进栈void STPushTop(ST* pst, STDataType x){assert(pst);//检查容量if (pst-top pst-capacity){int len pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* newstack (STDataType*)realloc(pst-stack, sizeof(ST) * len);assert(newstack);pst-capacity len;pst-stack newstack;}pst-stack[pst-top] x;pst-top;}//出栈void STPopTop(ST* pst){assert(pst);assert(!STIsEmpty(pst));pst-top--;}//获取栈顶的元素STDataType STTop(ST* pst){assert(pst);assert(!STIsEmpty(pst));return pst-stack[pst-top - 1];}//销毁栈void STDestroy(ST* pst){assert(pst);free(pst-stack);pst-stack NULL;pst-capacity pst-top 0;}定义两个栈一个栈pushst是专门入数据另一个popst是专门出数据 typedef struct{ST pushst;ST popst;} MyQueue;给两个栈初始化 MyQueue* myQueueCreate(){MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;}两个栈实现入队列只需要入pushst的栈即可 void myQueuePush(MyQueue* obj, int x){STPushTop(obj-pushst, x);}从队列的开头移除并返回元素与下面两个栈实现返回队列的队头数据相似我们可以直接调用 myQueuePeek 函数返回队头的元素后再移除队头 int myQueuePop(MyQueue* obj){int front myQueuePeek(obj);STPopTop(obj-popst);return front;}两个栈实现返回队列的队头数据 int myQueuePeek(MyQueue* obj){//如果popst栈为空就将pushst的数据导过来if (STIsEmpty(obj-popst)){while (!STIsEmpty(obj-pushst)){STPushTop(obj-popst, STTop(obj-pushst));STPopTop(obj-pushst);}}//返回popst的栈顶元素即是队列的头return STTop(obj-popst);}两个栈实现判断队列是否是空判断两个栈是否为空即可 bool myQueueEmpty(MyQueue* obj){return STIsEmpty(obj-pushst) STIsEmpty(obj-popst);}释放两个栈的内存 void myQueueFree(MyQueue* obj){STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);}
