力扣经典题：化栈为队

整体思路：入栈然后出栈，操作就和队列相同了

大佬的代码

typedef struct Node
{
    int val;
    struct Node* next;
}Node;
Node* newNode(int Val)
{
    Node* n=(Node*)malloc(sizeof(Node));
    n->val=Val;
    n->next=NULL;
    return n;
}
void push(Node* Head,int Val)
{
    Node* n=newNode(Val);
    n->next=Head->next;
    Head->next=n;
}
int pop(Node* Head)
{
    Node* n=Head->next;
    Head->next=n->next;
    int result=n->val;
    free(n);
    return result;
}
int peek(Node* Head)
{
    Node* n=Head->next;
    while(n->next!=0)
        n=n->next;
        int result=n->val;
    return result;
}
void del(Node* Head)
{
    while(Head!=0)
    {
        Node* n=Head;
        Head=Head->next;
        free(n);
    }
}
typedef struct {
    Node* stackIn;
    Node* stackOut;
} MyQueue;

bool myQueueEmpty(MyQueue* obj);//函数声明，不然会出错

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* L=(MyQueue*)malloc(sizeof(MyQueue));
    L->stackIn=newNode(0);
    L->stackOut=newNode(0);
    return L;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
      push(obj->stackIn,x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if(myQueueEmpty(obj))
      return -1;
if(obj->stackOut->next==0)
        while(obj->stackIn->next!=0)
            push(obj->stackOut,pop(obj->stackIn));
    return (pop(obj->stackOut));
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if(myQueueEmpty(obj))
    return -1;
    if(obj->stackOut->next==0)
          return(peek(obj->stackIn));
          return((obj->stackOut->next->val)); //返回结点数值，但不能pop，pop会删掉结点

}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
if(obj->stackOut->next==0&&obj->stackIn->next==0)
        return true;
        return false;
}

void myQueueFree(MyQueue* obj) {
    del(obj->stackIn);
    del(obj->stackOut);
    free(obj);
}

函数的详细解析：首先这是一个链栈，而且是带头链栈，只能进行头插和头删，但函数peek返回的是栈底的值，这与传统栈的方法相悖，但是下文函数会有作用。

队列的创建为同时初始化两个栈，队列的入队列为将元素放到第一个元素的队列中，出队列为先判空，然后将in栈的元素出栈再入到out栈，并返回栈顶元素，搜索函数首先返回in栈的栈底元素，如果没有则返回out栈的栈顶元素，其余比较简单

原文地址：https://blog.csdn.net/whcwhc111111/article/details/136669858

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！