04-图解数据结构之栈--Stack
04-图解数据结构之栈--Stack
张风捷特烈
发布于 2018-09-29 11:31:37
发布于 2018-09-29 11:31:37
零、前言
栈是一种线性的数据结构 特性：仅栈顶元素可见、后进先出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次
--- |---|---|---|---|---|---|---
push | O(1)|0.0011秒|0.0034秒|0.0158秒|0.0726秒|1.020秒
pop| O(1)|0.0006秒|0.0025秒|0.0085秒|0.0280秒|0.1751秒
peek | O(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你的喜欢与支持将是我最大的动力
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.09.22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录