1.用栈实现队列
solution：两个栈，stack1，stack2，将元素全部压入stack2，然后从stack1弹出（用两个栈实现队列和队列实现栈，画个图就一目了然）栈中的push,pop对应offer,poll，二者的top都等于peek
class MyQueue {
/** Initialize your data structure here. */
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
/** Push element x to the back of queue. */
public void push(int x) {
stack2.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (stack1.isEmpty()) {
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
return stack1.pop();
}
/** Get the front element. */
public int peek() {
if (stack1.isEmpty()) {
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
return stack1.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
if(stack1.isEmpty() && stack2.isEmpty()) {
return true;
} else {
return false;
}
}
}
2.用队列实现栈
solution:就用一个队列实现，交换元素，抓住栈的先入后出
class MyStack {
/** Initialize your data structure here. */
Queue<Integer> queue = new LinkedList<>();
/** Push element x onto stack. */
public void push(int x) {
queue.offer(x);
int size = queue.size();
for (int i = 0; i < size - 1; ++i) {
queue.offer(queue.poll());
}
}
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();
}
}
3.Valid Parentheses
[Valid Parentheses]https://leetcode.com/problems/valid-parentheses/description/
solution:利用栈的特性，先入后出，把所有的左括号压入栈，然后用右括号来匹配，如果弹出的不是相对应的左括号，就返回false
class Solution {
public boolean isValid(String s) {
Stack<Character> pair = new Stack<>();
if (s.length() == 0) {
return false;
}
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
pair.push(s.charAt(i));
} else if (s.charAt(i) == ')') {
if (pair.isEmpty() || pair.pop() != '(') {
return false;
}
} else if (s.charAt(i) == ']') {
if (pair.isEmpty() || pair.pop() != '[') {
return false;
}
} else if (s.charAt(i) == '}') {
if (pair.isEmpty() || pair.pop() != '{') {
return false;
}
}
}
return pair.isEmpty();
}
}
4.用数组实现栈
solution：利用数组特性
public class Stack {
/*
* @param x: An integer
* @return: nothing
*/
private List<Integer> array = new ArrayList<Integer>();
public void push(int x) {
// write your code here
array.add(x);
}
/*
* @return: nothing
*/
public void pop() {
// write your code here
int n = array.size();
if (n > 0) {
array.remove(n - 1);
}
return;
}
/*
* @return: An integer
*/
public int top() {
// write your code here
int n = array.size();
return array.get(n - 1);
}
/*
* @return: True if the stack is empty
*/
public boolean isEmpty() {
// write your code here
return array.size() == 0;
}
}
5.用链表实现队列
solution:队列的基本操作，插入在队尾，删除在队头
class MyQueue:
"""
@param: item: An integer
@return: nothing
"""
def __init__(self):
self.dummy = ListNode(-1)
self.tail = self.dummy
def enqueue(self, item):
# write your code here
node = ListNode(item)
self.tail.next = node
self.tail = node
"""
@return: An integer
"""
def dequeue(self):
# write your code here
item = self.dummy.next.val
self.dummy.next = self.dummy.next.next
if self.dummy.next is None:
self.tail = self.dummy
return item
def empty(self):
return self.dummy.next is None
