【Leetcode -225.用队列实现栈 -232.用栈实现队列】

简介: 【Leetcode -225.用队列实现栈 -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就是队头,1,2,3,4就是入队的顺序;

下面参考代码的实现:

实现栈的数据结构,以及栈的基本操作

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);
    }
目录
相关文章
|
1月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
10 0
|
1月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
18 0
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
27 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案,包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法,以及相应的示例操作。
39 2
|
3月前
|
Python
【Leetcode刷题Python】641.循环双端队列
文章介绍了如何实现一个循环双端队列,包括其操作如插入、删除、获取队首和队尾元素,以及检查队列是否为空或已满,并提供了Python语言的实现代码。
22 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2
|
17天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
16 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口