这篇文章主要讲解了“如何正确实现数据结构栈”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何正确实现数据结构栈”吧！
公司主营业务：成都网站设计、网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出抚州免费做网站回馈大家。
栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。
栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈，用链表实现的栈叫作 链式栈。
举个例子：就像叠盘子 一样，后放的盘子总是在上面，拿盘子时是从上面拿，也就是先拿后来放上面的盘子，最后的盘子是最早放的。
对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。
/** * 栈 数组实现 * * @author ervin * @Date 2021/4/20 */ public class ArrayStack{ private Object[] data; //栈顶 private int top; public ArrayStack(int size) { this.data = new Object[size]; this.top = -1; } public boolean isEmpty() { return this.top == -1; } public boolean isFull() { return this.top == data.length - 1; } public void push(T t) throws Exception { if (isFull()) { //扩容 Object[] newDate = new Object[top * 2]; for (int i = 0; i <= top; i++) { newDate[i] = this.data[i]; } data = newDate; } data[++top] = t; } public T pop() throws Exception { if (isEmpty()) { throw new Exception("stack empty"); } return (T) data[top--]; } @Override public String toString() { StringBuilder builder = new StringBuilder(); for (int i = 0; i < data.length; i++) { builder.append("index:" + i + "value:" + data[i]).append("\n"); } return builder.toString(); } }
我们采用带头节点的单链表在头部插入删除，把头部当中栈顶。插入直接在头节点后插入。而删除也直接删除头节点后第一个元素即可。
/** * 栈 链表实现 * @author ervin * @Date 2021/4/20 */ public class ListStack{ private static class Node { T item; Node next; Node(T ele,Node next){ this.item = ele; this.next = next; } } private Node header; private int size; ListStack() { this.header = new Node(null,null); this.size = 0; } public int size() { return this.size; } public boolean isEmpty() { return this.size == 0; } public void push(T data){ Node n = null; if (header.next != null){ n = new Node(data,header.next); } else{ n = new Node(data,null); } this.header.next = n; size++; } public T pop() throws Exception { if (this.header.next == null){ throw new Exception("stack empty"); } Node n = this.header.next; if (n.next != null){ this.header.next = n.next; } else { this.header.next = null; } size--; return (T)n.item; } }
实现浏览器的回退和前进功能
我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候，你点击回退按钮，我们依次把 4,3 这两个页面从 Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面 3，你点击前进按钮，我们将 3 页面从 Stack2 弹出，然后压入到 Stack1 中。
检查符号是否成对出现
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串， 判断该字符串是否有效。 有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 则不是。
这个问题实际是 Leetcode 的一道题目，我们可以利用栈 Stack 来解决这个问题。
首先我们将括号间的对应规则存放在 Map 中，这一点应该毋容置疑；
创建一个栈。遍历字符串，如果字符是左括号就直接加入stack中，否则将stack 的栈顶元素与这个括号做比较，如果不相等就直接返回 false。遍历结束，如果stack为空，返回 true。
反转字符串
将字符串中的每个字符先入栈再出栈就可以了。
维护函数调用
最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。
感谢各位的阅读，以上就是“如何正确实现数据结构栈”的内容了，经过本文的学习后，相信大家对如何正确实现数据结构栈这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！
