- 概述今天来看看栈这种线性数据结构，非常的基础，我举个例子你就能明白了。比如你桌子上堆放的一摞文件，最先放的在最下面，拿的时候也是最后拿，最后放的在最上面，拿的时候也先拿到。这种满足了 先进后出，后进先出 特点的数据结构，就叫做栈。相信结合上图你能够看到，栈这种数据结构，插入和删除的操作都被局限在了栈的一端，插入数据叫做入栈，删除数据叫做出栈。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()); }}