Notes for Lecture 4

---

Vector的嵌套

---

ADT

What is it？

抽象数据类型 (ADT)；数据集合和定义在该数据集合上的操作规范

Stack

定义：

应用：

#include"stack.h"

• size()方法返回值会动态变化,当用作条件判断时需注意是否需要使用初始长度or动态长度

栈的练习：

• 匹配思想：

• 从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。

Answer：

int check(string str)
{
	Stack <char> stack;
	int len = str.length();
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '(' || str[i] == '{')
		{
			stack.push(str[i]); //左(花)括号均压入栈
		}
		else if (str[i] == ')' || str[i] == '}')  //将右(花)括号与栈中左花括号匹配
		{
			if (!stack.isEmpty() && stack.peek() == str[i])  //弹出栈顶元素是需判断栈是否为空
			{				
				stack.pop();
			}
			else if (!stack.isEmpty() && stack.peek() != str[i)
			{
				return i;
			}
		}
	}
	if (!stack.isEmpty)  //通过判断栈是否为空来判断是否存在左(花)括号的case
	{
		return len;  
	}else
	return -1;
}

Quene

定义：

应用：

#include"quene.h"

• size()方法返回值会动态变化,当用作条件判断时需注意是否需要使用初始长度or动态长度

队列的练习：

• 匹配思想：

• 队列与栈的交互
  栈暂存队列弹出的元素
  队列弹出元素同时重新压回本身，恢复原状态
  将栈中元素重新压入队列(LIFO)

Answer：

void mirror(Quene<string>& quene)
{
	int len = quene.size(); //记录队列长度
	Stack <string> stack;
	for (int i = 0; i < len; i++)
	{
		string elem = quene.dequene();
		quene.enquene(elem); //恢复
		stack.push(elem);
	}
	while (!stack.isEmpty())
	{
		quene.enquene(stack.pop());
	}
}