栈（Stack）
2018-11-28 本文已影响0人
老王子H
1.栈的特点：
栈也是一种线性结构；
相比数组，栈所对应的操作是数组的子集；
栈只能从一端添加元素，也只能从这一端取出元素，这一端通常称之为"栈顶"；
向栈中添加元素的过程，称之为"入栈"，从栈中取出元素的过程称之为"出栈"；
栈的形象化描述如下图：
image.png
"入栈"的顺序若为1-2-3-4，那么出栈的顺序只能为4-3-2-1，即，栈是一种"后进先出"（Last In First Out）的数据结构；
从用户的角度，只能看到栈顶元素，其它元素对用户是不可见的；
在计算机世界里，"栈"有着不可思议的作用；
2.简单举例"栈"的应用
应用程序中的"撤销"(Undo)操作的底层原理就是通过"栈"来实现的；
程序调用的系统栈，通过下图简单示例：
image.png
image.png
image.png
- 栈的实现
任务目标如下：
Stack<E>
·void push(E) //入栈
·E pop() // 出栈
·E peek() // 查看栈顶元素
·int getSize() // 查看栈中共有多少元素
·boolean isEmpty() // 查看栈是否为空
需要提一下，从用户的角度来看，只要实现上述操作就好，具体底层实现，用户并不关心，实际上，底层确实有多种实现方式。
我们准备在之前实现的动态数组基础上，来实现"栈"这种数据结构。
先定义一个接口Interface，如下：
public interface Stack<E> { // 支持泛型
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
然后实现一个ArrayStack类，如下：
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
//构造函数
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
//无参数构造函数
public ArrayStack() {
array = new Array<>();
}
//实现getSize方法
@Override
public int getSize() {
return array.getSize();
}
//实现isEmpty方法
@Override
public boolean isEmpty() {
return array.isEmpty();
}
//实现getCapacity方法
public int getCapacity() {
return array.getCapacity();
}
//实现push方法
@Override
public void push(E e) {
array.addLast(e);
}
//实现pop方法
@Override
public E pop() {
return array.removeLast();
}
//实现peek方法
public E peek() {
return array.getLast();
}
//方便打印测试
@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 (i != array.getSize() - 1) {
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
Array类的业务逻辑如下：
public class Array<E> {
private E[] data; //设置为private，不希望用户从外部直接获取这些信息，防止用户篡改数据
private int size;
//构造函数，传入数组的容量capacity构造Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
//无参数构造函数，默认数组容量capacity=10
public Array() {
this(10); //这里的capacity是IDE自动添加的提示信息，实际不存在
}
//获取数组中的元素个数
public int getSize() {
return size;
}
//获取数组的容量
public int getCapacity() {
return data.length;
}
//判断数组是否为空
public boolean isEmpty() {
return size == 0;
}
//向数组末尾添加一个新元素e
public void addLast(E e) {
add(size, e);
}
//向数组开头添加一个新元素e
public void addFirst(E e) {
add(0, e);
}
//在index位置插入一个新元素e
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size");
}
if (size == data.length) {
resize(2 * size); //扩大为原容量的2倍
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
//获取index位置的元素
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Index is illegal.");
}
return data[index];
}
//获取最后一个元素
public E getLast() {
return get(size - 1);
}
//获取开头的元素
public E getFirst() {
return get(0);
}
//修改index位置的元素为e
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
}
data[index] = e;
}
//查找数组中是否存在元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
//查看数组中元素e的索引，若找不到元素e，返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
//删除掉index位置的元素，并且返回删除的元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--; //data[size]会指向一个类对象，这部分空间不会被释放loitering objects
data[size] = null;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2); //被利用的空间等于总空间的一半时，将数组容量减少一半
}
return ret;
}
//删除掉数组开头的元素，并返回删除的元素
public E removeFirst() {
return remove(0);
}
//删除掉数组末尾的元素，并返回删除的元素
public E removeLast() {
return remove(size - 1);
}
//如果数组中有元素e，那么将其删除，否则什么也不做
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
@Override
public String toString() { //覆盖父类的toString方法
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size=%d, capacity=%d\n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
}
- 对我们实现的栈进行测试：
public class Main {
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
//测试入栈push
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println(stack);
}
//测试出栈
stack.pop();
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
5.栈的时间复杂度分析
Stack<E>
·void push(E) O(1) 均摊
·E pop() O(1) 均摊
·E peek() O(1)
·int getSize() O(1)
·boolean isEmpty() O(1)
- 栈的另外一个应用——括号匹配
业务逻辑如下：
import java.util.Stack;
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
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 (topChar == '(' && c != ')') {
return false;
}
if (topChar == '[' && c != ']') {
return false;
}
if (topChar == '{' && c != '}') {
return false;
}
}
}
return stack.isEmpty(); //这里很巧妙
}
//测试
public static void main(String[] args){
System.out.println((new Solution()).isValid("()"));
System.out.println((new Solution()).isValid("()[]}{"));
System.out.println((new Solution()).isValid("({[]})"));
System.out.println((new Solution()).isValid("({)}[]"));
}
}
