LeetCode算法题-Implement Stack Using Queues
这是悦乐书的第193次升级,第198篇原创
01 看题和准备
今天详情的是LeetCode算法题中Easy级别的第54题(顺位题号是225)。使用队列实现栈的以下操作:
push(x) – 将元素x推入栈。
pop() – 删除栈顶部的元素。
top() – 获取顶部元素。
empty() – 返回栈能否为空。
例如:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); //返回2
stack.pop(); //返回2
stack.empty(); //返回false
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
借助ArrayList。进栈利用list的add方法。出栈时先获取list最后一位元素存起来,而后再删除最后一位元素,再返回先前存起来的最后一位元素。获取栈顶时,返回list最后一位元素就可。判空可以直接利用list的isEmpty方法。
class MyStack { List<Integer> list = null; /** Initialize your data structure here. */ public MyStack() { list = new ArrayList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { list.add(x); } /** Removes the element on top of the stack and returns that element. */ public int pop() { int top = list.get(list.size()-1); list.remove(list.size()-1); return top; } /** Get the top element. */ public int top() { return list.get(list.size()-1); } /** Returns whether the stack is empty. */ public boolean empty() { return list.isEmpty(); }}03 第二种解法
利用队列。
进栈直接使用queue的add方法或者者offer方法。
出栈时,由于队列是先进先出的特性,所以需要先把队列里的元素poll出来再add进去,但是此操作只能进行queue的size-1次,比方:进栈顺序是1->2->3,进行一次出队列再进队列操作后,2->3->1,再进行一次出队列再进队列的操作,3->1->2,假如你再操作一次就复原了,所以只能操作queue的size-1次。最后再使用队列的poll方法,实现出栈。
栈顶,和出栈的思路一样,不过在把队列里的元素poll出来再add进去size-1次后,先要将顶获取到,可以直接使用队列的peek方法,而后再来一次poll出来再add进去,就把队列元素的顺序复原了。方便下次操作。
判空可以直接使用队列自身的isEmpty方法。
class MyStack2 { Queue<Integer> queue = null; int size ; /** Initialize your data structure here. */ public MyStack2() { queue = new LinkedList<Integer>(); size = 0; } /** Push element x onto stack. */ public void push(int x) { queue.add(x); size++; } /** Removes the element on top of the stack and returns that element. */ public int pop() { for (int i=1; i<size; i++) { queue.add(queue.poll()); } size--; return queue.poll(); } /** Get the top element. */ public int top() { for (int i=1; i<size; i++) { queue.add(queue.poll()); } int res = queue.peek(); queue.add(queue.poll()); return res; } /** Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty(); }}04 第三种解法
还是使用队列。不过此解法除了入栈重新实现外,其余的出栈、栈顶、判空都是使用了队列的方法,所以重点讲下入栈就可。
入栈时,首先利用队列的add方法,而后利用循环,把队列里的元素poll出来再add进去,此循环只执行队列的size-1次,执行size次会复原。
class MyStack3 { Queue<Integer> queue = null; /** Initialize your data structure here. */ public MyStack3() { queue = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { queue.add(x); for (int i=0; i<queue.size()-1; i++) { queue.add(queue.poll()); } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue.poll(); } /** Get the top element. */ public int top() { return queue.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue.isEmpty(); }}05 小结
算法专题目前已连续日更超过一个月,算法题文章54+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Implement Stack Using Queues