目录

• 3.1栈和队列的定义和特点
  • 3.1.1栈的定义和特点
    • 1定义：
    • 2.特点：
    • 3.存储结构：
  • 3.1.2队列的定义和特点
    • 1.定义：
    • 2.特点：
    • 3.存储结构：
• 3.2案例引入
  • 1.案例3.1：数制的转换
    • 1.案例分析：
    • 2.代码：
    • 3.算法步骤：
  • 2、案例3.2：括号匹配的检验
    • 1.案例分析：
    • 2.代码：
    • 3.算法步骤：
  • 3.案例3.3：表达式求值
    • 1.案例分析：
    • 2.代码：
    • 3.算法步骤：
  • 4.案例3.4：舞伴问题
    • 1.案例分析：
    • 2.代码：
    • 3.算法步骤：
• 3.3栈的表示和操作的实现
  • 3.3.1栈的类型定义
  • 3.3.2顺序栈的表示和实现
    • 1.定义：
    • 2.栈的初始化
    • 3.入栈
    • 4.出栈
    • 5.取出栈顶元素

3.1栈和队列的定义和特点

3.1.1栈的定义和特点

1定义：

​ 栈是限定仅在表尾进行插入或者删除操作的线性表。因此，对于栈来说，表尾端有其特殊含义，称为栈顶，相应的，表头端称为栈底。不含元素的空表称为空栈。

2.特点：

​ 先进后出(FILO)

3.存储结构：

​ 顺序栈和链式栈，实际上栈的本质是线性表，不过是加了操作限制

3.1.2队列的定义和特点

1.定义：

​ 和栈类似都是操作受限制的线性表，只允许在一端进行插入(队尾：rear)，在一端进行删除(队头：front)；

2.特点：

​ 先进先出(FIFO)

3.存储结构：

​ 顺序队和链式队

3.2案例引入

1.案例3.1：数制的转换

1.案例分析：

​ 当将一个十进制整数N转换为八进制数时，在计算过程中，把N与8求余得到的八进制数的各位依次进栈，计算完毕后将栈中的八进制数依次出栈输出，输出结果就是待求得的八进制数

2.代码：

void conversion(int n)
{//对于任意一个非负十进制数，打印输出与其等值的八进制数
  InitStack(S);           //初始化栈
  while(N)                //当N非零时，循环
  {
     Push(S,N%8);         //把N与8求余得到的八进制数压入栈S
      N=N/8;              //N更新为N与8的商
  }
  while(!StackEmpty(S))   //当栈为非空时，循环
  {
     Pop(S,e);            //弹出栈顶元素e
     cout<<e;             //输出e
  }
}

3.算法步骤：

1、初始化一个空栈S。

2、当十进制数N非零时，循环执行以下操作：

把N与8求余得到的八进制数压入栈S；

N更新为N与8的商。

3、当栈S非空时，循环执行以下操作：

弹出栈顶元素e；

输出e。

2、案例3.2：括号匹配的检验

1.案例分析：

​ 用栈处理括号匹配问题，读取表达式，当是左括号时，压入栈；等待匹配的右括号；
当读取到与之匹配的右括号时，把栈顶的左括号弹出；依次类推直到表达式扫描完毕。
最后得出结论表达式是否匹配成功。

2.代码：

/***链栈实现括号匹配***/

#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char SElemType;
typedef int Status;
typedef struct SNode {
	int data;
	struct SNode *next;
} SNode, *LinkStack;

Status InitStack(LinkStack &S) {
	S = NULL;
	return OK;
}
bool StackEmpty(LinkStack S) {
	if (!S)
		return true;
	return false;
}
Status Push(LinkStack &S, SElemType e) {
	SNode *p = new SNode;
	if (!p) {
		return OVERFLOW;
	}
	p->data = e;
	p->next = S;
	S = p;
	return OK;
}
Status Pop(LinkStack &S, SElemType &e) {
	SNode *p;
	if (!S)
		return ERROR;
	e = S->data;
	p = S;
	S = S->next;
	delete p;
	return OK;
}
Status GetTop(LinkStack &S) {
	if (!S)
		return ERROR;
	return S->data;
}

//算法3.21　括号的匹配
Status Matching() {//检验表达式中所含括号是否正确匹配，如果匹配，则返回true，否则返回false
	//表达式以“#”结束
	char ch;
	SElemType x;
	LinkStack S;
	InitStack(S); //初始化空栈
	int flag = 1; //标记匹配结果以控制循环及返回结果
	cin >> ch; //读入第一个字符
	while (ch != '#' && flag) //假设表达式以“#”结尾
	{
		switch (ch) {
		case '[' :
		case '(': //若是左括号，则将其压入栈
			Push(S, ch);
			break;
		case ')': //若是“)”，则根据当前栈顶元素的值分情况考虑
			if (!StackEmpty(S) && GetTop(S) == '(')
				Pop(S, x); //若栈非空且栈顶元素是“(”，则正确匹配
			else
				flag = 0; //若栈空或栈顶元素不是“(”，则错误失败
			break;
		case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑
			if (!StackEmpty(S) && GetTop(S) == '[')
				Pop(S, x); //若栈非空且栈顶元素是“[”，则正确匹配
			else
				flag = 0; //若栈空或栈顶元素不是“[”，则错误匹配
			break;
		} //switch
		cin >> ch; //继续读入下一个字符
	} //while
	if (StackEmpty(S) && flag)
		return true; //匹配成功
	else
		return false; //匹配失败
}
int main() {
	LinkStack S;
	cout << "请输入待匹配的表达式，以“#”结束：" << endl;
	int flag = (int) Matching();
	if (flag)
		cout << "括号匹配成功！" << endl;
	else
		cout << "括号匹配失败！" << endl;
	return 0;
}

3.算法步骤：

1、先定义、创建栈的操作(查、删、插)；
2、定义括号匹配算法brack，初始化栈；
3、设置标记性变量flag来表决循环匹配结果，1表示匹配成功，0则不匹配；
4、扫描表达式，判断是否符合匹配条件，是左括号就调用Push压入栈

3.案例3.3：表达式求值

1.案例分析：

任何一个表达式都是由操作数(operand)运算符(operator)和界限符(delimiter)组成的，统称它们为单词。一般地，操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符 3 类；基本界限符 有左右括号和表达式结束符等。为了叙述的简洁，在此仅讨论简单算术表达式的求值问题，这种表达式只含加、减、乘、除4种运算符。读者不难将它推广到更一般的表达式上。

2.代码：

char EvaluateExpression () 
｛//算术表达式求值的算符优先算法，设OPTR和OPND分别为运算符栈和操作数栈
	InitStack(OPND); //初始化OPND栈
	InitStack(OPTR); //初始化OPTR栈
	Push (OPTR,'#') ; // 将表达式起始符＂＃＂ 压人OPTR栈
	cin>>ch; 
	while(ch!='#' | | GetTop(OPTR) !='#' ) //表达式没有扫描完毕或OPTR的栈顶元素不为"# "
	{
		if (!In (ch)) {Push (OPND, ch); cin»ch;} //ch不是运算符则进OPND栈
		else 
			switch (Precede (GetTop (OPTR) , ch))  //比较OPTR的栈顶元素和ch的 优先级
			{
				case'<': 
					Push(OPTR,ch);cin>>ch; //当前字符ch压入OPTR栈，读入下一字符ch
					break; 
				case'>': 
					Pop(OPTR,theta); //弹出OPTR栈顶的运算符
					Pop(OPND,b);Pop(OPND,a); //弹出OPND栈顶的两个运算数
					Push (OPND, Operate (a, theta, b·)); / /将运算结果压入OPND栈
					break; 
				case'=': //OPTR的栈顶元素是"("且ch是")"
					Pop(OPTR,x) ;cin>>ch; //弹出OPTR栈顶的"(", 读入下一字符ch
					break; 
			}//switch 
	}//while 
	return GetTop (OPND) ; //OPND栈顶元素即为表达式求值结果
}

3.算法步骤：

1.初始化OPTR栈和OPND栈，将表达式起始符“#”压入OPTR栈。
2.扫描表达式，读人第一个字符ch，如果表达式没有扫描完毕至“#”或OPTR的栈顶元素不为“#”时，则循环执行以下操作:
若ch不是运算符，则压入OPND栈，读入下一字符ch;
若ch是运算符，则根据OPTR 的栈顶元素和ch的优先级比较结果，做不同的处理:
若是小于，则ch 压入OPTR栈,读入下一字符ch;
若是大于，则弹出OPTR栈顶的运算符，从 OPND栈弹出两个数，进行相应运算，结果压入OPND栈;
若是等于，则OPTR 的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于括号匹配成功，然后读人下一字符ch。
3.OPND栈顶元素即为表达式求值结果，返回此元素。

4.案例3.4：舞伴问题

1.案例分析：

对千舞伴配对问题，先入队的男士或女士先出队配成舞伴，因此设置两个队列分别存放男士和女士入队者。假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。 当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。 此时，若某队仍有等待配对者，则输出此队列中排在队头的等待者的姓名，此人将是下一轮舞曲开始时第一个可获得舞伴的人。

2.代码：

void DancePartner(Person dancer[],int num) 
｛//结构数组dancer中存放跳舞的男女，num是跳舞的人数。
	InitQueue(Mdancers); //男士队列初始化
	InitQueue(Fdancers); //女士队列初始化
	for(i=0;i<num;i++) //依次将跳舞者根据其性别人队
	{
		p=dancer[i]; 
		if (p.sex=='F') EnQueue(Fdancers, p); / /插入女队
		else EnQueue(Mdancers,p); //插人男队
	}
	cout<<"The dancing partners are:\n"; 
	while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)) 
	｛//依次输出男女舞伴的姓名
		DeQueue(Fdancers,p); //女士出队
		cout<<p. name<<" "; //输出出队女士姓名
		DeQueue(Mdancers,p); //男士出队
		cout<<p.name<<endl; //输出出队男士姓名
	}
	if (! QueueEmpty (Fdancers)) //女士队列非空，输出队头女士的姓名
	{
		p=GetHead(Fdancers); //取女士队头
		cout<<"The first woman to get a partner is: "<< p.name<<endl; 
	}
	else if (!QueueEmpty (Mdancers)) //男士队列非空，输出队头男士的姓名
	{
		p=GetHead(Mdancers); //取男士队头
		cout<<"The first man to get a partner is: "<< p.name<<endl; 
	}
}

3.算法步骤：

1.初始化 Mdancers 队列和 Fdancers 队列。
2.反复循环，依次将跳舞者根据其性别插入 Mdancers 队列或 Fdancers 队列。
3.当 Mdancers 队列和 Fdancers 队列均为非空时， 反复循环， 依次输出男女舞伴的姓名。
4.如果 Mdancers 队列为空而 Fdancers 队列非空， 则输出 Fdancers 队列的队头女士的姓名。
5.如果 Fdancers 队列为空而 Mdancers 队列非空， 则输出 Mdancers 队列的队头男士的姓名。

3.3栈的表示和操作的实现

3.3.1栈的类型定义

栈的基本操作除了入栈和出栈外，还有栈的初始化，栈空长大判定，以及取栈顶元素等。下面给出栈的抽象数据类型定义

3.3.2顺序栈的表示和实现

顺序栈:利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,把数组中下标为0的一端作为栈底,为了只是栈中元素的位置,我们定义变量top来指示栈顶元素在顺序栈中的位置,top为整型.

1.定义：

public class sequenceStack {
    final int MaxSize=10;
    private T[] stackArray;
    private int top;

    public sequenceStack(){}
    public sequenceStack(int n){}
    
    //在栈顶插入一个新元素
    public void push(T obj){}
    
    //删除栈顶元素
    public T pop(){}
    
    //取出栈顶数据元素
    public T getHead(){}
    
    //判断当前栈是否为空
    public boolean isEmpty(){}
    
    //求出栈中数据元素的个数
    public int size(){}
    
    //依次访问栈中每个元素并输出
    public void nextOrder(){}
    
    //销毁一个已存在的栈
    public void clear(){}

}

ps:1.top为指针，top指向栈顶元素的位置

top的初始值为-1，指向栈底，而这个top==-1也可作为栈空的标志，每当插入一个新的栈顶元素时，先把栈顶指针top增加1，再把入栈的元素放到top指针指向的位置。
删除栈顶元素时，先删除栈顶，再将栈顶指针top减去1。
非空栈中的栈顶指针top始终在栈顶元素的位置上。

2.栈的初始化

public class sequenceStack {
    final int MaxSize=10;
    private T[] stackArray;
    private int top;

public sequenceStack(){
    top=-1;
    stackArray=(T[])new Object[MaxSize];

}

public sequenceStack(int n){
    if (n<=0){
        System.out.println("array length must large than 0");
        System.exit(-1);
    }
    top=-1;
    stackArray=(T[])new Object[n];
}

3.入栈

入栈时，首先应该判断栈是否满了，栈满时，不能入栈，否则出现空间溢出，引起错误，这种现象称为上溢。

public void push(T obj){
    if (top==stackArray.length-1){
        T []p=(T[])new Object[top*2+2];
        for(int i=0;i<top+1;top++)
            p[i]=stackArray[i];
        stackArray=p;
    }
    top++;
    stackArray[top]=obj;
}

4.出栈

出栈时，需要先判断栈是否为空，为空时不能出栈，否则会产生错误。

//删除栈顶元素
public T pop(){
    if(top==-1){
        System.out.println("stack is empty!");
        return null;
    }
    top=top-1;
    return stackArray[top+1];
}

5.取出栈顶元素

读栈时，需要先判度栈是否为空，为空时，不能操作，否则产生错误。

//取出栈顶数据元素
public T getHead(){
    if(top==-1){
        System.out.println("the stack is empty!");
        return null;
    }
    return stackArray[top];