堆栈

栈的概念

栈（Stack）是操作受限的线性表，插入和删除数据元素的操作只能在线性表的一端进行。

 

当然，你也可以简单理解栈为一个很多层的篮子，一层篮子只能存放一个数据，我们对这个篮子能处理的就只有最上面的那个数据。

往篮子里放入数据的过程就叫做插入（入栈，进栈，压栈）

把篮子最上面的那一层数据拿出的过程就叫做删除（出栈，弹栈）

 

栈的主要操作

入栈（Push）

出栈（Pop）

Rg6ag.png

操作特性：后进先出

栈的顺序储存结构

顺序栈—-栈的顺序储存结构

Rgjdl.png

指针top指示栈顶元素在数组中的位置

 

进栈：top+1

栈空：top = -1

栈出：top-1

栈满：top = MAX_SIZE

 

栈的上溢与下溢

在顺序栈中有”上溢”和”下溢”的概念。

顺序栈好比一个盒子，我们在里面放了一叠书，当我们要用书的话只能从最上面一本开始拿，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了，这时就是“上溢”，“上溢”也就是栈顶指针指出栈的外面，显然时出错了。

反之，当栈中已经没有书时，我们再去拿，发现已经没有书了，这就是“下溢”。“下溢”本身可以表示栈为栈空，因此可以用它来作为控制转移的条件。

 

Rg9yb.png

如图

1.$a_N,…,a_2,a_1$用来储存数据。

2.定义一个top变量储存栈顶指针的位置。

3.定义一个MAX_SIZE表示栈的最大容量。

 

上溢的判断

当栈为空时，top的值为-1.当往栈中压入一个元素时，top的值就会加1.

这样，a[0]就代表第一个进栈的元素，a[i-1]代表第i个进栈的元素，a[top]则表示栈顶的元素。

当top=MAX_SIZE-1时，表示栈满。如果再有元素进栈时，则栈会溢出，这时称为”上栈”。

下栈的判断

反之，当top=-1时，再将栈顶元素弹出，就要发生”下溢”

 

栈类的定义

栈类的定义（以储存字符型数据为例）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int MAX_SIZE = 100; //定义栈最大常数值
class Stack
{
    private:
    	char* data;     //线性表
    	int size;       //堆栈的实际大小
    	int top;        //栈顶
	public:
    Stack();               //构造函数
    Stack(int s);          //有参构造函数
    ~Stack();			   //析构函数
    void push(char ch);	   //成员函数：入栈
    char pop();            //成员函数：出栈并返回栈顶元素
    char getTop();           //成员函数：获得栈顶元素
    bool isEmpty();        //成员函数：栈是否为空
    bool isFull();         //成员函数：栈是否满
    void setNull();        //设置栈为空
}

构造函数

1
2
3
4
5
Stack::Stack(){
	size = MAX_SIZE;
	top = -1;
	data = new char[MAX_SIZE];//缺省构造函数
}
1
2
3
4
5
Stack::Srack(int s){
	size = s;
	top = -1;
	data = new char[size]; //根据指定的大小分配栈的内存空间
}

析构函数

1
2
3
Stack::~Stack(){
	delete[]data;     //内存回收
}

入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
Stack::push(char ch){
	if(isFull())     //解决数据上溢问题
    {
        cout<<"栈已满，无法入栈"<<endl;
    }
    else
    {
        top++;
        data[top] = ch;
        cout<<"已将元素"<<ch<<"压入栈中"<<endl;
        cout<<"此时top="<<top<<endl;
	}
}

出栈并返回栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Stack::pop()
{
    if(!isEmpty())
    {
        cout<<"出栈中"<<endl;
        top--;
        cout<<"此时top="<<top<<endl;
    	return data[top+1];//返回被删除元素
    }
    else //解决数据下溢过程
    {
        cout<<"栈已为空，无法继续出栈"<<endl;
    }
}

获得栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Stack::getTop()
{
 	if(!isEmpty())
    {
    	cout<<"获得栈顶元素中..."<<endl;
        cout<<"此时top="<<top<<endl;
        cout<<"栈顶元素为";
        return data[top];
    }   
    else
    {
        cout<<"栈已为空，无法获得栈顶元素"<<endl;
    }
}

栈是否为空

1
2
3
4
5
6
7
Stack::isEmpty()
{
    if(top = -1)
        return 1;  //栈为空
    else
        return 0;  //栈不为空
}

栈是否满

1
2
3
4
5
6
7
8
9
Stack::isFull
{
    if(top >= size - 1)
    {
        return 1;//栈已满
    }
    else
        return 0； //栈未满
}

设置栈为空

memset函数

1
void *memset(void *s, int ch, size_t n);

s中当前位置开始向后的n个字节中，把n个字节的每个字节都替换成ch。

1
2
3
char str[] = "This is a new world";
memset (str,'#',6);
cout<<str<<endl;

输出为

1
######s a new world

 

1
2
3
4
5
6
7
Stack::setNull(int len)
{
	memset(data,0,len *sizeof(char));
    //将char中元素全班替换为0
	this->top = -1;
	cout<<"此时top="<<top<<endl;
}

 

用异常捕获优化顺序栈

函数中最好不要有cout的输出语句，为保证类能多次重用。

输入输出的语句在display或者main函数中即可。

用try…catch语句

1
2
3
4
5
6
7
8
9
10
11
12
13
	try{
    语句1;
    语句2;
    语句3;
    ...
}
	catch(异常类型){
    异常处理代码
}
...
    catch(异常处理){
        异常处理代码
    }

 

自定义异常类的使用

定义一场内部类（在类的声明部分定义）

1
class Empty{};

丢出异常类（在pop函数遇到空栈时的语句）

1
throw Empty();

捕获异常类（在调用pop函数时，用try/catch捕获）

1
2
3
4
5
6
try{
       stack.pop();
   }
catch(Stack::Empty){
       cout<<"Stack Empty!!"<<endl;
   }

 

用类模板实现顺序栈

通用的栈类

DataType就是我们要使用的数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class DataType>
class Stack{
public :
    Stack();                    //初始化栈
    ~Stack();                   //销毁栈
    int empty();                //判断栈是否为空
    int pop(DataType & x);   //出栈
    int push(DataType x);    //压栈
    DataType top();          //取栈顶元素
    void print();               //遍历栈
private :
    DataType * data;         //栈数据储存
    int len;                    //栈当前元素个数
};

成员函数定义

1
2
3
4
5
6
7
8
9
10
11
template<class DataType>
Stack<DataType>::Stack(){
......
}
......
template<class DataType>
void Stack<DataType>::push(DataType e){
......
}
......
};

有类Stack的地方，后面都要改成Stack

 

为了使用类模板对象，必须显示指定模板参数

1
2
Stack<char> charStack;
Stack<int> intStack;

存在问题

(44条消息) c++模板学习10之类模板分文件编写_热爱编程的大忽悠的博客-CSDN博客

 

双端堆栈（两栈共享存储空间）

优点：提高空间利用率

两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。

RUZ9v.png

 

性质

栈1为空

1
top1 = -1;

栈2为空

1
op2 = Stack_Size;

栈满

1
top1+1 == top2;

两栈共享空间类的声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int Stack_Size=100;  
class BothStack 
{
  public:
       BothStack( );
       ~BothStack( ); 
       void Push(int num, DataType x);   
    //num表示要处理1号栈还是2号栈
       DataType Pop(int num);          
       DataType GetTop(int num);       
       bool isEmpty(int num);     
  private:
       DataType data[Stack_Size];     
       int top1, top2;        
};

当然，也可以用类模板去实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int Stack_Size=100;  
template <class T>
class BothStack 
{
  public:
       BothStack( );
       ~BothStack( ); 
       void Push(int i, T x);   
       T Pop(int i);          
       T GetTop(int i);       
       bool Empty(int i);     
  private:
       T data[Stack_Size];     
       int top1, top2;        
};

 

插入

1
2
3
4
5
6
7
8
9
1. 如果栈满，则抛出上溢异常；
2. 判断是插在栈1还是栈2；
       2.1 若在栈1插入，则
             2.1.1 top1加1;
             2.1.2 在top1处填入x；
       2.2 若在栈2插入，则
             2.2.1 top2减1;
             2.2.2 在top2处填入x；

代码实现

1
2
3
4
5
6
7
8
9
10
11
template <class T> 
void BothStack<T>::Push(int i, T x )
{
   if (top1==top2-1) 
   	throw "上溢";
   if (i==1) 
   	data[++top1]=x;
   if (i==2) 
   	data[--top2]=x;
}

删除

1
2
3
4
5
6
1.若是在栈1删除，则
	1.1 若栈1为空栈，抛出下溢异常；
	1.2 删除并返回栈1的栈顶元素；
2.若是在栈2删除，则
	2.1 若栈2为空栈，抛出下溢异常；
	2.2 删除并返回栈2的栈顶元素；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class DataType>
DataType BothStack<DataType>::Pop(int i){
   if (i == 1) {   
       if (top1 == -1) 	
           throw "下溢";
       return data[top1--];
   }
   if (i == 2) {                           
       if (top2 == StackSize)  	
           throw "下溢";
       return data[top2++]; 
  }
}

判断每个栈空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class DataType> 
bool BothStack<DataType>::Empty(int i)
{  
    if(i == 1){     //对于栈1操作
        if(top1 == -1) 	
            return 1;  //栈空就返回1
        else 	return 0;
    }
    if(i == 2)	{    //对于栈2操作
        if(top2 == StackSize)	
            return 1;  
        else  return 0;
    }
}

取某个栈顶

1
2
3
4
5
6
7
8
9
10
11
12
template <class DataType> 
DataType BothStack<DataType>::GetTop(int i)
{
    if(i==1)	{
        if (top1!=-1) 	
            return data[top1];
    }
    if(i==2)	{
        if(top2!=StackSize)  
            return data[top2];
   } 
}

 

压栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class DataType>
void BothStack<DataType>::push(int num, DataType x){
  if(isFull(num)){      //如果栈已满
    throw BothStack<DataType>::Full();
  }
  else{
    if(num == 1){
      top1++;
      data[top1] = x;
    }
    else if(num == 2){
      top2--;
      data[top2] = x;
    }
  }
}

 

出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class DataType>
DataType BothStack<DataType>::pop(int num){
  if(num == 1){
    if(isEmpty1(num)){       //如果栈空
      throw BothStack<DataType>::Empty1();
    }
    else{
      return data[top1--];
    }
  }
  else if(num == 2){
    if(isEmpty2(num)){
      throw BothStack<DataType>::Empty2();
    }
    else{
      return data[top2++];
    }
  }
}

取栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class DataType>
DataType BothStack<DataType>::getTop(int num){
  if(num == 1){
    if(isEmpty1(num)){
      throw BothStack<DataType>::Empty1();
    }
    else{
      return data[top1];
    }
  }
  else if(num == 2){
    if(isEmpty2(num)){
      throw BothStack<DataType>::Empty2();
    }
    else{
      return data[top2];
    }
  }
}

 

栈的链式储存

通用类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class DataType>
class LinkStack{
private:
  typedef struct node{
  DataType data;
  struct node*next;
  }Node;
   Node *top;
public:
  LinkStack();
  ~LinkStack();
  void push(DataType x);
  DataType pop();
  DataType getTop();
  bool isEmpty();
  class Empty{};
};

成员函数

初始化链栈
1
2
3
4
template <class DataType>
LinkStack<DataType>::LinkStack(){
  top == NULL;
}

销毁栈

1
2
3
4
5
6
7
8
9
10
11
template <class DataType>
LinkStack<DataType>::~LinkStack(){
  Node *q = top;
  Node *p = top -> next;
  while(top->next){
    q = p ->next;
    delete(p);
    p = q ->next;
  }
  delete(top);
}

压栈

1
2
3
4
5
6
7
8
template <class DataType>
void LinkStack<DataType>::push(DataType x){
  Node *s ;
  s = new Node;
  s->data = x;
  s->next = top;
  top = s;
}

是否栈空

1
2
3
4
5
6
7
template <class DataType>
bool LinkStack<DataType>::isEmpty(){
  if(top == NULL)
    return true;
  else
    return false;
}

取栈顶元素

1
2
3
4
5
6
7
8
9
10
template <class DataType>
DataType LinkStack<DataType>::pop(){
  if(isEmpty())
    throw LinkStack<DataType>::Empty();
  DataType x = top->data;
  Node*p = top;
  top = top ->next;
  delete p;
  return x;
}

取栈顶元素

1
2
3
4
5
6
7
template <class DataType>
DataType LinkStack<DataType>::getTop(){
  if(isEmpty())
    throw LinkStack<DataType>::Empty();
  DataType x = top->data;
  return x;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

template<class DataType>

int main()
{
  typedef LinkStack <int> intStack;
  int x;
  intStack s;
  s.push(1);
  s.push(2);
  s.push(3);
  cout <<"栈顶元素："<< s.getTop() <<endl;
  try{
    x = s.pop();
    cout << x <<endl;
    x = s.pop();
    cout << x <<endl;
    x = s.pop();
    cout << x <<endl;
  }
  catch(intStack::Empty){
    cout << "LinkStack is Empty!"<<endl;
  }
  return 0;
}

 

栈的应用—表达式求值

一、表达式求值的规则

表达式求值是程序设计语言编译中的一个基本问题。它的实现就是对“栈”的典型应用。
首先了解算术四则运算的运算规则：
（1）先乘除，后加减。
（2）从左到右计算
（3）先算括号内，再算括号外

 

任何一个表达式都由操作数（operand）、运算符（operator）和界定符组成：

 

二、运算符优先级

对于两个相继出现的操作符$\theta_1$和$\theta_2$有三种关系：
$\theta_1$ <$\theta_2$ $\theta_1$的优先级低于$\theta_2$
$\theta_1$ =$\theta_2$ $\theta_1$的优先级等于$\theta_2$
$\theta_1$ >$\theta_2$ $\theta_1$的优先级高于$\theta_2$
由此可以列出“+-*/”之间的优先级。如下图

RUmdr.png

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char getPriority(char theta1, char theta2)   //获取theta1与theta2之间的优先级  
{
    const char priority[][7] =     //算符间的优先级关系  
    {
        { '>','>','<','<','<','>','>' },
        { '>','>','<','<','<','>','>' },
        { '>','>','>','>','<','>','>' },
        { '>','>','>','>','<','>','>' },
        { '<','<','<','<','<','=','0' },
        { '>','>','>','>','0','>','>' },
        { '<','<','<','<','<','0','=' },
    };

    int index1 = getIndex(theta1);    //theta_1即为表中的行
    int index2 = getIndex(theta2);    //theta_1即为表中的列
    return priority[index1][index2];   //返回表中的index1行index2列
}
//其返回值为>,<,=

三、算法思路

为实现优先算法，可以使用两个工作栈，一个是OPTR，用于寄存运算符，一个是OPND，用于寄存操作数和运算结果。算法的基本思想是：
（1） 首先置操作数栈为空栈，表达式起始符’#’为栈底元素。
（2）依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级作相应操作，直至整个表达式求值完毕（OPTR栈顶元素和当前读入的字符均为’#’）

RUgvc.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
double getAnswer() {   //表达式求值  
{
    opter.push('#');      //首先将'#'入栈opter  
    int counter = 0;      //添加变量counter表示有多少个数字相继入栈，实现多位数的四则运算  
    char c = getchar();    //读取缓冲区
    while (c != '#' || opter.top() != '#')   //终止条件  
    {
        if (isdigit(c))   //如果c在'0'~'9'之间  
        {
            if (counter == 1)   //counter==1表示上一字符也是数字，所以要合并，比如12*12，要算12，而不是单独的1和2  
            {
                double t = opval.top();
                opval.pop();
                opval.push(t * 10 + (c - '0'));
                counter = 1;
            }
            else
            {
                opval.push(c - '0');     //将c对应的数值入栈opval  
                counter++;
            }
            c = getchar();   //读取缓冲区
        }
        else
        {
            counter = 0;   //counter置零  
            switch (getPriority(opter.top(), c))   //获取运算符栈opter栈顶元素与c之间的优先级，用'>'，'<'，'='表示  
            {
            case '<':               //<则将c入栈opter  
                opter.push(c);
                c = getchar();
                break;
            case '=':               //=将opter栈顶元素弹出，用于括号的处理  
                opter.pop();
                c = getchar();
                break;
            case '>':               //>则计算  
                char theta = opter.top();
                opter.pop();
                double a = opval.top();
                opval.pop();
                double b = opval.top();
                opval.pop();
                opval.push(calculate(b, theta, a));//计算栈出的b，theta和a
            }
        }
    }
    return opval.top();   //返回opval栈顶元素的值  
}

四，计算b，theta和a

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double calculate(double b, char theta, double a)   //计算b theta a  
{
    switch (theta)
    {
    case '+':
        return b + a;
    case '-':
        return b - a;
    case '*':
        return b * a;
    case '/':
        return b / a;
    default:
        break;
    }
}

五，获取theta所对应的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int getIndex(char theta)   //获取theta所对应的索引  
{
    int index = 0;
    switch (theta)
    {
    case '+':
        index = 0;
        break;
    case '-':
        index = 1;
        break;
    case '*':
        index = 2;
        break;
    case '/':
        index = 3;
        break;
    case '(':
        index = 4;
        break;
    case ')':
        index = 5;
        break;
    case '#':
        index = 6;
    default:break;
    }
    return index;
}

六，主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>     
#include<cstdio>  
#include<cctype>  
#include<stack>  
using namespace std;

stack<char> opter;    //运算符栈  
stack<double> opval;  //操作数栈  

int main();
{
    //freopen("test.txt", "r", stdin);  
    int t;     // 需要计算的表达式的个数  
    cin >> t;
    getchar();
    while (t--)
    {
        while (!opter.empty())opter.pop();
        while (!opval.empty())opval.pop();
        double ans = getAnswer();
        cout << ans << endl << endl;
        getchar();
    }
    return 0;
}

 

示例

输入

1
2
6
2+3*4*(5-2)+6#

RUyUq.png

输出

RUPNG.png

 

输入（多位数）

1
2
6
23*(2+5)+62/3#

RURE1.png

输出

RUDFD.png