前言

数据结构，一门数据处理的艺术，精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美，在为信息技术打下坚实地基的同时，也令无数开发者和探索者为之着迷。

也因如此，它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持，我打算将这门课的笔记也写作系列博文，既用于整理、消化，也用于同各位交流、展示数据结构的美。

此系列文章，将会分成两条主线，一条“数据结构基础”，一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主，“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

欢迎关注博主，一起交流、学习、进步，往期的文章将会放在文末。

前面总结了线性表的基本使用。这一节我们来总结一下两种常用的也是非常重要且特殊的线性结构——栈和队列。

说它重要，是因为这种结构在日常生产中的大大小小事务中无时无刻不在用到。

例如程序调用函数时产生的存储就是栈结构，所以我们常说“栈空间”，先调用的函数最后结束，后来函数内的局部变量的空间都会在该函数结束时得到释放，且不会影响到前面的函数。而计算机底层指令执行就是一种队列结构，后来的指令最后执行。

不仅如此，在各种算法中，两个数据结构也是频频入镜。以最基本的两种搜索算法为例，深度优先和广度优先就是基于这两种结构对状态进行的枚举。

另外，面对事务并发的场景，一种不错的解决方案是使用队列管理事务，将其队列化后依次处理。常见的输入输出流也是字节数据的队列。面向对象中一个类实例化和释放时他本身及其继承的父类关系就是栈的关系。

所以，这两种基础数据结构的重要性是不言而喻的。俗话说“基础不牢，地动山摇”，要建立坚实可靠算法基础和业务逻辑能力，本节基础内容和下一节的应用扩展内容将会是一个绕不开的重点，那么就让我们开始吧：

本节思维导图：

堆栈

堆栈简称栈，是一种首先得线性表，只允许表的同一段进行插入和删除操作，且这些操作是按后劲消除的原则进行的。

进行插入和删除的一段被称为栈顶，另一端被称为栈底。栈中没有元素的时候被称为空栈

顺序栈

顺序栈的存储方式是顺序的，使用数组实现。

其特点就是栈的最大规模是确定的，因为数组的大小无法动态改变。

顺序栈的封装

下面我们来封装一个顺序栈。最基本操作如下：

• 压入一个元素（push）
• 弹出一个元素（pop）
• 获得栈顶元素（peek）
• 清空栈（clear）
• 判断是否为空（isEmpty）
• 判断是否存满（isFull）
• 获得元素个数（size）

在顺序栈中，我们只需要知道一个数组的地址、当前元素个数以及数组规模便可以完成栈的基本操作。

所以栈的类的原型以及构造函数可如下（以int元素为例）：

//C
typedef struct _Stack{ 
	int * elements;
	int maxLen;
	int size;
}Stack;

Stack * createStack(int maxLen){ 
	Stack * stack = (Stack *)malloc(sizeof(Stack));
	
	stack->maxLen = max(1,maxLen);
	stack->size = 0;
	stack->stack = (int *)malloc(sizeof(int) * min(1,maxLen));
	
	return stack;
}

//java
public class Stack { 
	private int[] elements;

	private int maxLen;
	
	private int size;
	
	public Stack(int maxLen) { 
		this.maxLen = Math.max(1,maxLen);
		
		elements= new int[maxLen];
		
		size = 0;
	}
}

判断是否空/满

有了这样的原型，判断一个栈是否空或者满就很简单了。

空就是当前规模为0，满就是当前规模和最大规模相同。

//C
int isEmpty(Stack * stack){ 
	return stack->size == 0;
}

int isFull(Stack * stack){ 
	return stack->size == stack->maxLen;
}

public boolean isEmpty() { 
	return size == 0;
}
public boolean isFull() { 
	return size == maxLen;
}

获得当前栈中元素数量

在确定了栈的原型之后，这个问题就变成了一个送分题，因为栈中元素数量就在里面存着。

//C
int size(Stack * stack){ 
	return stack->size;
} 

public int size() { 
return size;
}

压入一个元素

在栈还有剩余空间的条件下，插入一个元素只需要将该元素放置在数组末尾 ，同时更新栈顶位置即可。

所以在执行插入操作之前，我们需要先对栈是否已满进行判断

//C
int push(int value,Stack * stack){ 
	if(isFull(stack)){ 
		return 0;	// 插入元素失败，栈满 
	}
	Stack->elements[stack->size] = value;
	stack->size++;
	return 1;
}

//java
public boolean push(int value) throws Exception { 
	if(isFull()) { 
		throw new Exception("栈满不能添加元素");
	}
	elements[size] = value;
	size++;
	return true;
}

获得栈顶元素

获得栈顶元素，栈顶元素就是当前数组中的最后元素，直接按照下标返回即可。

但在这之前需要判定一下栈是否为空。

//C
int peek(Stack * stack){ 
	if(isEmpty(stack)){ 
		return 0;
	}
	return stack->elements[stack->size - 1];
} 

public int peek() throws Exception { 
	if(isEmpty()) { 
		throw new Exception("空栈异常");
	}
	return elements[size - 1];
}

弹出栈顶元素

当栈顶元素存在时，顺序栈只需要将栈顶指针向前移动一位即可表示删除。对于空栈，可以选择抛出异常，也可以不做任何处理。

//C
int pop(Stack * stack){ 
	stack->size = max(0,stack->size - 1);
	return stack->size;
} 

public int pop() { 
	size = Math.max(0, size - 1);
	return size;
}

清空栈

清空栈相当于删除所有的元素，只需要将栈顶指针置零即可。

//C
int clear(Stack * stack){ 
	int size = stack->size;
	stack->size = 0;
	return size;
} 

//java
public int clear() { 
	int size = this.size;
	this.size = 0;
	return size;
}

完整代码

//C
#include<malloc>

typedef struct _Stack{ 
	int * elements;
	int maxLen;
	int size;
}Stack;

Stack * createStack(int);
int isEmpty();
int isFull();
int push(Stack*,int);
int pop(Stack*);
int peek(Stack*);
int size(Stack*);
int clear(Stack*);


Stack * createStack(int maxLen){ 
	Stack * stack = (Stack *)malloc(sizeof(Stack));
	
	stack->maxLen = max(1,maxLen);
	stack->size = 0;
	stack->stack = (int *)malloc(sizeof(int) * min(1,maxLen));
	
	return stack;
}

int isEmpty(Stack * stack){ 
	return stack->size == 0;
}

int isFull(Stack * stack){ 
	return stack->size == stack->maxLen;
}

int push(int value,Stack * stack){ 
	if(isFull(stack)){ 
		return 0;	// 插入元素失败，栈满 
	}
	Stack->elements[stack->size++] = value;
	return 1;
}

int peek(Stack * stack){ 
	if(isEmpty(stack)){ 
		return 0;
	}
	return stack->elements[stack->size - 1];
} 

int pop(Stack * stack){ 
	stack->size = max(0,stack->size - 1);
	return stack->size;
} 

int size(Stack * stack){ 
	return stack->size;
} 

int clear(Stack * stack){ 
	int size = stack->size;
	stack->size = 0;
	return size;
} 

//java
public class Stack { 
	private int[] elements;

	private int maxLen;
	
	private int size;
	
	public Stack(int maxLen) { 
		this.maxLen = Math.max(1,maxLen);
		
		elements = new int[maxLen];
		
		size = 0;
	}
	public boolean isEmpty() { 
		return size == 0;
	}
	public boolean isFull() { 
		return size == maxLen;
	}
	
	public boolean push(int value) throws Exception { 
		if(isFull()) { 
			throw new Exception("栈满不能添加元素");
		}
		elements[size] = value;
		size++;
		return true;
	}
	
	public int pop() { 
		size = Math.max(0, size - 1);
		return size;
	}
	
	public int peek() throws Exception { 
		if(isEmpty()) { 
			throw new Exception("空栈无栈顶");
		}
		return elements[size - 1];
	}
	public int size() { 
		return size;
	}
	
	public int clear() { 
		int size = this.size;
		this.size = 0;
		return size;
	}
}

链式栈

链式栈是指使用链式存储结构实现的栈。载体就是链表。

链式栈由于其使用链表实现，所以其相对于顺序栈来说没有了最大元素个数的上限。因此链式栈没有了判断栈满的方法，因为链式栈理论上是无限的。

相较于顺序栈来说，链式栈的一些操作会有些不同，最突出的是压栈和弹栈。原因在于顺序栈的栈顶指针并不是实际的元素指针，而是模拟的栈顶元素下标。再删除元素的时候是直接将栈顶指针减一，栈顶元素自然就被排除在了栈之外，而并没有被真正删除。但是在链式栈这里，删除操作除了要将栈顶元素提出栈之外，还要切实的释放掉它。

另外，链式栈的封装和顺序栈也不一样，不再需要保留全部的数组而是仅保留一个头指针即可，这样大大减少了封装对象的大小。

最后一个问题，就是有关链式栈的栈顶在哪边的问题，是放在链首好还是放在链尾好。其实这个问题非常好回答以至于基本上就是显而易见的。由于栈结构的特殊性，我们需要频繁的访问栈顶或插入删除栈顶，而链表中唯一可以直接访问到的元素就是链首，要是访问链尾则需要每次遍历整个栈，这个复杂度是我们不可接受的。

需要注意的是，链式栈中没有哨位结点，而且基本操作也比单链表简单
（当然者不代表使用哨位结点不行，只是实现起来会麻烦一些）

链式栈的封装

在封装具体的方法之前，先来封装下链式栈对象和结构体。

//C
typedef struct _Node{ 
	int value;
	struct Node * next;
}Node;
typedef struct _LinkedStack{ 
	Node * head;
	int size;
}LinkedStack;

LinkedStack * createLinkedStack(){ 
	LinkedStack stack = (LinkedStack*)malloc(sizeof(LinkedStack));
	stack->head = NULL;
	stack->size = 0;
}

//java
public class LinkedStack { 
	private class Node{ 
		int value;
		Node next;
	}
	
	private Node head;
	
	private int size;
	
	public LinkedStack() { 
		size = 0;
		head = null;
	}
}

有了链表结构体和类声明，下面就可以封装对应的方法了。
当然，我们没必要封装所有的方法，只需要封装几个有明显不同实现的方法即可。

压栈

插入一个元素，需要新建一个结点并将它加入队首。

//C
int push(LinkedStack * stack,int value){ 
	Node * node = (Node*)malloc(sizeof(Node));//新建一个结点
	
	node->value = value;
	node->next = stack->head;
	
	stack->head = node;
	stack->size++;
	return 1;
}

//java
public boolean push(int val) { 
	Node node = new Node();
	node.value = val;
	node.next = head;
	head = node;
	return true;
}

弹栈

弹出栈顶元素需要将栈顶元素踢出链表并释放空间

//C
int pop(LinkedStack * stack){ 
	if(isEmpty()){ 
		return false;
	}
	Node * node = stack->head;//缓存一下不然会出事
	stack->head = node->next;//踢出链表
	free(node);//释放空间
	return 1;
}

public boolean pop() { 
	if(isEmpty()) { 
		return false;
	}
	
	head = head.next;
	return true;
}

获取栈顶元素

//C
int peek(LinkedStack * stack){ 
	if(isEmpty(stack)){ 
		return 0;
	}
	return stack->head->value;
}

public int peek() throws Exception { 
	if(isEmpty()) { 
		throw new Exception("空栈异常");
	}
	return head.value;
}

清空栈

清空栈的难点主要体现在将栈中的结点逐个释放掉

//C
int clear(LinkedStack * stack){ 
	Node * node;
	while(stack->head){ 
		node = stack->head;
		stack->head = node->next;
		free(node);
	}
	size = 0;
	return 1;
}

//java
public boolean clear() { 
	size = 0;
	head = null;
	//由于java存在垃圾回收机制，所以不用手动的释放结点内存
	return true;
}

队列

顾名思义，队列在使用起来时就像现实生活中排队的队列一般。

队列也是一种受限的线性结构，插入操作只能将元素放在一端而查询和删除操作只能对另一端使用。

这样的限制导致了队列元素特殊的先进先出特性。

这么看，是不是挺像排队的俯视图的。

既然是特殊的线性结构，那就会有顺序的和链接的两种存储模式，他们分别对应着顺序队列，和链式队列，下面我们就来介绍并封装他们。

顺序队列

顺序队列是指队列元素在存储空间上是顺序的，它采用顺序表也就是数组存储。

在数组中表示队列，需要队首和队尾两个指针。

当需要插入一个元素时，仅需要将新的元素放置在队尾，并将队尾指针向后移动一格。
当需要弹出元素时，仅需要将队首指针向后移动一格即可。

因为队首和队尾每次都是只增不减，所以整个队列看起来就像是在朝着队尾方向前进。

那么空队列也就是队列中没有元素时，其标志就是队首位于队尾的右面一格。

这样一来，当加入一格新元素的时候，队尾就会和队首重合，这个唯一的元素就既是队首也是队尾。

当删除最后一个元素时，队首会向前移动，位于队尾的后方，回到空队列的情况。

但是这样有一个明显的弊端，那就是队列的插入次数是有限的。因为数组的大小总是有上限的，每次插入都会使队列向前移动一步，而每次弹出的空间却不能在被队列使用。这样就造成了极大地不便，也是我们不能接受的。我们所希望的，是队列的上限取决于队列的长度，而非历史插入次数。

循环队列

于是我们便引出循环队列来解决这个问题，循环队列的思路就是将数组首位相接，允许队首和队尾指针越过数组的边界再回到开始位置，这个操作可以使用取模运算来完成。

只是这样的设计存在一个问题，那就是不能再像之前那样根据队首和队尾的位置来判断队列是否为空了。队尾指针出现在队首指针后面时，还有可能是整个数组都是队列，且当队列翻越数组终点时，队尾指针也会在队首指针后面。


所以必须使用指针之外的办法来管理数组。

一个很直接的方法就是引入队列中元素个数和数组长度两个属性。这样一来只需要在每次插入和删除的时候维护一下元素个数即可，就可以根据元素个数及数组长度来判断队列是否空或者满。

顺序队列的封装

封装一个顺序队列，至少要完成一下的基础操作：

• 入队：向队尾添加元素
• 出队：删除队首元素
• 获取队首元素
• 判断队列是否为满
• 判断队列是否为空

顺序队列的类

在封装基础操作之前，不妨先来给顺序队列的结构体和类封装一下，这是所有操作的基础。

经过上面的分析，实现顺序队列，就是用循环队列实现，所以类成员至少需要包括以下三个信息：

• 队列数组elements
• 数组规模maxLen
• 队列规模size
• 队首位置head
• 队尾位置tail

//C
typedef struct _ArrayQueue{ 
	int * elements;
	int maxLen;
	int size;
	int head;
	int tail;
}ArrayQueue;

ArrayQueue * createArrayQueue(int maxLen){ 
	ArrayQueue * queue = (ArrayQueue*)malloc(sizeof(ArrayQueue));
	maxLen = min(1,maxLen);
	queue->elements = (int*)malloc(sizeof(int) * maxLen);
	queue->maxLen = maxLen;
	queue->size = 0;
	queue->head = 0;
	queue->tail = maxLen - 1;
}

public class ArrayQueue { 
	private int[] elements;
	private int maxLen;
	private int size;
	
	public ArrayQueue(int maxLen) { 
		maxLen = Math.min(1, maxLen);
		elements = new int[maxLen];
		this.maxLen = maxLen;
		size = 0;
		head = 0;
		tail = maxLen - 1;
	}
}

获取队列规模

获取队列规模只需要返回其中存储的size即可。

int size(ArrayQueue * queue){ 
	if(queue == NULL)
		return 0;
	return queue->size;
}

//java
public int size() { 
return size;
}

判断队列是否为空

当队列当前元素数量为0时队列为空

//C
int isEmpty(ArrayQueue * queue){ 
	if(queue == NULL)
		return 0;
	return queue->size == 0;
}

//java
public boolean isEmpty() { 
	return size == 0;
}

判断队列是否为满

当队列中元素个数与最大元素个数相等时，队列为满

//C
int isFull(ArrayQueue * queue){ 
	if(queue == NULL)
		return 0;
	return queue->size == queue->maxLen;
}

//java
public boolean isFull() { 
	return size == maxLen;
}

入队

入队需要首先判断队列是否为满，如果没有满则可以入队，将新元素放到队尾，同时维护队尾指针和队列规模。

//C
int push(ArrayQueue * queue,int element){ 
	if(isFull(queue))
		return 0;
	queue->tail = (queue->tail + 1) % queue->maxLen;
	queue->elements[tail] = element;
	queue->size++;
	return 1;
}

//java
public boolean push(int element) { 
	if(isFull()){ 
		return false;
	}
	tail = (tail + 1) % maxLen;
	elements[tail] = element;
	size++;
	return true;
}

出队

出队之前需要先判断队列是否为空，若不为空则直接将头指针向后移动一位同时维护队列长度即可。

//C
int pop(ArrayQueue * queue){ 
	if(isEmpty(queue))
		return 0;
	queue->head = (queue->head + 1) % queue->maxLen;
	queue->size--;
	return 1;
}

//java
public boolean pop() { 
	if(isEmpty())
		return false;
	head = (head + 1) % maxLen;
	size--;
	return true;
}

队首元素

//C
int front(ArrayQueue * queue){ 
	if(isEmpty())
		return 0;
	return queue->elements[queue->head];
}

//java
public int front() throws Exception { 
	if(isEmpty()) { 
		throw new Exception("空队列异常");
	}
	return elements[head];
}

清空队列

清空队列相当于将队列恢复出厂设置，只需要将头尾指针归为并将元素个数置零即可。

//C
int clear(ArrayQueue * queue){ 
	queue->head = 0;
	queue->tail = -1;
	queue->size = 0;
	return 1;
}

//java
public boolean clear() { 
	size = 0;
	head = 0;
	tail = -1;
	return true;
}

完整代码

//C
typedef struct _ArrayQueue{ 
	int * elements;
	int maxLen;
	int size;
	int head;
	int tail;
}ArrayQueue;

ArrayQueue * createArrayQueue(int maxLen){ 
	ArrayQueue * queue = (ArrayQueue*)malloc(sizeof(ArrayQueue));
	maxLen = min(1,maxLen);
	queue->elements = (int*)malloc(sizeof(int) * maxLen);
	queue->maxLen = maxLen;
	queue->size = 0;
	queue->head = 0;
	queue->tail = maxLen - 1;
}

int size(ArrayQueue * queue){ 
	if(queue == NULL)
		return 0;
	return queue->size;
}

int isEmpty(ArrayQueue * queue){ 
	if(queue == NULL)
		return 0;
	return queue->size == 0;
}

int isFull(ArrayQueue * queue){ 
	if(queue == NULL)
		return 0;
	return queue->size == queue->maxLen;
}

int push(ArrayQueue * queue,int element){ 
	if(isFull(queue))
		return 0;
	queue->tail = (queue->tail + 1) % queue->maxLen;
	queue->elements[tail] = element;
	queue->size++;
	return 1;
}

int pop(ArrayQueue * queue){ 
	if(isEmpty(queue))
		return 0;
	queue->head = (queue->head + 1) % queue->maxLen;
	queue->size--;
	return 1;
}

int front(ArrayQueue * queue){ 
	if(isEmpty())
		return 0;
	return queue->elements[queue->head];
}

int clear(ArrayQueue * queue){ 
	queue->head = 0;
	queue->tail = -1;
	queue->size = 0;
	return 1;
}

//java
public class ArrayQueue { 
	private int[] elements;
	private int maxLen;
	private int size;
	private int head;
	private int tail;
	
	public ArrayQueue(int maxLen) { 
		maxLen = Math.min(1, maxLen);
		elements = new int[maxLen];
		this.maxLen = maxLen;
		size = 0;
	}
	public int size() { 
		return size;
	}
	
	public boolean isEmpty() { 
		return size == 0;
	}
	
	public boolean isFull() { 
		return size == maxLen;
	}
	
	public boolean push(int element) { 
		if(isFull()){ 
			return false;
		}
		tail = (tail + 1) % maxLen;
		elements[tail] = element;
		size++;
		return true;
	}
	
	public boolean pop() { 
		if(isEmpty())
			return false;
		head = (head + 1) % maxLen;
		size--;
		return true;
	}
	
	public int front() throws Exception { 
		if(isEmpty()) { 
			throw new Exception("空队列异常");
		}
		return elements[head];
	}
	
	public boolean clear() { 
		size = 0;
		head = 0;
		tail = -1;
		return true;
	}
}

注：这里仅考虑完成基本的功能，对于更复杂的需求例如线程安全等并没有考虑。

链式队列

链式队列和链式栈很类似，都是使用链表对队列进行改造。

且仔细观察不难发现，单链表的结构更适合实现队列。

在链首，元素删除更加容易。在链尾，元素无法直接得到其前驱，插入更加容易。

所以我们将链首当做队首，将链尾当做队尾。

与链式栈类似，链式队列中也不需要哨位结点，且没有最大长度限制

当队列为空时首尾指针都为空。

链式队列的封装

首先还是先来封装链式队列的结构体和类，链式队列仅需要记录头结点和尾结点的指针以及队列规模，没有队列的最大长度限制。

//C
typedef struct _Node{ 
	int value;
	struct Node * next;
}Node;

typedef struct _LinkedQueue{ 
	Node * head;
	Node * tail;
	int size;
}LinkedQueue;

LinkedQueue * createLinkedQueue(){ 
	LinkedQueue * queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	queue->size = 0;
	queue->head = NULL;
	queue->tail = NULL;
	return queue;
}

//java
public class LinkedQueue { 
	private class Node{ 
		int value;
		Node next;
	}
	
	private Node head;
	private Node tail;
	private int size;
	
	public LinkedQueue() { 
		size = 0;
		head = null;
		tail = null;
	}
}

同链式栈一样，这里仅封装不太一样的方法：

入队

入队时需要在队尾添加元素，同时更新队列大小。需要注意的是要单独处理队中没有元素的情况。

//C
int push(LinkedQueue * queue,int value){ 
	Node * node = (Node*)malloc(sizeof(Node));
	node->value = value;
	node->next = NULL;
	if(isEmpty(queue)){ //当队中元素唯一时，该元素既是队首又是队尾
		queue->head = node;
		queue->tail = node;
	}else{ 
		queue->tail->next = node;
		queue->tail = node;
	}
	queue->size++;
	return 1;
}

//java
public boolean push(int value) { 
	Node node = new Node();
	node.value = value;
	node.next = null;
	if(isEmpty()) { 
		head = node;
		tail = node;
	}else { 
		tail.next = node;
		tail = node;
	}
	size++;
	return true;
}

出队

出队的时候需要注意一下，当队中最后一个元素要被踢出时，需要更新尾指针为空。

//C
int pop(LinkedQueue * queue){ 
	if(isEmpty(queue)){ 
		return 0;	
	}
	Node * node = queue->head;
	queue->head = node->next;
	if(queue->size = 1){ 
		queue->tail = NULL;
	}
	free(node);
	queue->size--;
	return 1;
}

//java
public boolean pop() { 
	if(isEmpty()) { 
		return false;
	}
	
	head = head.next;
	if(size == 1) { 
		tail = null;
	}
	
	size--;
	return true;
}

清空队列

同链式栈相似，清空队列也需要将队列中的元素结点释放，同时维护队列规模，并将头尾指针还原为空。

//C
int clear(LinkedQueue * queue){ 
	queue->size = 0;
	Node * node;
	while(queue->head){ 
		node = queue->head;
		queue->head = node;
		free(node);
	}
	queue->tail = NULL;
	return 1;
}

//java
public boolean clear() { 
	head = null;
	tail = null;
	size = 0;
	return true;
}

往期博客

• 【数据结构基础】数据结构基础概念
• 【数据结构基础】线性数据结构——线性表概念 及 数组的封装
• 【数据结构基础】线性数据结构——三种链表的总结及封装

参考资料：

• 《数据结构》（刘大有，杨博等编著）
• 《算法导论》（托马斯·科尔曼等编著）
• 《图解数据结构——使用Java》（胡昭民著）