1. 概述
今天来看看栈这种线性数据结构，非常的基础，我举个例子你就能明白了。比如你桌子上堆放的一摞文件，最先放的在最下面，拿的时候也是最后拿，最后放的在最上面，拿的时候也先拿到。这种满足了 先进后出，后进先出 特点的数据结构，就叫做栈。
相信结合上图你能够看到，栈这种数据结构，插入和删除的操作都被局限在了栈的一端，插入数据叫做入栈，删除数据叫做出栈。
2. 栈的实现
栈有两种实现方式，一是使用数组，这种实现叫做顺序栈，二是使用链表，叫做链式栈。下面是其实现的代码：
顺序栈的代码实现
public class ArrayStack { private String[] items;//储存数据的数组 private int size;//栈中数据个数 public ArrayStack(int capacity) { this.items = new String[capacity]; this.size = 0; } public ArrayStack() { this(10); } //入栈 public boolean push(String value) { //如果栈已满，则扩容数组 if(size == items.length) resize(items.length * 2); items[size ++] = value; return true; } //出栈 public String pop() { if(size == 0) return null; return items[-- size]; } //获取栈顶元素 public String peek() { if(size == 0) return null; return items[size - 1]; } //重新设置数组大小，用于扩容 private void resize(int newSize) { String[] temp = new String[newSize]; for (int i = 0; i < items.length; i++) { temp[i] = items[i]; } items = temp; } }
链式栈的代码实现
public class LinkedListStack { private Node head = null;//栈顶元素 private int size = 0;//栈中元素个数 //入栈 public boolean push(String value) { Node node = new Node(value); if(head == null) { head = node; this.size ++; return true; } node.next = head; head = node; this.size ++; return true; } //出栈 public String pop() { if(head == null) return null; String result = head.data; head = head.next; this.size --; return result; } //获取栈顶元素 public String peek() { if(head == null) return null; return head.getData(); } //判断栈是否为空 public boolean isEmpty() { return this.head == null; } //栈中元素的个数 public int size() { return this.size; } //清空栈 public void clear() { this.head = null; this.size = 0; } //打印栈中所有的元素 public void print() { Node pNode = head; while(pNode != null) { System.out.print(pNode.getData() + " "); pNode = pNode.next; } System.out.println(); } //定义栈的节点 public static class Node{ private String data; private Node next; public Node(String data) { this.data = data; this.next = null; } public String getData() { return data; } } }
3. 栈练习
下面思考一个练习题：如何使用栈来实现浏览器的前进和后退功能？我们在使用浏览器的时候，会新打开一个网页，如果连续打开了多个网页，我们可以后退，也可以前进，如果这时候又新打开了一个网页，那就不能在新页面中前进了。使用栈，我们可以轻松实现这个功能。
浏览器的前进后退功能代码实现
public class LinkedListStack { private Node head = null;//栈顶元素 private int size = 0;//栈中元素个数 //入栈 public boolean push(String value) { Node node = new Node(value); if(head == null) { head = node; this.size ++; return true; } node.next = head; head = node; this.size ++; return true; } //出栈 public String pop() { if(head == null) return null; String result = head.data; head = head.next; this.size --; return result; } //获取栈顶元素 public String peek() { if(head == null) return null; return head.getData(); } //判断栈是否为空 public boolean isEmpty() { return this.head == null; } //栈中元素的个数 public int size() { return this.size; } //清空栈 public void clear() { this.head = null; this.size = 0; } //打印栈中所有的元素 public void print() { Node pNode = head; while(pNode != null) { System.out.print(pNode.getData() + " "); pNode = pNode.next; } System.out.println(); } //定义栈的节点 public static class Node{ private String data; private Node next; public Node(String data) { this.data = data; this.next = null; } public String getData() { return data; } } }
