首先想要实现栈，就得知道栈为何物，以下一段摘抄至百度百科：
栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的模型图
大致了解了栈这种数据结构后，我们就尝试着将其实现吧。
首先，我们需要定义一个Stack接口，代码如下：
public interface Stack<E> { int getSize();//得到栈的大小 boolean isEmpty();//判断栈是否为空 void push(E e);//压栈 E pop();//出栈 E peek();//查看栈顶元素 }
由于在<数据结构1>（https://www.cnblogs.com/LASloner/p/10721407.html）中我们已经实现了ArrayList，所以今天我们就用Array来作为Stack的数据存储方式吧：
public class ArrayStack<E> implements Stack<E>{ //这里用的是自己实现的Array，当然读者可以直接用Java自带的ArrayList,效果相同 private Array<E> array; //有参构造 public ArrayStack(int capacity){ array=new Array<E>(capacity); } //无参构造 public ArrayStack() { array=new Array<E>(); } //获取栈的大小 @Override public int getSize() { return array.getSize(); } //判断栈是否为空 @Override public boolean isEmpty() { return array.isEmpty(); } //压栈（向栈顶添加元素） @Override public void push(E e) { array.addLast(e); } //出栈（取出栈顶元素） @Override public E pop() { return array.removeLast(); } //查看栈顶元素 @Override public E peek() { return array.get(array.getSize()-1); } @Override public String toString() { StringBuilder res=new StringBuilder(); res.append("Stack: "); res.append(‘[‘); for (int i=0;i<array.getSize();i++) { res.append(array.get(i)); if(array.getSize()-1!=i) res.append(", "); } res.append("] top"); return res.toString(); } }
当当，这就实现了栈的结构，其实也没那么复杂嘛（当然实现栈的数据存储方式还有很多，不仅仅是数组，还有链表，在我们学习过链表后，就尝试用链表也实现一下）
okey,让我们测试一下
Main代码：
public class Main { public static void main(String[] args) { ArrayStack<Integer> stack = new ArrayStack<>(); for(int i = 0 ; i < 5 ; i ++){ stack.push(i); System.out.println("入栈："+stack); } System.out.println("--------------------------"); stack.pop(); System.out.println("出栈："+stack); System.out.println("--------------------------"); System.out.println("查看栈顶元素："+stack.peek()); System.out.println(stack); } }
输出如下：
入栈：Stack: [0] top 入栈：Stack: [0, 1] top 入栈：Stack: [0, 1, 2] top 入栈：Stack: [0, 1, 2, 3] top 入栈：Stack: [0, 1, 2, 3, 4] top -------------------------- 出栈：Stack: [0, 1, 2, 3] top -------------------------- 查看栈顶元素：3 Stack: [0, 1, 2, 3] top
那老规矩，再看一下栈中各种操作的时间复杂度吧：
ArrayStack<E>: void push(E) O(1) E pop() O(1) E peek() O(1) int getSize() O(1) boolean isEmpty O(1)
最后用一个实例来应用一下 栈 这种数据结构吧：
/*有效的括号 给定一个只包括 ‘(‘，‘)‘，‘{‘，‘}‘，‘[‘，‘]‘ 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 */ public class Solution { public boolean isValid(String s) { ArrayStack<Character> stack=new ArrayStack<>(); for(int i=0;i<s.length();i++) { char c=s.charAt(i); if(c == ‘(‘ || c == ‘[‘ || c == ‘{‘) stack.push(c); else{ if(stack.isEmpty())return false; char topChar=stack.pop(); if(c == ‘)‘ && topChar != ‘(‘) return false; if(c == ‘]‘ && topChar != ‘[‘) return false; if(c == ‘}‘ && topChar != ‘{‘) return false; } } return true; } public static void main(String[] args) { System.out.println(new Solution().isValid("()[]{}")); System.out.println(new Solution().isValid("([)]")); } }
输出：
true
flase
ok，今天的学习就这样了。有什么问题，希望各位能够多多指正。
对于学习，四个字概括：至死方休
<数据结构系列2>栈的实现与应用（LeetCode<有效的的括号>）
原文：https://www.cnblogs.com/LASloner/p/10831942.html