从博客查看此篇文章
你好我是久远，我们先来复习一下上周我们讲的知识。

• 什么是链表？

在计算机科学中，链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。

• 链表的优点

由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

什么是栈

栈有时也被称作堆栈或者堆叠。栈是有序集合，它的添加，移除操作总是发生在同一端，设这一端为顶端，则未执行操作的一端为底端。
栈中的元素离底端越近，代表其在栈中的时间越长，最新添加的元素将被最先移除。这种排序原则被称作 LIFO（last-in first-out），即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端，旧元素则靠近底端。

生活中的例子：

在我们的生活中也很常见关于栈的例子，假设我们有一个放羽毛球的球桶，我们只能从桶的上面取出球，底部是不能取的，靠近开口的球，更先被取到。

既然有取出的先后，那么我们的栈也算是有顺序的，我们依旧使用列表来实现栈的一些操作。

举例来说，对于列表[1, 5, 3, 7, 8, 6]，只需要考虑将它的哪一边视为栈的顶端。一旦确定了顶端，所有的操作就可以利用 append 和pop 等列表方法来实现。

在这里我们视列表的尾部为栈顶，因此当进行 push 操作时，新的元素会被添加到列表的尾部。pop 操作同样会修改这一端。

栈的操作

我们前面已经介绍了栈的基本情况，既然我们要实现栈的操作，那我们肯定要新建一个栈，有了这个栈，我们肯定要做一些彰显出栈特性的事情————出栈，入栈。还有我们常见的操作，判断是否为空，判断栈的大小等等。

以下是我们要实现的方法：

• Stack()创建一个空栈。不传任何参数，返回空栈。
• push(item)将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值。
• pop()将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容。
• peek()返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容。
• isEmpty()检查栈是否为空。它不需要参数，且会返回一个布尔值。
• size()返回栈中元素的数目。它不需要参数，且会返回一个整数。

栈的定义

class Stack:
    def __init__(self):
        self.items = []

定义一个 stack 类来告诉计算机，我们现在定义了一个全新的类型叫做 stack ，每个类有一个定义方法即 init() ,我们使用 init 方法来定义栈的一些属性。我们新建一个栈，栈中最重要的就是元素，多个元素构成栈，而一开始当我们没有向栈中放入任何元素时，栈是空的，因此有 self.items = []，我们定义了一个空栈来作为栈的初始化。

栈是否为空

既然栈存在，我们就可以进行栈有无的判断，我们也像之前的数据结构类型一样，引入 isEmpty() 方法来判断栈中是否有元素，没有元素则为空栈，返回 true ；包含有元素，则说明栈不为空，返回 false。

def isEmpty(self):
        return self.items == []

栈的大小

栈的大小实际上就是判断栈中有多少元素，而我们使用列表来进行栈的实现，因此我们只需要使用 len() 方法计算引入的列表的长度即可判断栈中元素的多少了，即栈的大小。

def size(self):
        return len(self.items)

入栈操作

现在我们既可以判断栈中是否有元素，又可以判断栈的大小了，那么接下来就要实现栈最主要的两个操作了，入栈和出栈。

进行入栈操作我们就要想到，既然要把元素加入到栈中，那么我们就要传入一个参数去表示要加入到栈中的元素，然后将这个参数加入到栈中即可。

def push(self, item):
        self.items.append(item)

我们传入一个 item 参数，为我们要加入到栈中的元素，然后将其加入到我们引入的 items 列表中即可完成栈中元素的加入了。

出栈操作

既然有元素加入到栈中，那我们就可以将元素从栈中删除，因此我们有了出栈的操作，出栈操作一般的思维是这样的：我们让栈顶的元素弹出，同时也要告诉大家，我弹出的是哪个元素。

因此要返回弹出的那个元素。

代码实现为：

def pop(self):
        return self.items.pop()

使用列表中的 pop方法，返回列表末尾的那个元素，并将该元素从列表中删除，实现出栈。

查看栈顶

我们的栈操作中通常还包含一项查看栈顶元素的操作，因为我们在此将引入的列表末尾视为栈顶，因此我们只需要返回所引入的列表的最后一个元素即可。

def peek(self):
        return  self.items[len(self.items)-1]

整体的代码如下：

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return  self.items[len(self.items)-1]

总结

恭喜你又学完了一个知识点，栈是一个后进先出的数据类型，它有两个非常主要的操作，进栈和出栈：

• 进栈：将资料放入栈的顶端，栈的顶端移到新放入的资料。
• 出栈：将堆栈顶端资料移除，堆栈顶端移到移除后的下一笔资料。

它可以用数组或者链表来实现，而由于 python 的特殊性，我们常使用列表来实现栈的操作。

与栈相对的有队列，队列是一种先进先出的数据类型，我们下次会进行讲解。

流沙团队联合AI悦创|久远·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线，随时响应！

栈是什么？如果用生活中最常见的例子，我想到是书本的放置（当然这是部分人喜欢的做法）。但是给人的感觉是非常直接的，书本整齐跨一叠在一起，放在最上面的那本最先拿走，放在最底下那本书就最后拿走，形象吧，生活中有很多后进先出的栗子，就不一一说明了，用图来说明应该很好理解。

放在最上面的那本书的位置叫栈顶，栈顶是可变的，比如说你拿走了西游记，那么栈顶就是红楼梦得位置。相对应的栈底是不可操作的一端。
栈是一种特殊的线性表，特殊之处在于只能在一端对其进行操作，把元素放到栈中，这操作叫压栈(push)，压栈之后，栈顶指针就向上移动。把元素从栈顶弹出，这叫出栈(pop)，出栈后栈顶指针向下移动。访问栈只能从栈顶元素进行。栈是很重要的数据结构，在很多算法都有应用，比如图的深度优先遍历算法(DFS)，Dijkstra算法的中转站。

栈的实现分为两种，一是顺序栈，用数组来实现，二是链式栈，用指针将结点串联起来，与链表相似，但仅能在栈顶进行操作。

先实现简单的顺序栈，顺序栈简直不要太简单，上代码：

#ifndef STATICSTACK_H
#define STATICSTACK_H

template <typename T, int N>
class StaticStack
{
protected:
	T array[N];	// 使用模板参数决定栈的大小
	int m_top;	// 使用整型作为标记，相当于栈顶指针
	int m_size;	// 栈中数据元素的个数
public:
	StaticStack()	// 初始化操作得做一下
	{
		m_top = -1;
		m_size = 0;
	}
	
	bool push(const T& obj)	// 压栈操作，就是往数组增加一个元素
	{
		bool ret = m_size < N;	// 满了就没办法了
		
		if( ret )
		{
			array[++m_top] = obj;
			++m_size;
		}
		
		return ret;
	}
	
	bool pop()	// 出栈操作
	{
		bool ret = m_size > 0;
		
		if( ret )
		{
			--m_top;
			--m_size;
		}
		
		return ret;
	}
	
	T top()	// 获取栈顶元素
	{
		return array[m_top];
	}
	
	void clear()	// 把栈清空
	{
		m_top = -1;
		m_size = 0;
	}
	
	int size()	// 获取栈的大小
	{
		return m_size;
	}
	
	~StaticStack()
	{
		clear();
	}
};

#endif

来用一下这个简单顺序栈。记住，后进先出！

#include <iostream>
#include "StaticStack.h"

using namespace std;

int main(int argc, const char* argv[])
{
	StaticStack<int, 10> stack;

	for(int i = 0; i < 10; ++ i)
	{
		stack.push(i);
	}
	// 入栈的时候是 0123456789 的顺序
	
	for(int i = 0; i < 10; ++ i)
	{
		cout << stack.top() << endl;
		stack.pop();
	}
	
	return 0;
}

输出正确。OK,顺序栈就可以跳过了，因为顺序栈的实现依赖于原生数组，所以在定义的时候必须给定大小，并且在使用的过程中不能动态改变其大小，这是顺序栈的一个缺点，另外，当顺序栈存放的元素是类类型，那么在定义顺序栈时就会自动调用类的构造函数，有多少个元素就会调用多少次，这样做显然会降低效率，所以顺序栈的使用相对较少。

现在重点来实现链式栈吧，有了顺序栈的基础，实现链式栈也相当容易。
直接上代码：

#ifndef LINKSTACK_H
#define LINKSTACK_H

template <typename T>
class LinkStack
{
protected:
	struct Node
	{
		T data;
		Node* next;
	};
	mutable Node header;	// 使用头节点会方便各种操作
	int m_size;
	
public:
	LinkStack()
	{
		header.next = NULL;
		m_size = 0;
	}
	
	bool push(const T& obj)	// 压栈操作
	{
		bool ret = true;	
		Node* n = new Node();
		
		if( n != NULL )
		{
			n->data = obj;
			Node* current = &header;	// 相当于链表的头插
			n->next = current->next;
			current->next = n;
			++m_size;
		}
		else
		{
			ret = false;
		}
		
		return ret;
	}
	
	bool pop()	// 出栈操作
	{
		bool ret = true;
		
		if( m_size > 0 )
		{
			Node* current = &header;	// 相当于链表的头删
			Node* todel = current->next;
			current->next = todel->next;
			--m_size;
			delete todel;
		}
		else
		{
			ret = false;
		}
		
		return ret;
	}
	
	T top() const	// 获取栈顶元素
	{
		Node* current = header->next;
		
		return current->data;
	}
	
	int size() const
	{
		return m_size;
	}
	
	void clear()	// 清空栈
	{
		while( m_size > 0 )
		{
			pop();
		}
	}
	
	~LinkStack()
	{
		clear();
	}
};

#endif

仅仅是实现一个栈好像没有什么好玩的，顺序栈操作一个数组，链式就几个指针操作。现在用栈来实现一个扫描函数，将字符串中的左右符号进行匹配。举个栗子，“（ a { b c [ d < e " f ’ g’ " h > i ] j } k）”,这样一个看起来复杂l凌乱的字符串，怎么知道它的左右符号匹不匹配呢？人工智能嘛，人工来数一下不就可以了吗？Good idea！简单的数几分钟就应该知道结果了，要是一本书那么多的字符串怎么来数？当然是把工作交给计算机！写个程序来检查左右符号是否匹配不就得了。主要注意的地方是左符号、右符号以及引号的处理，其他字符直接忽略。知道重点了，实现就容易了，说干就干，动手！

#include <iostream>
#include "LinkStack.h"

// 需要提前准备相应的辅助函数
bool is_Left(const char c)	// 判断是否为左符号
{
	return (c == '(') || (c == '{') || (c == '<') || (c == '[');
}

bool is_Right(const char c)	// 判断是否为右符号
{	
	return (c == ')') || (c == '}') || (c == '>') || (c == ']');
}
	
bool is_Quot(const char c)	// 判断是否为引号
{
	return (c == '\'') || (c == '\"');
}

bool is_Match(const char l,const char r)	// 进行匹配判断
{
	bool ret = ( (l == '(') && (r == ')') )   ||
		   ( (l == '{') && (r == '}') )   ||
		   ( (l == '[') && (r == ']') )   ||
		   ( (l == '<') && (r == '>') )   ||
		   ( (l == '\'') && (r == '\'') ) ||
		   ( (l == '\"') && (r == '\"') ) ;	
		   
	return ret;
}

bool scan_func(const char* str)	// 扫描字符串的函数
{
	bool ret = true;	
	int i = 0;
	str = str ? str : "";	// 参数合法性判断，如果参数为空，则用空字符串代替
	LinkStack<char> stack;	// 看着怎么使用栈吧

	while( ret && (str[i] != '\0') )	// 循环遍历字符串
	{					// 如果有不匹配的字符就立即结束循环
		if( is_Left(str[i]) )		// 左符号，直接入栈
		{
			stack.push(str[i]);
		}
		else if( is_Right(str[i]) )	// 右符号，判断栈是否为空
		{				// 如果栈为空，结束循环
			if( (stack.size() > 0) && (is_Match(stack.top(), str[i])) )		
			{
				stack.pop();	// 栈不为空，且与栈顶元素能匹配，那就把栈顶中的左符号出栈
			}
			else
			{
				ret = false;	
			}
		}
		else if( is_Quot(str[i]) )	// 引号判断
		{				// 如果栈为空或者与栈顶元素不匹配，入栈
			if( (stack.size() == 0) || (!is_Match(stack.top(), str[i])) )
			{
				stack.push(str[i]);
			}			// 与栈顶元素匹配，那就将栈顶的引号出栈
			else if( is_Match(stack.top(), str[i]) )
			{
				stack.pop();
			}
		}
	}
	
	return (ret && (stack.size() == 0) );
}

int main(int argc, const char* argv[])
{
	const char* str1 = " < ( [ { 123 } ] ) > ";
	const char* str2 = " \" \' 123 \' \" ";
	const char* str3 = "< 123 ";

	cout << endl;
	cout << str1 << " result of match : " << ( scan_func(str1) ? " true " : " false " ) << endl;
	
	cout << endl;
	cout << str2 << " result of match : " << ( scan_func(str2) ? " true " : " false " ) << endl;
	
	cout << endl;
	cout << str3 << " result of match : " << ( scan_func(str3) ? " true " : " false " ) << endl;
	
	
	return 0;
}

看看输出结果，多easy，要是用人工的智能来数，得花点点点时间。

你好，我是久远，上次我们进行了关于栈的讲解，我们先来对知识进行回顾：

• 什么是栈

栈是有序集合，队列元素的增添和移除总是发生在同一端的，这一端我们称之为栈顶，另一端称之为栈底，栈中的元素离底端越近，代表其在栈中的时间越长，最新添加的元素将被最先移除。这种排序原则被称作 LIFO（last-in first-out），即后进先出。它提供了一种基于在集合中的时间来排序的方式。最近添加的元素靠近顶端，旧元素则靠近底端。

• 栈的重要操作

栈中最重要的两个操作是出栈和入栈，我们在 python 中一般通过列表来实现栈的出入。

接下来我们来进行队列的学习，队列和栈一样，是非常简单的数据结构，但是也是非常常见的数据结构。

什么是队列

队列和栈一样，也是有序集合，但它不同于栈的地方在于，队列中的元素是从一端进入，另一端出去。添加操作发生在“尾部”，移除操作则发生在“头部”。新元素从尾部进入队列，然后一直向前移动到头部，直到成为下一个被移除的元素。最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO（first-in first-out），即先进先出，也称先到先得。

队列字如其名，它的例子在生活中也是比比皆是的，我们现实中的排队即为队列的应用。

日常生活中，我们进电影院要排队，在超市结账要排队，好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况。

队列的实现

队列的实现分为队列的定义和操作，如前所述，队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是 先进先出（FIFO），它支持以下操作。

• Queue() ：创建一个空队列。它不需要参数，且会返回一个空队列。
• enqueue( item ) ：在队列的尾部添加一个元素。它需要一个元素作为参数，不返回任何值。
• dequeue() ：从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队 列的内容。
• isEmpty() ：检查队列是否为空。它不需要参数，且会返回一个布尔值。
• size() ： 返回队列中元素的数目。它不需要参数，且会返回一个整数。

创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样，我们利用简洁强大的列 表来实现队列。 既然要创建队列，我们首先要确认队列的头尾，在这里我们假设队列的尾部在列表的位置 0 处。

首先我们对队列类进行定义，一个队列中最主要最核心的要素就是队列中的元素，而新生成一个队列时，这个队列中往往没有任何元素，因此我们对队列的初始化定义为：队列中的元素为空，即引用的列表为空列表。

代码如下：

class Queue:
    def __init__(self):
        self.items = []

当一个队列生成以后，最常见的计算队列长度的操作是必不可少的，因此只需要计算引入列表的长度即可。

代码如下：

def size(self):
        return len(self.items)

既然可以计算长度，那么我们也可以判断队列是否为空，通常我们只需判断引入的列表是否为空列表即可判断队列是否为空了。

代码如下：

def isEmpty(self):
        return self.items == []

接下来就是我们似曾相识，但是又用途非常广泛的两种操作了，插入和删除，我们在前面讲解栈的时候进行了出栈和入栈的操作，而在队列中也有类似的操作，即入队和出队，而队列和栈最大的不同便是，入队和出队并不是在同一个地方执行的。添加操作发生在“尾部”，移除操作则发生在“头部”。

我们在此设引入的列表的 0 号位为队列的尾部，传入要插入的元素 item ，默认将其插入到列表首位，即队列的入队操作，代码如下：

def enqueue(self, item):
        self.items.insert(0,item)

我们在此设引入的列表的表尾为队列的头部，要进行出队操作，只需删除列表的最后一个元素即可。代码如下：

def dequeue(self):
        return self.items.pop()

整体的代码如下：

class Queue:
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return self.items == []
    
    def size(self):
        return len(self.items)
    
    def enqueue(self, item):
        self.items.insert(0,item)
        
    def dequeue(self):
        return self.items.pop()

总结

恭喜你又学完了一个知识点，队列和栈的知识是不是很简单呢？只需要掌握列表的一些要点，就可以轻松的将队列和栈实现，我们在基础篇只讲解了最基础的实现方法，在后续的提高篇里会告诉大家在考试或者就业面试中，站和队列要怎么运用。

流沙团队联合AI悦创|久远·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。QQ、微信在线，随时响应！