1、基本常识
1.1 什么是栈
比如弹夹式手枪，向弹夹装子弹，最先装入的，会压到最底端。当子弹被射出时，最后放入的子弹会最先被射出。这种先进后出，后进先出的结构称为“栈”。
1.2 栈的特点
“先进后出，后进先出”。
1.3 栈的操作
栈的操作就两种，分别为出栈和入栈。那我们上边的例子，我们弹夹装子弹的过程称为入栈；我们发射子弹的过程称为出栈。
2、栈的实现
栈也是线性表的特例，所以也都能由数组和链表来实现
栈的实现主要有两种，一种是数组的实现，叫做顺序栈，另外一种是链表的实现，叫做链式栈。如下：
2.1 顺序栈
2.2 链表栈
3.2 代码实现
顺序栈（Java）
1/**
2 * 功能:基于数组的顺序栈
4 *
5 */
6public class ArrayStack {
7
8 private String[] items; // 数组
9 private int count; // 栈中元素个数
10 private int n; // 栈的大小
11
12 // 初始化数组，申请一个大小为 n 的数组空间
13 public ArrayStack(int n) {
14 this.items = new String[n];
15 this.n = n;
16 this.count = 0;
17 }
18
19 /**
20 * 功能:入栈
21 * 说明:数组入栈的入口为数组尾部
22 * @param item :入栈数据元素
23 * @return:是否入栈成功
24 */
25 public boolean push(String item) {
26 // 数组空间不够了，直接返回 false，入栈失败。
27 if (count == n) return false;
28 // 将 item 放到下标为 count 的位置
29 items[count] = item;
30 //数组长度+1
31 ++count;
32 //入栈成功
33 return true;
34 }
35
36 /**
37 * 功能:出栈
38 * @return:返回出栈元素
39 */
40 public String pop() {
41 // 栈为空，则直接返回 null
42 if (count == 0) return null;
43 // 返回下标为 count-1 的数组元素
44 String tmp = items[count-1];
45 //数组长度-1
46 --count;
47 //返回出栈数据元素
48 return tmp;
49 }
50}链式栈（Java）
1/**
2 * 功能:基本链表实现栈，入栈、出栈、输出栈
4 *
5 */
6public class StackBasedLinkedList {
7 //定义栈顶指针
8 private Node top = null;
9
10 //定义栈结点
11 private static class Node {
12 //栈结点数据域
13 private int data;
14 //栈结点指针域
15 private Node next;
16 //构造函数
17 public Node(int data, Node next) {
18 this.data = data;
19 this.next = next;
20 }
21 //get 获取数据域方法
22 public int getData() {
23 return data;
24 }
25 }
26
27 /**
28 * 功能:入栈
29 * @param value:要入栈的数据元素
30 */
31 public void push(int value) {
32 //创建一个栈结点
33 Node newNode = new Node(value, null);
34 // 判断栈是否为空
35 if (top == null) {
36 //如果栈为空，就将入栈的值作为栈的第一个元素
37 top = newNode;
38 } else {
39 //否则插入到top栈结点前（所谓的就是单链表的头插法）
40 newNode.next = top;
41 top = newNode;
42 }
43 }
44
45 /**
46 * 功能 : 出栈
47 * @return: -1 为栈中没有数据
48 */
49 public int pop() {
50 // 如果栈的最顶层栈结点为null,栈为空
51 if (top == null) return -1;
52
53 //否则执行出栈操作，现将栈顶结点的数据元素赋值给 Value
54 int value = top.data;
55 //将 top 指针向下移动
56 top = top.next;
57 //返回出栈的值
58 return value;
59 }
60
61 /**
62 * 功能:输出栈中所有元素
63 */
64 public void printAll() {
65 //将栈顶指针赋值给p
66 Node p = top;
67 //循环遍历栈(遍历单链表)
68 while (p != null) {
69 System.out.print(p.data + " ");
70 //指向下一个结点
71 p = p.next;
72 }
73 System.out.println();
74 }
75}栈的性能
3.1 时间复杂度
O(1)
3.2 空间复杂度
?O(1)