07、栈数据结构特点？如何实现一个栈？

### 考点分析
浏览器的前进、后退功能，我想你肯定很熟悉吧？ 当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页 面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。 但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页 面 c 了。 假设你是 Chrome 浏览器的开发工程师，你会如何实现这个功能呢？

### 典型回答
关于“栈”，我有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候， 都是从下往上一个一个放取的时候，我们也是从上往下一个一个地依次取，不能从中间任 意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。

![输入图片说明](https://images.gitee.com/uploads/images/2020/1031/120455_805210ae_1767738.png "屏幕截图.png")
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。 我第一次接触这种数据结构的时候，就对它存在的意义产生了很大的疑惑。因为我觉得，相 比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？

为什么还要用这个“操作受限”的“栈”呢？ 事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

如何实现一个“栈”？
从刚才栈的定义里，我们可以看出，栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。
理解了栈的定义之后，我们来看一看如何用代码实现一个栈。实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈， 用链表实现的栈，我们叫作链式栈。

**顺序栈**
```
public class ArrayStack {
	/** 数组 */
	private String[] items = null;
	/** 栈元素量 */
	private int count = 0;
	/** 栈大小 */
	private int n = 0;

/*** 初始化栈 * @param n */
	public ArrayStack(int n) {
		this.items = new String[n];
		this.n = n;
		this.count = 0;
	}
	/**
	 * 入栈
	 * 
	 * @param item
	 * @return
	 */
	public boolean push(String item) {
		if (count == n) {
			// 容器没有容量 返回 false
			return false;
		}
		// 入栈
		items[count] = item;
		// 修改指针
		++count;
		return true;
	}

/**
	 * 出栈
	 * @return
	 */
	public String pop() {
		// 没有数据
		if (count == 0) {
			return null;
		}
		String temp = items[count - 1];
		--count;
		return temp;
	}
}
```

**链式栈**
```

package com.qf.day24;

public class LinkStack {
	// 节点类型
	static class LinkNode {
		/** 数据存储 */
		private Object data;
		/** 下一个节点 */
		private LinkNode next;

/*** 构造函数赋值 * @param data */
		public LinkNode(Object data) {
			this.data = data;
		}

/*** 获取数据 * @return */
		public Object getData() {
			return this.data;
		}

/*** 设置数据 * @param data */
		public void setData(Object data) {
			this.data = data;
		}

/*** 获取下个节点 * @return */
		public LinkNode getNext() {
			return this.next;
		}

/*** 设置下一个节点 * @param linkNode */
		public void setNext(LinkNode linkNode) {
			this.next = linkNode;
		}
	}

private LinkNode root = null;

public LinkStack() {
		root = new LinkNode(null);
	}

/**
	 * 入栈
	 * @param data
	 */
	public void push(Object data) {
		// 先判断根节点是否有数据、如果存在直接设置值
		if (root.getData() == null) {
			root.setData(data);
		} else if (root == null) {
			root = new LinkNode(data);
		} else {
			// 创建新节点
			LinkNode nextNode = new LinkNode(data);
			// 将新节点追加到头部
			nextNode.setNext(root);
			// 将当前节点设置成根节点
			root = nextNode;
		}
	}

/**
	 * 出栈
	 * @return
	 */
	public Object pop() {
		Object data = null;
		if (root == null) {
			// 没有数据
			return "没有数据可出栈！";
		}
		// 获取第一个数据
		data = root.getData();
		// 将第一个移除
		root = root.getNext();
		return null;
	}

}
```

Java技术交流/Java技术提升库

内容风险标识

评论 (0)

Java技术交流/Java技术提升库 .gitee-modal { width: 500px !important; }

内容风险标识