这篇文章主要讲解了“如何正确实现数据结构栈”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何正确实现数据结构栈”吧！
栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。
栈常用一维数组或链表来实现，用数组实现的栈叫作 顺序栈 ，用链表实现的栈叫作 链式栈 。
举个例子：就像叠盘子 一样，后放的盘子总是在上面，拿盘子时是从上面拿，也就是先拿后来放上面的盘子，最后的盘子是最早放的。
对于数组来说，我们模拟栈的过程很简单，因为栈是后进先出，我们很容易在数组的末尾进行插入和删除。所以我们选定末尾为栈顶。
计算
安全
数据库
网络和加速
企业服务
/**
* 栈 数组实现
*
* @author ervin
* @Date 2021/4/20
*/
public class ArrayStack<T> {
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<T> {
private static class Node<T>{
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） 特性。
感谢各位的阅读，以上就是“如何正确实现数据结构栈”的内容了，经过本文的学习后，相信大家对如何正确实现数据结构栈这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4074923/blog/5026632
