共计 2571 个字符，预计需要花费 7 分钟才能阅读完成。
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 BrowserForwardAndBack {
private LinkedListStack forward;
private LinkedListStack back;
public BrowserForwardAndBack() {
this.forward = new LinkedListStack();
this.back = new LinkedListStack();
}
// 新打开一个页面
public void open(String url) {
// 将其保存到前进的栈中
this.forward.push(url);
// 如果后退的栈不为空，则清空后退的栈
if(!back.isEmpty()) back.clear();
System.out.println(“ 新打开一个页面，url = ” + url);
}
// 前进，从 back 中取出内容到 forward 中
public void goForward() {
if(this.back.isEmpty()) {
System.out.println(“ 前面没有页面！”);
return;
}
this.forward.push(this.back.pop());
System.out.println(“ 前进一个页面，当前页面为：” + this.forward.peek());
}
// 后退，从 forward 中取出内容到 back 中
public void goBack() {
if(this.forward.size() <= 1) {
System.out.println(“ 后面没有页面！”);
return;
}
this.back.push(this.forward.pop());
System.out.println(“ 后退一个页面，当前页面为：” + this.forward.peek());
}
}
