零、前言
栈是一种线性的数据结构 特性：仅栈顶元素可见、后进先出LIFO 操作：push入栈 pop弹栈 peek查看栈顶元素
栈.png
栈的数组实现
一、栈的接口
/**
* 作者：张风捷特烈
* 时间：2018/8/17 0017:12:49
* 邮箱：1981462002@qq.com
* 说明：栈的接口
*/
public interface IStack<T> {
/**
* 栈元素个数
* @return 栈元素个数
*/
int size();
/**
* 栈元素容积
* @return 容积
*/
int capacity();
/**
* 是否为空
* @return 是否为空
*/
boolean isEmpty();
/**
* 入栈
* @param el 元素
*/
void push(T el);
/**
* 出栈
* @return 元素
*/
T pop();
/**
* 取出元素
* @return 元素
*/
T peek();
}
二、栈的数组实现：数组总结见第01篇
/**
* 作者：张风捷特烈
* 时间：2018/8/17 0017:12:56
* 邮箱：1981462002@qq.com
* 说明：栈的数组实现
*/
public class ArrayGroupStack<T> implements IStack<T> {
/**
* 成员变量
*/
private ArrayGroup<T> array;
public ArrayGroupStack(int capacity) {
array = new ArrayGroup<>(capacity);
}
public ArrayGroupStack() {
array = new ArrayGroup<>();
}
@Override
public int size() {
return array.size();
}
@Override
public int capacity() {
return array.getCapacity();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public T pop() {
return array.removeLast();
}
@Override
public void push(T el) {
array.addLast(el);
}
@Override
public T peek() {
return array.get(size() - 1);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack ：");
res.append("[ ");
for (int i = 0; i < array.size(); i++) {
res.append(array.get(i));
if (i != array.size() - 1) {
res.append(", ");
}
}
res.append("] <--top");
return res.toString();
}
}
数组栈测试
private static void arrayStackTest() {
ArrayGroupStack<Integer> arrayGroupStack = new ArrayGroupStack<>();
for (int i = 0; i < 5; i++) {
arrayGroupStack.push(i);
System.out.println(arrayGroupStack);
}
arrayGroupStack.pop();
arrayGroupStack.pop();
Integer peek = arrayGroupStack.peek();
System.out.println(peek);
}
//Stack ：[ 0] <--top
//Stack ：[ 0, 1] <--top
//Stack ：[ 0, 1, 2] <--top
//Stack ：[ 0, 1, 2, 3] <--top
//Stack ：[ 0, 1, 2, 3, 4] <--top
//2
三、链表实现栈 ：链表总结见第02篇
/**
* 作者：张风捷特烈
* 时间：2018/8/17 0017:22:40
* 邮箱：1981462002@qq.com
* 说明：栈的链表式集合实现
*/
public class SingleLinkedStack<E> implements IStack<E> {
private SingleLinkedGroup<E> mLinkedGroup;
public SingleLinkedStack() {
mLinkedGroup = new SingleLinkedGroup<>();
}
@Override
public int size() {
return mLinkedGroup.size();
}
@Override
public int capacity() {
return mLinkedGroup.size();
}
@Override
public boolean isEmpty() {
return mLinkedGroup.isEmpty();
}
@Override
public void push(E el) {
mLinkedGroup.addFirst(el);
}
@Override
public E pop() {
return mLinkedGroup.removeFirst();
}
@Override
public E peek() {
return mLinkedGroup.get(0);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("SingleLinkedStack Stack ：");
res.append(mLinkedGroup);
return res.toString();
}
}
测试：
/**
* 链表式集合实现的栈测试方法
*/
private static void linkStackTest() {
SingleLinkedStack<Integer> linkedStack = new SingleLinkedStack<>();
for (int i = 0; i < 5; i++) {
linkedStack.push(i);
System.out.println(linkedStack);
}
linkedStack.pop();
linkedStack.pop();
Integer peek = linkedStack.peek();
System.out.println(peek);
//SingleLinkedStack Stack ：head: 0->NULL
//SingleLinkedStack Stack ：head: 1->0->NULL
//SingleLinkedStack Stack ：head: 2->1->0->NULL
//SingleLinkedStack Stack ：head: 3->2->1->0->NULL
//SingleLinkedStack Stack ：head: 4->3->2->1->0->NULL
//2
}
四、链表和数组实现栈的比较
数组栈：ArrayGroupStack测试
方法\数量复杂度1000次10000次10W次100W次1000W次
pushO(1)0.0011秒0.0034秒0.0158秒0.0726秒1.020秒popO(1)0.0006秒0.0025秒0.0085秒0.0280秒0.1751秒peekO(1)----------
链表栈：SingleLinkedStack测试
方法\数量 |复杂度 |1000次|10000次|10W次|100W次|1000W次 --- |---|---|---|---|---|---|--- push | O(1)|0.0005秒|0.0027秒|0.0075秒|0.3817秒|3.1550秒 pop| O(1)|0.0004秒|0.0022秒|0.0050秒|0.0223秒|0.1267秒 peek | O(1)|--|--|--|--|--|
后记、
1.声明：
[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明 [2]欢迎广大编程爱好者共同交流 [3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 [4]你的喜欢与支持将是我最大的动力
2.连接传送门：
更多数据结构知识欢迎访问:图解数据结构 项目源码均在我的https://github.com/toly1994328/DS：欢迎star 张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com
3.联系我
QQ:1981462002 邮箱：1981462002@qq.com 微信：zdl1994328
4.欢迎关注我的微信公众号，最新精彩文章，及时送达：
公众号.jpg
转载于:https://www.cnblogs.com/toly-top/p/9781867.html
相关资源：JAVA上百实例源码以及开源项目
