一、栈的实现
1. 抽象栈接口方法
public interface Stack<E> {
/**
* 查看栈中元素个数
* @return
*/
int getSize();
/**
* 判断栈是否为空
* @return
*/
boolean isEmpty();
/**
* 进栈
* 将元素 e 压入栈中
* @param e
*/
void push(E e);
/**
* 出栈
* 将栈顶的元素出栈
* @return
*/
E pop();
/**
* 查询栈顶的元素
* @return
*/
E peek();
}
2. 使用数组实现栈
数组的右侧作为栈顶。
public class ArrayStack<E> implements Stack<E> {
private E[] data;
private int size;
public ArrayStack(int capacity) {
data = (E[])new Object[capacity];
this.size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void push(E e) {
if (size == data.length) {
throw new RuntimeException("push failed, Stack is full");
}
data[size] = e;
size++;
}
@Override
public E pop() {
if (isEmpty()) {
throw new NoSuchElementException("pop failed, stack is empty");
}
E ret = data[size - 1];
size--;
return ret;
}
@Override
public E peek() {
if (isEmpty()) {
throw new NoSuchElementException("pop failed, stack is empty");
}
return data[size - 1];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Stack: [");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i != size - 1) {
sb.append(",");
}
}
sb.append("] top");
return sb.toString();
}
}
但用静态数组有个缺点，就是一旦初始化，它的容量就变不了了。
public class DynamicArrayStack<E> implements Stack<E> {
private ArrayList<E> data;
public DynamicArrayStack(int capacity) {
this.data = new ArrayList<>();
}
@Override
public int getSize() {
return data.getSize();
}
@Override
public boolean isEmpty() {
return data.isEmpty();
}
@Override
public void push(E e) {
data.addLast(e);
}
@Override
public E pop() {
return data.removeLast();
}
@Override
public E peek() {
return data.getLast();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Stack: [");
for (int i = 0; i < data.getSize(); i++) {
sb.append(data.get(i));
if (i != data.getSize() - 1) {
sb.append(",");
}
}
sb.append("] top");
return sb.toString();
}
}
3. 链表实现栈
在链表的表头作为栈顶。 push 和 pop 的时间复杂度为 O(1)。
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> linkedList;
public LinkedListStack() {
linkedList = new LinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public void push(E e) {
linkedList.addFirst(e);
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public E peek() {
return linkedList.getFirst();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack：[");
for (int i = linkedList.getSize() - 1; i >= 0; i--) {
res.append(linkedList.get(i));
if (i != 0) {
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
Java中内置的栈是一个类，其底层是基于数组实现的。（可以去看源码）
二、两道练习
1. LeetCode20
https://leetcode-cn.com/problems/valid-parentheses
方案一：
class Solution {
public boolean isValid(String s) {
// 遇到匹配的 就把这两个字符删除
// String 里没有删除字符的操作，首先我们把他变成 StringBuilder
StringBuilder sb = new StringBuilder(s);
int count = sb.length()/2;
for (int i = 0; i < count; i++) {
// j 和 j+1 每次遍历的时候都会消除一对括号
// 那需要遍历多少趟呢？ 需要遍历 s.length/2 趟
for (int j = 0; j < sb.length() - 1; j++) {
char c1 = sb.charAt(j);
char c2 = sb.charAt(j + 1);
// 如果相邻的字符符合要求，则删除
if (isMatched(c1, c2)) {
// 注意 delete 不包含第二个参数
sb.delete(j, j + 2);
break;
}
}
}
return sb.length() == 0;
}
private boolean isMatched(char c1, char c2) {
if ( c1 == '(') return c2 == ')';
else if (c1 == '[') return c2 == ']';
else if (c1 == '{') return c2 == '}';
else return false;
}
}
方案二：碰到左括号进栈，碰到右括号出栈
class Solution {
public boolean isValid(String s) {
if (s == null) return true;
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == ' ') continue;
if (c == '(' || c == '{' || c == '[') {
// 如果是左括号，则直接入栈
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
// 判断栈顶元素是否等于左括号对应的右括号
char topElement = stack.pop();
char matched = '#';
if (c == ')')
matched = '(';
else if (c == ']')
matched = '[';
else
matched = '{';
if (matched != topElement)
return false;
}
}
// 如果栈不为空，那么也算没有匹配好
return stack.isEmpty();
}
}
2. LeetCode155
https://leetcode-cn.com/problems/min-stack
方案一：设置minStack
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
dataStack.push(val);
// 非常要注意：这里要加上 = 号
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int top = dataStack.pop();
if (top == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
方案二：使用一个栈dataStack实现，dataStack中每一个节点，存储两个数据。
class MinStack {
private Stack<Node> stack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
Node node = new Node();
node.val = x;
int min = x;
// 注意 这里的stack可能是空的
if (!stack.isEmpty() && stack.peek().min < x) {
min = stack.peek().min;
}
node.min = min;
stack.push(node);
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek().val;
}
public int getMin() {
return stack.peek().min;
}
}
// 定义一个Node
class Node {
int val;
int min;
Node next;
public Node() {
}
public Node(int val, int min) {
this.val = val;
this.min = min;
}
}
方案三：用链表实现最小栈
class MinStack {
private Node dummyHead;
/** initialize your data structure here. */
public MinStack() {
dummyHead = new Node();
}
public void push(int x) {
int min = x;
Node head = dummyHead.next;
// 注意 这里的head可能是空的
if (head!=null && head.min < x) {
min = head.min;
}
Node node = new Node(x,min);
node.next = dummyHead.next;
dummyHead.next = node;
}
public void pop() {
Node head = dummyHead.next;
if (head != null) {
dummyHead.next = head.next;
head.next = null;
}
}
public int top() {
return dummyHead.next.val;
}
public int getMin() {
return dummyHead.next.min;
}
}
// 定义一个Node
class Node {
int val;
int min;
Node next;
public Node() {
}
public Node(int val, int min) {
this.val = val;
this.min = min;
}
}
