这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！