1、栈（Stack）

栈是一种特殊的线性表，只能在一端进行操作。

栈

**注：**这里说的“栈”与内存中的“栈空间”是两个不同的概念。这里说的栈是一种数据结构，而“栈空间”是内存的一种，两者虽然有一定的联系，但却是两个完全不同的概念。

  • 栈的常见操作主要包括：

    • 入栈（Push）：往栈中添加元素。

    • 出栈（Pop）：从栈中移出元素。

      **注：**只有栈顶元素可被移出。

  • 元素出入原则：后进先出。

2、栈的设计

仔细观察可以发现，如果我们把栈内元素按照入栈的先后顺序依次存储在前面学习过的动态数组或链表中，那么元素的入栈和出栈操作完全等价于在动态数组或链表的尾部添加和删除元素。因此，我们可以直接利用动态数组或（双向）链表来实现栈。

**注：**如果频繁在尾部进行添加、删除操作，选择动态数组和（双向）链表均可。此时，两者时间复杂度均为O(1)。

（1）类的结构设计

在编程之前，我们需要先对栈类（Stack）的结构进行设计。因为我们是直接利用动态数组或（双向）链表来实现栈，所以我们可以通过“组合”的方式来实现栈。即：将动态数组类或（双向）链表类的对象定义成Stack类的私有成员变量。

**注：**我们之所以没采用“继承”（即：让Stack类直接继承动态数组类或双向链表类）的方式来实现栈，是因为如果Stack类直接继承动态数组类或双向链表类，那么它在继承动态数组或（双向）链表特性的同时也会继承它们的其他接口，从而破坏了Stack类封装的接口。

因此，栈类需要的成员主要包括：

  • 私有成员变量：动态数组类或（双向）链表类的对象。

    1
    private ArrayList<E> list = new ArrayList<E>();

    或

    1
    private DoubleLinkedList<E> list = new DoubleLinkedList<E>();

  • 接口函数。

（2）接口设计

  • int size(); //元素的数量
  • boolean isEmpty(); //是否为空
  • void push(E element); //入栈
  • E pop(); //出栈
  • E top(); //获取栈顶元素
  • void clear(); //清空栈内元素

3、栈的实现

3.1、编程实现

新建一个项目，在其中：

①先新建一个名称为Stack（包名为：com.atangbiji）的类，用来自己实现栈；

②再新建一个名称为Main（包名为：com.atangbiji）的类，用来调用（测试）自己封装的栈。

③将前面章节中封装好的动态数组类或（双向）链表类拷贝到该项目的com.atangbiji包中，供Stack类调用，如下图所示。

工程

**注：**其实Java中已经为我们封装好了Stack类。当我们调用Stack时会提示有两个Stack类。为了测试自己写的数据结构，此时我们应该选择包名为com.atangbiji的那个。

④接口实现，我们这里直接考虑栈内元素均为泛型的情况。

（1）定义私有成员变量

Stack.java文件：

1
2
3
4
5
6
7
8
9
package com.atangbiji;

public class Stack<E> {
	
	//使用动态数组或双向链表来实现栈
	private ArrayList<E> list = new ArrayList<E>();	
    // 或 private DoubleLinkedList<E> list = new DoubleLinkedList<E>();

}

（2）实现size()接口

Stack.java文件：

1
2
3
4
5
6
7
8
9
/*
 * 元素的数量
 * @param
 * @return 
 * */
public int size() {
	// 栈中元素数量, 就是列表中存储的元素数量
	return list.size();
}

（3）实现isEmpty()接口

Stack.java文件：

1
2
3
4
5
6
7
8
9
/*
 * 是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	// 栈是否空, 就是列表是否空
	return list.isEmpty();
}

（4）实现push(E element)接口

Stack.java文件：

1
2
3
4
5
6
7
8
9
/*
 * 入栈
 * @param
 * @return 
 * */
public void push(E element) {
	// 入栈, 即：将元素添加到列表的最后面
	list.add(element);
}

（5）实现pop()接口

Stack.java文件：

1
2
3
4
5
6
7
8
9
/*
 * 出栈
 * @param
 * @return 
 * */
public E pop() {
	// 出栈, 即：将列表中最后一个元素删除并返回
	return list.remove(list.size() - 1);
}

（6）实现top()接口

Stack.java文件：

1
2
3
4
5
6
7
8
9
/*
 * 获取栈顶元素
 * @param
 * @return 
 * */
public E top() {
	// 获取栈顶元素, 就是获取列表中的最后一个元素
	return list.get(list.size() - 1);
}

（7）实现clear ()接口

Stack.java文件：

1
2
3
4
5
6
7
8
9
/*
 * 清空栈内元素
 * @param
 * @return 
 * */
public void clear() {
	// 清空栈, 就是清空列表
	list.clear();
}

3.2、接口测试

在Main类（Main.java文件）中新建一个Stack对象，用来测试自己封装的栈。这里仅以入栈和出栈接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		Stack<Integer> stack  = new Stack<Integer>();
		stack.push(11);
		stack.push(22);
		stack.push(33);
		stack.push(44);
		stack.push(55);
		
		//若栈不为空，则弹出栈顶元素。直到栈为空为止。
		while (!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}
}

运行该程序，输出结果为：

测试结果

4、java.util.Stack类源码分析

Java自带的java.util.Stack类就是一个栈，它是通过Vector（向量）来实现的。自行分析，这里不再赘述。

注：Vector（向量）类似于我们之前实现的ArrayList（动态数组）。两者最主要的区别是：Vector是线程安全的，ArrayList是非线程安全的。（了解即可）

5、栈的应用

  • 浏览器的前进和后退功能

    **注：**内部用到了两个栈。

  • 软件的撤销和恢复功能

  • 括号匹配

（本讲完，系列博文持续更新中…… ）

参考文献：
[1] 《恋上数据结构与算法》，小码哥MJ
[2] 《数据结构与算法》，邓俊辉

附：如何获取源代码？

关注 “阿汤笔迹” 微信公众号，在后台回复关键词 “数据结构与算法设计与实现” ，即可获取项目源代码。

阿汤笔迹微信公众平台

原文地址：http://www.atangbiji.com/2023/07/23/Stack/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。