2019-03-21 21:36:13 salmon_zhang 阅读数 677
  • 数据结构基础系列(3):和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

栈是一种数据结构,今天我们先来理解下栈的定义,然后再看几个在现实开发中运用到的实例。

1. 什么是栈?

栈是一个具有“先进后出、后进先出”这种特点的数据结构。

从栈的结构图中可以看出,栈是一种“操作受限”的线性表,只允许在一端插入或删除数据。

从功能上来说,数组或链表可以替代栈,但特定的数据结构是对应特定场景的抽象。当某个数据集合只涉及在一端插入和删除数据,并且满足先进后出、后进先出的特性时,这时候我们就可以选择栈这种数据结构。

2. 如何实现一个栈?

从上面栈的结构图中可以看到栈主要包含了两个操作:入栈和出栈。即在栈顶插入一个数据或删除一个数据。理解栈的定义后,我们就可以实现一个栈了。

数组和链表都可以用来实现栈。用数组实现的栈叫作“顺序栈”,用链表实现的栈叫作“链式栈”。

下面我分别用数组和链表来实现一个栈。

基于数组实现的顺序栈

public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组,申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了,直接返回 false,入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置,并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

基于链表实现的链式栈

public class StackBasedLinkedList {
  private Node top = null;

  public void push(int value) {
    Node newNode = new Node(value, null);
    // 判断是否栈空
    if (top == null) {
      top = newNode;
    } else {
      newNode.next = top;
      top = newNode;
    }
  }

  /**
   * 用-1表示栈中没有数据。
   */
  public int pop() {
    if (top == null) return -1;
    int value = top.data;
    top = top.next;
    return value;
  }

  public void printAll() {
    Node p = top;
    while (p != null) {
      System.out.print(p.data + " ");
      p = p.next;
    }
    System.out.println();
  }

  private static class Node {
    private int data;
    private Node next;

    public Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }

    public int getData() {
      return data;
    }
  }
}

其实,不管是顺序栈还是链式栈,存储数据都只需要一个大小为n的数组就够了,在入栈和出栈的时候也只需要一两个临时变量存储空间,因此空间复杂度是O(1)。

注意,这里存储数据需要一个大小为n的数组,并不是说空间复杂度就是O(n)。因为这n个空间是必须的,无法去掉。我们所说的空间复杂度,是指除了原本的数据存储空间外,算法运行时还需要额外的存储空间。

在顺序栈或链式栈中,入栈或出栈都只是操作栈顶个别数据,所以时间复杂度都是O(1)。

3. 实现一个支持动态扩容的顺序栈

上面实现的顺序栈是一个大小固定的栈,在初始化栈时就指定了栈的大小。在栈满后,就无法再往栈里添加数据。尽管链式栈的大小不受限,但要存储next指针,需要消耗的内存较多。那么如何基于数组实现一个可以支持动态扩容的栈呢?

在前面学习数组的时候,我们知道当数组空间不够时,我们就要重新去申请一块更大的内存,将原来的数据拷贝过去,这样就实现了一个支持动态扩容的数组。

同理,当我们要实现一个支持动态扩容的栈时,只需要在底层依赖一个支持动态扩容的数组就行了。当栈满后,我们就去申请一个更大的数组,将原来的数据拷贝到新数组中。

我们可以参考下面的图去理解:

其实,在实际开发过程中,我们很少用到支持动态扩容的顺序栈。这里我们着重分析下它的复杂度。

出栈时间复杂度

在出栈操作中,没有内存重新申请和数据移动,所以出栈的时间复杂度是O(1)。

入栈时间复杂度

在入栈时就要分情况讨论:

  • 当栈中有空闲空间时,此时入栈的时间复杂度是O(1)

  • 当栈中的内存空间不够时,就需要重新申请内存和数据搬移,此时入栈的时间复杂度是O(n)

通过上面的分析,入栈时最好情况时间复杂度是O(1),最坏情况时间复杂度是O(n)。

平均情况时间复杂度

这里我们用摊还分析法分析下它的平均情况时间复杂度。为了分析的方便,我们需要事先做一些假设和定义:

  • 栈空间不够时,重新申请一个原来两倍大小的数组

  • 为了简化分析,假设只有入栈操作没有出栈操作

  • 定义不涉及内存重新申请的入栈操作为simple-push操作,时间复杂度为O(1)

如果当前栈大小为k,并且已满,那么当有数据再入栈时,就需要先申请2倍大小的内存,并且做k个数据迁移的操作,然后再入栈。但后续的k-1次入栈都不需要重新申请内存和数据迁移,所以后续的k-1次入栈操作就只需要简单的simple-push操作。

这里就很符合均摊分析法的特点:在每一次O(n)操作后,就会紧跟n-1个O(1)操作。这样我们就可以将耗时多的操作均摊到n-1次耗时少的操作上。

为了方便理解,插入一张图:

从上面的图中可以看出,k次入栈操作,总共涉及k个数据的迁移,以及k次simple-push操作。将k个数据迁移均摊到k次入栈操作,那么每个入栈操作只需要一个数据迁移和一个simple-push操作,以此类推,入栈操作的均摊时间复杂度就是O(1)。

这里也证明了我在《复杂度分析》中的结论:均摊时间复杂度一般都等于最好情况时间复杂度。

因为在大部分情况下,入栈操作的时间复杂度都是O(1),只有在个别情况下是O(n),我们就可以把耗时多的入栈操作的时间均摊到其他入栈操作时间少上,所以平均情况下的时间复杂度就是O(1)。

4. 函数调用中的栈

操作系统会给每个线程分配一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回后,就会将这个函数对应的栈帧出栈。

结合代码来分析:

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

在上面的代码片段中,main()函数调用了add()函数,获取计算结果,并与临时变量a相加,最后打印res的值。

为了更清晰的看到这个过程对应的函数栈,画了一张图,图中显示的是在执行到add()函数时,函数调用栈的情况:

5. 内存中的堆栈与数据结构堆栈的区别

内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。

内存空间在逻辑上分为三部分:

  • 代码区

  • 静态数据区

  • 动态数据区(又分为栈区和堆区)

代码区:

存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换。

静态数据区:

存储全局变量、静态变量、常量。常量包括final修饰的常量和String常量。系统自动分配和回收。

栈区:

存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。

堆区:

new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据。

6. 为什么用栈来保存临时变量?

其实,也不一定要用栈来保存临时变量,只不过如果这个函数调用符合“后进先出”的特性,就会立马想到用栈这种数据结构来实现。

从调用函数进入到被调用函数,对于数据来说,变化的是作用域。所以在根本上只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好就回到调用函数的作用域内。

7. 栈在表达式求值中的应用

实际上,编译器就是通过两个栈来实现表达式求值的。其中一个保存操作数的栈,另一个保存运算符的栈。从左向右遍历表达式,当遇到数值的时候,就直接压入操作数的栈;当遇到运算符,就与运算符栈的栈顶元素进行比较:

  • 如果比运算符栈顶元素的优先级高,就将当前运算符压入栈

  • 如果比运算符栈顶元素优先级低或者相同,就从运算符栈中取出栈顶运算符,从操作数栈的栈顶取2个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。

为了方便理解,我画了一个3+5*8-6表达式的计算过程图:

8. 栈在括号匹配中的应用

栈不仅可以用来实现表达式求值,还可以来检查表达式中的括号是否匹配。

假设表达式中只包含三种括号,圆括号()、方括号[]和花括号{},它们之间可以任意嵌套。我们规定{[{}]}、[{()}([])]为合法格式,而{[}()]、[({)]为不合法格式。

那么我们就可以用栈来检查表达式是否合法。

用栈来保存未匹配的左括号,从左到右依次扫描字符串:

  • 当扫描到左括号时,则将其直接压入栈中

  • 当扫描到右括号时,从栈顶取出一个左括号

如果能匹配,比如“(”跟“)”匹配,则继续扫描剩下的字符串;如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。

当所有的括号都扫描完成后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。

9. 浏览器的前进、后退功能

我们可以用两个栈就可以实现浏览器的前进、后退功能。

使用两个栈,X和Y,我们把首次浏览的页面依次压入栈X,

  • 当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据依次放入栈Y。

  • 当点击前进按钮时,依次从Y中取出数据,放入X栈中。

  • 当栈X中没有数据时,则说明没有页面可以继续后退浏览。

  • 当栈Y中没有数据时,则说明没有页面可以继续前进浏览。

例如依次顺序查看了a、b、c三个页面,我们就依次把a、b、c压入X栈,这个时候X栈和Y栈的数据如下:

当我们通过浏览器的后退按钮,从页面c后退到页面a之后,我们就依次把c、b从栈X中弹出,并依次放入Y栈中,这时候X栈和Y栈的数据如下:

如果你又想看页面b,可以通过点击前进按钮回到b页面,我们就把b再从栈Y中出栈,放入到栈X中,这时候X栈和Y栈的数据如下:

如果这时候通过页面b又跳转到了新的页面d,这时页面c就无法再通过前进、后退按钮重复查看了,所以就需要清空栈Y,这时候X栈和Y栈的数据如下:

非常感谢您的耐心阅读,希望我的文章对您有帮助。欢迎点评、转发或分享给您的朋友或技术群。
2019-10-06 14:59:52 arttnba3 阅读数 62
  • 数据结构基础系列(3):和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

绪论

今天我们要讲的栈其实和先前的链表就某种程度而言本质上是相通的,所以便不再精讲了(其实是因为懒)

在写下这篇博文之前,我的C++其实一直都是连入门的边缘都碰不到的级别,所以很多用的都还是C的语法和思维,为此还因为写错代码而被大佬们批判了一番…

基本概念:栈(Stack)

系统里的栈

在计算机系统中,栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中,也可以将数据从栈顶弹出。在i386机器中,栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小,弹出的操作使得栈顶的地址增大。
(百度百科:栈)

嗯,大概就是这样(明白脸)

其实我们今天的重点是数据结构当中的栈啦!

数据结构中的栈

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈(Stack)是限制插入和删除只能在一个位置上进行的表,我们将该操作位置称为栈的(Top),我们有关栈的所有操作都要从这里开始

栈ADT有两种基本操作,一种是进栈Push),一种是出栈Pop),顾名思义,进栈就是将一个新的数据压入栈中使之成为新的栈顶,出栈则是将栈顶的数据(最后插入的元素)删除

由于栈的特殊操作模式,栈有的时候又被称为后进先出表LIFO

对一个空栈进行Push或Pop操作一般被认为是栈ADT的错误,但是当Push时空间用尽则是一个实现错误而并非ADT错误

栈的模式图如下,如图所示,只有顶部元素是可以直接访问的:

在这里插入图片描述
(图片来自百度百科)

栈的实现

常见的栈的实现方式有两种:结构体实现和数组实现,前一种是一般情况下比较通用的实现方式,后一种则是在OI当中用的更多

利用基于单链表的ADT接口实现栈

单链表的构造很适合我们用来实现栈,我们可以通过在表的顶端插入来实现Pop,通过删除表的顶端元素实现Push,这样一个简单的栈的模型就构建出来了

我们依然选择用上一篇的老办法,三步走战略。

要注意在C++当中不能直接使用malloc分配类的内存,最好是使用operator new(虽然说本质上还是在使用malloc…这个就不属于本篇讨论的范围了)

一、建立抽象

栈的基本属性便是一个能储存多项数据、数据的增添与删除只能在一个位置的表,这个位置为栈的顶

栈的基本操作只有Pop和Push两种,为了使程序更加人性化,我们照例增添一些功能性操作函数,那么我们所需要实现的其实便只有这七个功能:

1、初始化一个非空栈
2、确定栈当中的项数
3、在栈顶使一个新项入栈
4、在栈顶使一个项出栈
5、检查栈是否为空栈
6、删除一整个栈
7、检索栈顶元素

函数声明如下:

bool IsEmpty(Stack * pStack);
Stack* MakeStack(string _Name,ElementType* sData,int dType);
bool PopStack(Stack ** pTop);
bool PushStack(string sName,ElementType* sData,int dType, Stack ** pTop);
bool ClearStack(Stack ** pTop);
int CheckStack(Stack * pTop);
int DataType(Stack *pStack);
ElementType* DataValue(Stack *pStack);

二、建立接口

为了增强栈的通用性(其实只是闲着无聊),我们选择使用一个共用体(即union,在CPP当中被翻译为联合)来定义栈中元素储存的数据

在创建栈时,通过预先定义好的接口中的数据类型码,我们可以很好的确定要读入的数据类型,以使用共用体不同的成员读入数据

typedef union elementtype{
	short int s_int;//0
	unsigned short int us_int;//1
	int _int;//2
	unsigned u_int;//3
	long long int ll_int;//4
	unsigned long long int ull_int;//5
	float _float;//6
	double _double;//7
	char _char;	//8
	char _string[20];//9
}ElementType;

在我们学会了写链表的情况下,栈ADT链表实现的类型声明也就不难写了:

typedef struct stack{
	ElementType sElement;
	string StackName;
	struct stack *sNext;
	int tData;
}Stack;

我们同样选择将接口定义与功能函数其放置于外部文件当中,下文便不再说明

三、实现栈模型

1、初始化一个非空栈

在C++当中使用new操作符可以很方便快捷的分配栈当中元素的内存空间,这样我们便可以很方便的使用string类来命名栈中元素

需要注意的是,我们使用了一个共同体作为栈元素当中的数据,因而我们在读入数据时需要注意读入的数据类型,因此我们的函数的参数当中新增了一个整型作为“类型码”,读入的数据也变成了共同体指针:

Stack* MakeStack(string _Name,ElementType* sData,int dType)
{
	Stack *pStack= new Stack;
	pStack->StackName=_Name;
	pStack->sNext=NULL;
	pStack->tData=dType;
	switch(dType)
	{
		case 0:
				pStack->sElement.s_int=sData->s_int;
				break;
		case 1:
				pStack->sElement.us_int=sData->us_int;
				break;
		case 2:
				pStack->sElement._int=sData->_int;
				break;
		case 3:
				pStack->sElement.u_int=sData->u_int;
				break;
		case 4:
				pStack->sElement.ll_int=sData->ll_int;
				break;
		case 5:
				pStack->sElement.ull_int=sData->ull_int;
				break;
		case 6:
				pStack->sElement._float=sData->_float;
				break;
		case 7:
				pStack->sElement._double=sData->_double;
				break;
		case 8:
				pStack->sElement._char=sData->_char;
				break;
		case 9:
				strcpy(pStack->sElement._string,sData->_string);
				break;
		default:
				delete (pStack);
				return NULL;//用户给了错误的输入
	}
	return pStack;
}

2、确定栈当中的项数

我们只需要使用递归一层一层的检索便可以很轻松地得到栈当中的项数:

int CheckStack(Stack * pTop)
{
	if(pTop!=NULL)
		return CheckStack(pTop->sNext)+1;
	return 1;
}

3、在栈顶使一个新项入栈

由于我们的函数声明与定义都在外部文件当中,因此要对其他文件中的栈进行操作,我们依然需要使用二级指针进行操作

入栈操作本质上和新建非空栈的原理并无不同,这里便不再多做解释,需要注意的是莫要忘了将新的栈顶内的指针指向其下一层的元素:

bool PushStack(string sName,ElementType* sData,int dType, Stack ** pTop)
{
	Stack *pStack=new Stack;
	if(pStack==NULL)
		return false;
	pStack->StackName=sName;
	pStack->sNext=*pTop;
	pStack->tData=dType;
	switch(dType)
	{
		case 0:
				pStack->sElement.s_int=sData->s_int;
				break;
		case 1:
				pStack->sElement.us_int=sData->us_int;
				break;
		case 2:
				pStack->sElement._int=sData->_int;
				break;
		case 3:
				pStack->sElement.u_int=sData->u_int;
				break;
		case 4:
				pStack->sElement.ll_int=sData->ll_int;
				break;
		case 5:
				pStack->sElement.ull_int=sData->ull_int;
				break;
		case 6:
				pStack->sElement._float=sData->_float;
				break;
		case 7:
				pStack->sElement._double=sData->_double;
				break;
		case 8:
				pStack->sElement._char=sData->_char;
				break;
		case 9:
				strcpy(pStack->sElement._string,sData->_string);
				break;
		default:
				delete (pStack);
				return false;
	}
	*pTop=pStack;
	return true;
}

4、在栈顶使一个项出栈

我们使用new操作符分配到内存可以很方便的使用delete进行释放,这里类比此前我们写链表时用的方法即可,需要注意的是要记得将指向原栈顶的指针指向新的栈顶:

bool PopStack(Stack **pTop)
{
	if(pTop==NULL)
		return false;//不能删除空栈
	Stack *temp=*pTop;
	*pTop=(*pTop)->sNext;//栈顶变更
	delete (temp);
	return true;
}

5、检查栈是否为空栈

我们定义值为NULL的指针指向的是空栈:

bool IsEmpty(Stack * pStack)
{
	return pStack==NULL;
}

6、删除一整个栈

实现这个功能只需要使用递归一层一层的Pop到栈底就可以了,不再过多解释,上代码:

bool ClearStack(Stack ** pTop)
{
	if(*pTop!=NULL)
		ClearStack(&((*pTop)->sNext));
	else 
		return false;//没法删除空栈
	delete (*pTop);
	return true;
}

7、检索栈顶元素

我们选择使用两个函数,一个返回栈顶元素类型码,一个返回指向栈顶元素的共同体的指针

PS:其实这种写法是吃饱了撑的

int DataType(Stack * pStack)
{
	if(pStack==NULL)
		return -1;
	return pStack->tData;
}

ElementType* DataValue(Stack * pStack)
{
	if(pStack==NULL)
		return NULL;
	return &(pStack->sElement);
}

利用数组实现栈

由于栈的结构与操作上的特殊性,利用数组来实现栈方便快捷,基本上已经成为了OI当中首选实现栈的方式

我们只需要预先定义一个长度足够的数组,再定义一个用来表示栈顶位置的整型变量即可实现一个基础的栈ADT

需要注意的是,这样的栈虽然好写,但是这样建立的栈的容量是固定的,元素种类也是固定的,通用性并不高,也不适用于更大的编程项目

不过,如果我们有着良好的编程原则,对于小的程序而言,使用者其实不需要太过于在意实现形式

那么数组栈该怎么写就不需要我多说了⑧

咕咕咕了,以后有时间再补上

栈的简单应用

计算后缀表达式

描述
逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值,其中运算符包括+ - * /四个。
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。
可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
提示
可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解。
来源
计算概论05

(Noi.OpenJudge.cn:1696:逆波兰表达式)

咕咕咕…

中缀表达式的转换

描述
人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。
给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。
输入
第一行为测试数据的组数N
接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。
输出
对每一组测试数据输出一行,为表达式的值
样例输入
3
3+5*8
(3+5)8
(23+34
45/(5+6+7))
样例输出
43
64
108
提示
注意:运算过程均为整数运算(除法运算’/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。
中间计算结果可能为负。
(OpenJudge程序设计入门与进阶:10:中缀表达式的值)

咕咕咕…

2017-07-26 22:59:48 ShannonNansen 阅读数 803
  • 数据结构基础系列(3):和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

  本文内容是数据结构第二弹——栈及其应用。首先会介绍栈的基本结构和基本操作以及代码实现,文后会讲解几个栈的典型应用。栈是一个比较简单但是用途及其广泛的重要的数据结构,所以对于栈的学习重在理解应用而非实现。在今后的学习中可能会遇到各种依赖栈实现的算法或数据结构,一般那种情况下不需要我们自己实现栈,费时费力,一般直接使用C++ STL内置的stack泛型容器,方便快捷。这里讲解栈主要是针对入门的小伙伴~(ps:下面的栈的实现也均使用泛型)

一、栈的定义及实现

  首先,阐述一下栈的定义。

  定义:栈是限定仅在表头进行插入和删除操作的线性表。要搞清楚这个概念,首先要明白”栈“原来的意思,如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。

  栈也是一种线性表,只不过栈比较特殊,它的运算和操作受限,不同于链表,栈的元素插入和删除仅限于在其一端进行操作。

  也就是说,栈这个容器,只能操作当前的首元素,其他元素不可见也不可访问更不可更改。

  我们假想栈是一个顶端开口底部封闭的“容器”,我们只能从栈顶“加入物品”,也只能从栈顶“取出物品”,如下图,为了方便展示与理解,我们把线性表“竖着画”:


  可见,栈有先进后出或后进先出的特点。

  栈的基本运算有以下几种:

(1) 入栈:Push

(2) 出栈:Pop

(3) 取栈顶:Top

(4) 获取大小:Size

(5) 栈是否空:Empty

  下面依次介绍这几种运算的原理及实现。

  首先需要说的是,栈是一种线性表,所以也会有顺序栈和链式栈,所谓顺序栈,与顺序表类似,就是使用数组来实现栈的相关功能,不过这种方法局限性大,且耗费内存,所以在此不推荐使用,以下所有实现均采用链式结构。

  与链表类似,我们首先定义出栈元素结点的结构,同样含有一个值域和一个指针域,如下图所示,粉色框框圈起来的是栈内元素:


  结点代码如下:

template<class T>
struct Node
{
	T data;
	Node<T> *next;
};

  接下来我们开始抽象出栈的类结构,我们把栈想象成一条链表,只不过这条链表只能从头部插入元素,只能从头部获取元素,也只能从头部删除元素,这个头部,就是我们栈的栈顶。是不是感觉这其实就是一个操作受限制的链表?而且是逆序建立链表?而且没有需要特殊处理的尾指针?对,就是这样,瞬间就变得简单了。

  我们对栈的类定义如下:

template<class T>
class Stack
{
private:
	Node<T> *head;
	int cnt;
public:
	Stack()
	{
		head = new Node<T>;
		head->next = NULL;
		cnt = 0;
	}
	void push(T elem); // 将elem元素入栈
	void pop(); // 删除栈顶元素
	T top(); // 获取栈顶元素值
	int size(); // 获取栈内元素数量
	bool empty(); // 判断是否为空栈
};
  可以看出,相比较链表,我们的栈操作还是很少的,所以实现起来也很简单,但就是这样简单的一个数据结构,却有着极为广泛的应用。下面的讲解均无图,详情参考单链表的相关知识,传送门>>

1. 入栈操作(push)

  与链表头部插入一样,首先需要实例化一个新的结点,并给该节点赋初值,使指针p指向该节点,然后通过一下几步:

  ① 将p指针域指向栈顶结点(首元素),p->next = head->next;

  ② 将head指针域指向p,head->next=p;

  ③ 计数器+1

  代码如下:

template<class T>
void Stack<T>::push(T elem) // 将elem元素入栈
{
    Node<T> *p = new Node<T>;
    p->data = elem;
    p->next = head->next;
    head->next = p;
    cnt++;
}
  可以看出,栈的入栈实现还是很简单的,与单链表的push_front()是一样的,而且还不用注意尾指针的特殊情况。

2. 出栈操作(pop)

  同样,这里的出栈操作其实就是删除栈顶元素,放在单链表里说就是删除首元素,同样是与单链表类似,我们先要获取待删元素的前置结点,也就是head结点(这个好像压根不用获取……),然后使指针p指向head结点的下一结点,执行下列步骤:

  ① 若p为NULL,则说明栈内没有元素,直接返回;否则将head的指针域指向p->next。

  ② 释放p指向的结点的内存,即delete p;

  ③ 计数器-1

  需要注意的是,如果p为NULL,说明栈空,此时请求pop操作是非法的,可以根据实际情况抛出异常或者返回特殊值,这里方法直接返回。

  代码如下:

template<class T>
void Stack<T>::pop() // 删除栈顶元素
{
    Node<T> *p = head->next;
    if(p == NULL)
    {
        return;
    }
    head->next = p->next;
    delete p;
    cnt--;
}

3. 获取栈顶元素(top)

  这里直接使用一个p指针指向head->next,如果不为空,则返回p的数据域即可 ;p为NULL的话,说明栈内无元素,此时请求top操作实际上是非法的,可以根据自身情况抛出异常或者返回特殊值。这里采用了返回一个实例化的对象,也就是默认值,代码如下:

template<class T>
T Stack<T>::top() // 获取栈顶元素值
{
    Node<T> *p = head->next;
    if(p == NULL) // 如果栈内没有元素,则返回一个新T类型默认值
    {
        return *(new T);
    }
    return p->data;
}

4. 获取栈的大小(size)

  直接返回内部计数器即可,代码:
template<class T>
int Stack<T>::size() // 获取栈内元素数量
{
    return cnt;
}

5. 判断栈是否为空(empty)

  此方法经常在循环操作栈的时候用作条件,如果栈空则返回true,非空返回false。代码如下 :

template<class T>
bool Stack<T>::empty() // 判断是否为空栈
{
    return (cnt == 0);
}

**下面是完整的代码以及简短测试用例:

#include <bits/stdc++.h>

using namespace std;

template<class T>
struct Node
{
	T data;
	Node<T> *next;
};

template<class T>
class Stack
{
private:
	Node<T> *head;
	int cnt;
public:
	Stack()
	{
		head = new Node<T>;
		head->next = NULL;
		cnt = 0;
	}
	void push(T elem); // 将elem元素入栈
	void pop(); // 删除栈顶元素
	T top(); // 获取栈顶元素值
	int size(); // 获取栈内元素数量
	bool empty(); // 判断是否为空栈
};

template<class T>
void Stack<T>::push(T elem) // 将elem元素入栈
{
    Node<T> *p = new Node<T>;
    p->data = elem;
    p->next = head->next;
    head->next = p;
    cnt++;
}
template<class T>
void Stack<T>::pop() // 删除栈顶元素
{
    Node<T> *p = head->next;
    if(p == NULL)
    {
        return;
    }
    head->next = p->next;
    delete p;
    cnt--;
}
template<class T>
T Stack<T>::top() // 获取栈顶元素值
{
    Node<T> *p = head->next;
    if(p == NULL) // 如果栈内没有元素,则返回一个新T类型默认值
    {
        return *(new T);
    }
    return p->data;
}
template<class T>
int Stack<T>::size() // 获取栈内元素数量
{
    return cnt;
}
template<class T>
bool Stack<T>::empty() // 判断是否为空栈
{
    return (cnt == 0);
}

int main()
{
    Stack<int> st;
    st.push(1);
    printf("Top: %d, Size: %d\n", st.top(), st.size());
    st.push(2);
    st.push(666);
    printf("Top: %d, Size: %d\n", st.top(), st.size());
    st.pop();
    printf("Top: %d, Size: %d\n", st.top(), st.size());
    st.pop();
    st.pop();
    printf("Top: %d, Size: %d\n", st.top(), st.size()); // 这里栈空,top()会返回一个随机值

    return 0;
}

  附个练习,可以用来练习一下栈的基本操作,传送门来了:

  SDUT OJ 3335 数据结构实验之栈八:栈的基本操作

二、栈的典型应用

  这里是栈的应用,所以需要用到栈的地方我直接使用C++ STL的stack,因为如果我每次都引用我自己写的泛型栈的话,代码太长了……大家可以根据自己的实际情况选择怎么写,编程这个东西,要的就是灵活。

1. 进制转换

  进制转换是栈的一个很典型的应用,我们通常说的使用栈解决进制转换问题是指的十进制转换成N进制,因为N进制转十进制根本不需要什么辅助手段,直接一个式子算出来就好……

  关于进制转换的数学求法,就不过多赘述了,我记得高中数学好像学过,就是对于十进制整数X,求其N进制表示,使X不断地对N取余数、整除N,如此循环直至X变为0,则所有余数值的逆序序列即为转换后的N进制数。如我们要将十进制数2017转换成八进制,计算过程如图所示:


  红色为每步计算的余数,最后余数倒置即为结果。

  所以我们的栈就派上了用场,前面介绍栈的特点是“先进后出”或“后进先出”,也就是说,如果一个序列顺序入栈,再全部顺序出栈,则出栈后的序列与出栈前恰好相反,所以恰好可以用来实现序列逆置。

  假设这样一个题目:输入两个数X和N,空格间隔,X代表一个十进制正整数,N表示要转换的进制(2<=N<=16),超过10进制的基数用大写ABCDEF表示。求X的N进制表示。

  这里我们需要注意的是,超过十进制的基数,也就是说,如果N大于10,那么栈内极有可能有大于等于10的数存在,这时候我们不能原样输出,而是要转换成字母来表示超过9的基础,毕竟数字只有10个,16进制不够用啊QAQ!

  我们提前定义好各基数就好,代码如下:

#include<bits/stdc++.h>

using namespace std;

// 按下标定义余数的输出字符
const char rep[] = "0123456789ABCDEF"; 

int main()
{
    int n,x;
    while(~scanf("%d %d", &x, &n))
    {
        stack<int> st;
        while(x)
        {
            st.push(x % n); // 余数入栈
            x /= n; // 整除
        }
        while(!st.empty())
        {
            int tp = st.top();
            st.pop();
            putchar(rep[tp]); // 按照对应的样式输出余数
        }
        puts("");
    }

    return 0;
}

  这就是栈的一个基本应用——进制转换,实际上就是把一个序列倒序输出,很好地利用了栈的特点。下面给几个练习题传送门:

  SDUT OJ 1252 进制转换

  SDUT OJ 2131 数据结构实验之栈一:进制转换

2. 行编辑器

  我们日常编辑文本文件的时候,一定都会使用退格键,用于删除光标左端的字符,在行编辑器问题上,光标始终在行最右端,不存在移动光标的问题。我们现在引入问题,假设一个简单的行编辑器,用户可以键入字符,也可以敲击退格键删除光标左边的一个字符,也可以敲击删除键来删除整行字符。现在我们把用户键入的按键(注意是按键)转换成一串按键序列,比如abcde#haha##66@qaq代表用户的键入序列,从左至右依次为用户按下的键,“#”代表退格键,删除一个字符;“@”代表删除键,删除整行字符,其它的都代表一个正常的可见字符,现在给定你一串用户的按键序列,让你输出屏幕上最终的字符串(假设输入的字符不包含空格)。

  分析这种需求,行编辑器光标始终在右边,输入一个字符就相当于在最右端添加一个字符,删除一个字符也是从最右端删除,删除行则是从右端开始删除所有字符,这正好与栈的运算模式契合,所以使用栈是最好的解决办法。

  实现上,从左向右扫描键入序列,如果是“#”,则弹出栈顶元素(需要注意的是,如果栈空,则这个“#”为非法操作,应该直接忽略),“@”则循环弹出栈顶元素直至栈为空,其他情况直接将该字符入栈 。最后将栈内元素依次弹出(此时得到的序列是逆序的,所以需再次逆置,可以再用一个栈辅助逆置),代码如下:

#include<bits/stdc++.h>

using namespace std;

char line[1010];

int main()
{
    while(~scanf("%s", line))
    {
        stack<char> st;
        for(int i = 0 ; line[i] ; i++)
        {
            if(line[i] == '#')
            {
                if(!st.empty()) // 非空才删除
                    st.pop();
            }
            else if(line[i] == '@')
            {
                while(!st.empty()) // 循环删除全部元素
                    st.pop();
            }
            else
            {
                st.push(line[i]);
            }
        }
        stack<char> tmp; // 由于出栈结果是倒置的,所以需要使用另一个栈将结果再次倒置
        while(!st.empty())
        {
            tmp.push(st.top());
            st.pop();
        }
        while(!tmp.empty())
        {
            putchar(tmp.top());
            tmp.pop();
        }
        puts("");
    }

    return 0;
}

  同样,附上练习题传送门:

  SDUT OJ 1479 数据结构实验之栈:行编辑器

3. 表达式转换及求值

  这里涉及到两点,一点是表达式转换,另一点是表达式求值,下面分别介绍

 (1) 表达式转换

  我们日常算术中使用的表达式是中缀式,通常是符号位于操作数中间,这种表达方式需要考虑算符的优先级问题,所以引入括号来强行更改算术优先级。这种中缀式适合人脑计算,比较符合人类的运算习惯,但是对计算机却很不友好,解析难度较大,所以引入了前缀式和后缀式,这两种表达式均没有括号,且无优先级限制,只需要按照书写顺序进行计算即可,不同于中缀式,后缀式只需要使用一个栈进行相关操作即可,而中缀式需要两个栈,一个存符号,一个存操作数。

  下面分析一个表达式转换问题。

  我们要做的是将一个中缀表达式转换成后缀表达式(前缀我们暂不考虑,与后缀大同小异),中缀表达式里包含+-*/和括号。

  下面给出转换方法:

  ① 首先构造一个符号栈,此栈的特点是要求遵循栈内元素自底向上优先级严格递增原则,也就是说,上面的元素优先级必须大于下面的元素优先级(前缀式是大于等于,这点区别一定要记清楚)。

  ② 从左向右扫描表达式(前缀式从右向左),逐步判断:

a) 如果遇到运算数,则直接输出

b) 如果是运算符,则比较优先级,如果当前运算符优先级大于栈顶运算符优先级(栈空或栈顶为括号时,直接入栈 ),则将运算符入栈;否则弹出并输出栈顶运算符,直至满足当前运算符大于栈顶运算符优先级(或者栈变空、栈顶为括号)为止,然后再将当前运算符入栈。

c) 如果是括号,则特殊处理。左括号的话,直接入栈;右括号的话,则不断弹出并输出栈顶符号,直到栈顶符号是左括号,然后弹出栈顶左括号(不输出,因为后缀式没有括号),并忽略当前右括号,继续扫描。

d) 由以上步骤可知,括号具有特殊的优先级,左括号在栈外的时候,是最高的优先级,在栈内有最低优先级。

  ③ 重复上述步骤,直到表达式扫描结束,此时若栈内有剩余符号,则将符号依次出栈并输出。

  例如:将a*b+(c-d/e)*f转换成后缀表达式,分解步骤如下:


  上表即为表达式转换的分解步骤,利用了栈的特性完成转换,转换后的后缀表达式不需要考虑算符优先级,只要按照符号出现的顺序进行计算即可,下一小节就会讲利用栈求后缀式的计算结果值。

  中缀式转后缀式代码如下(简化版,假设运算数是小写字母,运算符只有四则运算和括号):

#include<bits/stdc++.h>

using namespace std;

char line[1010]; // 输入的中缀式
char res[1010]; // 保存结果
int level[128]; // 定义运算符的优先级

// 比较两运算符优先级,如果a>b返回true,否则false
bool operatorCmp(char a, char b)
{
    return level[(int)a] > level[(int)b];
}

int main()
{
    // 初始化定义运算符优先级
    level['+'] = level['-'] = 1;
    level['*'] = level['/'] = 2;
    while(~scanf("%s", line))
    {
        stack<char> st;
        int ptr = 0; // 初始化结果字符串指针
        for(int i = 0 ; line[i] ; i++)
        {
            if(isalpha(line[i])) // 如果是字母
            {
                res[ptr++] = line[i]; // 暂存到结果字符数组
            }
            else // 否则,运算符或括号
            {
                // 可以直接入栈的情况:栈空、栈顶括号、当前是括号
                // 认真思考一下这个短路条件的内涵
                if(st.empty() || st.top() == '(' || line[i] == '(')
                {
                    st.push(line[i]);
                }
                else if(line[i] == ')') // 右括号,弹出栈内符号直至遇到左括号
                {
                    // 这里也有一个短路条件,如果弹出过程遇到栈空,说明括号不匹配,应该报错
                    while(!st.empty() && st.top() != '(')
                    {
                        res[ptr++] = st.top();
                        st.pop();
                    }
                    // 弹出左括号
                    if(!st.empty())
                        st.pop();
                }
                else
                {
                    // 遇到符号,如果栈非空且当前符号小于等于栈顶符号,则一直弹出并输出栈顶符号
                    while(!st.empty() && !operatorCmp(line[i], st.top()))
                    {
                        res[ptr++] = st.top();
                        st.pop();
                    }
                    // 循环结束,可以入栈了
                    st.push(line[i]);
                }
            }
        }
        // 扫描结束,依次弹出并输出栈内剩余元素
        while(!st.empty())
        {
            res[ptr++] = st.top();
            st.pop();
        }
        // 为结果字符串添加结束标志'\0'
        res[ptr] = 0;
        // 打印转换结果
        puts(res);
    }

    return 0;
}

  同样附上练习题,传送门:

  SDUT OJ 2132 数据结构实验之栈二:一般算术表达式转换成后缀式(此题与上面例子很像,但是有细节差异哦)

  SDUT OJ 2484 算术表达式的转换(此题要求前缀,与后缀类似,相信你可以触类旁通~)

 (2) 后缀表达式计算

  前面说到,后缀式很适合计算机识别,所以后缀式求值只需要利用一个栈即可快速求值。而且实现起来也很简单。

  由于后缀式不存在优先级,所以计算起来也没那么麻烦,下面给出计算步骤。

  步骤如下:

  ① 构造一个操作数栈,用于存放操作数。

  ② 从左向右扫描后缀式,如果遇到操作数,则将操作数入栈;

  ③ 如果遇到运算符,根据运算符需要的运算数的个数,从栈中取出对应个数的操作数,先出栈的作为操作数,后出栈的为操作数,计算出结果后,将计算结果入栈。

  ④ 扫描结束后,如果后缀式合法,则过程中不会产生错误且最终栈内一定有且仅有一个元素,输出栈顶元素即为最终结果。

  我们以后缀式59*684/-3*+为例,这里的操作数均为个位数(前面不是59而是5和9),当然有更复杂的后缀式,比如多位数,这里不研究。

  解析如下:


  利用一个数栈,即可完成后缀表达式的计算,且不用考虑优先级,需要注意的是不遵循交换律的运算(-和/)要注意左右操作数,先出栈的为右操作数

  上例后缀式求值代码如下:

#include<bits/stdc++.h>

using namespace std;

char line[1010];

int calc(int a, int b, char op)
{
    if(op == '+')
        return a + b;
    else if(op == '-')
        return a - b;
    else if(op == '*')
        return a * b;
    else // '/'
        return a / b;
}

int main()
{
    while(~scanf("%s", line))
    {
        stack<int> st; // 构造操作数栈
        for(int i = 0 ; line[i] ; i++)
        {
            if(isdigit(line[i])) // 如果是数字(操作数),入栈
            {
                st.push(line[i] - '0');
            }
            else // 如果是符号
            {
                int b = st.top(); // 取出第一个运算数,也就是右操作数
                st.pop();
                int a = st.top(); // 取出第二个运算数,也就是左操作数
                st.pop();
                st.push(calc(a, b, line[i])); // 计算结果并入栈
            }
        }
        printf("%d\n", st.top()); // 输出结果
    }

    return 0;
}

  附练习题传送门:

  SDUT OJ 2133 数据结构实验之栈三:后缀式求值

4. 括号匹配

  下面就是本章栈的另一个重要的应用了——括号匹配,这也是一个比较常见的应用。简单点说,就是给你一串括号序列,让你判断此序列是否是合法的括号匹配序列。比如,(())就是一个合法序列,而)()(就不是合法序列,同样(][)也不是合法序列,诸如此类……

  接下来,我们引入一个问题,给定一串带各种括号的表达式序列或括号序列,可能包括括号、数字、字母、标点符号、空格,括号包括圆括号(),方括号[],花括号{},让你判断给定序列是不是括号匹配的,匹配输出yes,否则输出no。

  例如,sin(20+10)是匹配的,{[}]是不匹配的。

  我们先分析算法:

  首先,判断一对括号匹配,一定是右括号匹配最近的左括号。也就是说,每遇到一个右括号,左边都会有一个唯一的左括号与之匹配,当所有右括号与所有左括号匹配完成,没有多余的左括号,则匹配成功,否则失败。

  所以我们可以利用一个栈来存储括号:我们从左向右扫描序列,遇到左括号,就直接入栈;遇到右括号,我们就检查栈顶是不是与之对应的左括号,如果是,则匹配,弹出栈顶元素,继续扫描;否则,说明该右括号无匹配的左括号,则失败,该序列不匹配。

  实现起来还是很容易的,直接上代码了:

#include<bits/stdc++.h>

using namespace std;

// 给定左符号a和右符号b判断是否匹配
bool match(char a, char b)
{
    if( (a == '(' && b == ')') ||
		(a == '[' && b == ']') ||
		(a == '{' && b == '}'))
			return true;
	return false;
}

// 判断给定字符串是否是括号匹配的
bool check(char *s)
{
	stack<char> st;
	for(int i = 0 ; s[i] ; i++)
	{
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
		{
			// 左括号直接入栈
			st.push(s[i]);
		}
		else if(s[i] == ')' || s[i] == ']' || s[i] == '}')
		{
			// 如果遇到右括号时,栈空,或者栈顶元素与这个右括号不匹配,直接false
			if(st.empty() || !match(st.top(), s[i]))
				return false;
			// 执行到这里说明上一步匹配成功,弹出栈顶左括号
			st.pop();
		}
		// else 扫描到其他情况,非括号直接不考虑
	}
	// 扫描结束后,只有栈为空才是括号匹配的,否则说明栈内有左括号未被匹配
	return st.empty();
}

int main()
{
	char str[110];
	while(gets(str))
	{
		// 检查是否匹配
		puts(check(str) ? "yes" : "no");
	}

    return 0;
}
  练习题传送门:

  SDUT OJ 2134 数据结构实验之栈四:括号匹配 (此题与上例一样)

5. 出栈序列的判定

  我们通过先前的学习知道,栈是先进后出结构,正是这种特性决定了栈在计算机领域的重要地位。现在有这样一个问题:有一个待入栈序列,你需要将个序列中的元素依次入栈,你可以随时将某元素出栈,这样可以得到一个出栈序列。例如有入栈序列1,2,3,4,5,依次执行push,push,push,pop,pop,pop,push,pop,push,pop,可得到出栈序列3,2,1,4,5。

  现在给定你一个待入栈的序列,再给定若干个待判定序列,你需要判断这些待判定序列是否是待入栈序列的合法出栈序列。

  例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该入栈序列对应的一个出栈序列,但4,3,5,1,2就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。

  提出问题,假设第一行输入n,代表序列长度,随后一行n个整数,代表序列,第三行输入m,代表待匹配出栈序列的个数,接下来m行,每行n个数代表出栈序列。

  其实此题可以根据栈的特性设计算法来快速解决,但是我们这里不考虑,我们只用栈模拟解决 。我们假设给定出栈序列合法,设置一个指针指向出栈序列首端,表示待匹配元素,那么我们将待入栈序列依次入栈,每入栈一个元素,判断一下当前栈顶是不是与指针指向的出栈序列元素匹配,匹配的话,说明该栈顶元素需要出栈,然后还需将指针后移,然后继续判断栈顶和指针元素是否匹配,如此循环直至不匹配;否则继续将待入栈序列入栈。当待入栈序列全部入栈完毕,检查此时栈是否为空。若栈为空,说明入栈序列与出栈序列全部匹配,该出栈序列合法,否则说明不匹配,出栈序列不合法。代码如下:

#include <bits/stdc++.h>

using namespace std;

int arr[10010];
int chk[10010];

int main()
{
    int n, m;
    while(~scanf("%d", &n))
    {
        for(int i = 0 ; i < n ; i++)
            scanf("%d", &arr[i]);
        scanf("%d", &m);
        while(m--)
        {
            for(int i = 0 ; i < n ; i++)
                scanf("%d", &chk[i]);
            stack<int> st;
            int ptr = 0; // 初始化出栈序列匹配元素的指针
            for(int i = 0 ; i < n ; i++)
            {
                // 将入栈序列的元素依次入栈
                st.push(arr[i]);
                while(!st.empty() && st.top() == chk[ptr])
                {
                    // 如果栈不空且栈顶与指针所指匹配,就弹出栈顶并移动指针
                    st.pop();
                    ptr++;
                }
                // 不匹配了,就继续入栈序列元素
            }
            if(st.empty()) // 栈空,说明所有元素匹配,序列合法
                puts("yes");
            else // 否则,说明存在未匹配元素,序列不合法
                puts("no");
        }
    }

    return 0;
}

  附练习题传送门,其实就是这个题……

  SDUT OJ 3334 数据结构实验之栈七:出栈序列判定

6. 迷宫问题

  迷宫问题的求解,我们通常使用两种最经典的搜索方式——深度优先搜索(Depth First Search, DFS)或广度优先搜索(Breadth First Search, BFS)。我们本章是栈,所以暂且不讲这两种搜索,后面二叉树的章节会学到这两种搜索方式。先透露一下,深度优先搜索,是函数递归式的,是利用了函数的特性;广度优先搜索的实现 ,需要依赖队列来维护一个搜索序列。所以栈和队列这两种数据结构的重要性不言而喻。

  迷宫求解问题,我们假设有如下问题:

  一个由n * m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从起点到终点经过每个格子至多一次的走法数(也就是路线的种数)。

  我们回归到问题,假设啊,我们用人类的思维方式走迷宫,我不知道你们是怎么做的,反正我是遵循“不撞南墙不回头”的策略,按照一条路走下去,碰壁了再原路返回,这样逐步地尝试,就会找到出口。我们的深度优先搜索就是“撞南墙”式的搜索方式,按照一个方向不断地找下去,直至无法继续,再改变方向继续寻找,再直至所有方向都尝试完,搜索结束。

  那么用栈如何解决呢?其实函数递归就是栈的典型应用,我们知道,递归其实就是把函数的各参数和入口地址等信息保存到函数栈中,执行的始终是栈顶函数,结束后弹出函数栈执行上一层函数……如此下去,所以这里深搜的递归问题完全可以用栈来解决,我们先图解一个4*4迷宫,假设我们定义方向的优先顺序为右下左上顺时针,即RDLU,如下图(图很大,我可以自己用Windows画图画了好久,绿色起点,粉色终点,看不清请点大图):


  根据上图可以看出,我们在“撞南墙”后需要回退到上一步的操作,这就涉及到保存先前走迷宫的状态,包括走过的格子和每个格子当时所朝向的方向,所以恰好可以用栈来保存状态,因为每次回退的时候,其实就是弹出栈顶元素,这样栈顶元素始终是最后一次操作的状态。

  我们使用一个三元组(x,y,d)来保存迷宫路径状态,x和y分别代表迷宫格子的行列位置,d代表这个格子当前所朝向的方向。注意我们的方向只有四个,且每个方向最多枚举一次(方向不能无限地来回转啊,这样永远没完没了了)。比如我们将上面的迷宫图按照步骤画出栈内状态(又要祭出我的大Windows画图了,假设左上角是1,1):


  这样按照步骤一步一步来,是不是就清晰明了了?下面给出代码,代码中有注释帮助你们自己分析思考,dfs_recursive是递归形式的解法,比较简单,你们可以自己实现一下~上代码:

#include <bits/stdc++.h>

using namespace std;

template<class T1, class T2, class T3>
struct tuple // 自定义一个泛型三元组
{
    T1 first;
    T2 second;
    T3 third;
    tuple(T1 a, T2 b, T3 c):first(a), second(b), third(c){} // 三元组的构造
};
typedef tuple<int, int, int> tpl; // 重定义以下写起来方便……

const int dx[] = {0,1,0,-1}; // 行上的方向
const int dy[] = {1,0,-1,0}; // 列上的方向
// dx dy取相同下标时可表示为一个方向,例如dx[0]和dy[0]表示的是右

int mp[10][10]; // 地图数据
bool vis[10][10]; // 标记数组

int dfs_stack(int n, int m) // 非递归(栈实现)的深度搜索
{
    int res = 0;
    memset(vis, 0, sizeof(vis)); // 多组数据一定记得初始化这些有标记意义的数组或对象
    stack<tpl> st;
    st.push(tpl(1, 1, -1)); // 将起点入栈这里初始方向写成-1
    // 是因为每次取出栈顶均要通过+1来更改方向,
    // 所以初始-1的话,+1才会变成0
    vis[1][1] = true; // 标记此点已在栈中,代表该点是当前已走路径上的点
    while(!st.empty())
    {
        /**
        * 此题求路径数,所以就算找到终点也要回退
        * 继续找其他可能的路径,所以条件是栈空
        * (说明已经退到底了)才结束
        **/
        tpl tmp = st.top(); // 取栈顶元素开始枚举下一步能达到的点
        st.pop(); // 这里先弹出,因为要更改方向,方向更改完成后还要放回栈中,除非无路可走要退回
        int x = tmp.first;
        int y = tmp.second;
        vis[x][y] = false; // 同样先取消标记,因为已经出栈了
        if(x == n && y == m)
        {
            res++;  // 当前点是终点,计数器加1,表示已经搜寻到一条路径
            continue;
        }
        int d;
        for(d = tmp.third + 1 ; d < 4 ; d++) // 顺时针更改方向
        {
            // 根据方向得到下一步尝试(划重点,尝试)到达的点
            int px = tmp.first + dx[d];
            int py = tmp.second + dy[d];
            if(px > 0 && px <= n && py > 0 && py <= m && !vis[px][py] && mp[px][py] == 0)
            {
                // 如果该尝试的点未出界且未在栈内且不是障碍物,则可通行
                tmp.third = d; // 更改栈顶元素的方向值
                st.push(tmp); // 放回栈内
                vis[x][y] = true; // 做上标记,表示在栈中
                st.push(tpl(px, py, -1)); // 把可通行的点入栈,方向初始化为-1
                vis[px][py] = true; // 做上入栈标记
                break; // 跳出循环,一定要跳出,因为已经找到下一步路了,不要再枚举方向了
            }
        }
        // 如果循环可以正常结束(非break),那么说明当前栈顶点已经枚举完所有的方向了,可以回退
        // 在这里回退表现的是没经过修改方向后再次入栈这一步,因为没走break,仔细看
    }
    return res;
}

int dfs_recursive(int n, int m) // 递归的深度搜索(自己实现)
{
    return 0;
}

int main()
{
    int t,n,m;
    while(~scanf("%d", &t))
    {
        while(t--)
        {
            scanf("%d %d", &n, &m);
            for(int i = 1 ; i <= n ; i++)
                for(int j = 1 ; j <= m ; j++)
                    scanf("%d", &mp[i][j]);
            printf("%d\n", dfs_stack(n, m));
        }
    }

    return 0;
}
  深度优先搜索的非递归还是挺麻烦也挺难想的,不过这很能锻炼对栈思想的认识,所以学会非递归模式的深度搜索相当有必要,上述代码需要仔细理解,如果困难的话可以使用单步调试来观察程序的运行,下面给出这道题的传送门:

  SDUT OJ 2449 走迷宫

  

  以上就是本章全部内容了,栈还是一个比较简单的数据结构,但是对于计算机的意义是相当重大的。我们日常使用的操作系统都离不开栈,线程栈、任务栈、进程栈、各种栈……包括我们编程接触的函数递归在运行时也里不开栈,总之,学习并深刻理解栈是相当重要的。如果文中有描述不当或者讲解错误的地方,欢迎大家留言指正~


  下集预告&传送门:数据结构与算法专题之线性表——队列及其应用

2019-05-26 17:00:35 wangguan_9527 阅读数 77
  • 数据结构基础系列(3):和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

栈的定义

栈是一种只能在表尾进行插入或者删除操作的线性表。
允许插入和删除的一端叫栈顶,另一端叫栈底,无任何元素叫空栈(空表),是一种先入后出的线性表。

栈的插入操作叫进栈,也有叫压栈、入栈。(如图)
在这里插入图片描述

栈的删除操作叫出栈,也有叫弹栈。(如图)
在这里插入图片描述

栈的数据结构

栈的顺序存储结构

栈的顺序存储结构也是线性表的存储结构,可以用数组实现。
在这里插入图片描述


public class ArrayStack<T> {
    private int DEFAULT_SIZE = 5;//默认大小
    private Object[] objs;
    private int topIndex = 0;//用来纪录当前栈顶的下标

    public ArrayStack(int DEFAULT_SIZE) {
        this.DEFAULT_SIZE = DEFAULT_SIZE;
        objs = new Object[DEFAULT_SIZE];
    }

    public ArrayStack() {
        objs = new Object[DEFAULT_SIZE];
    }

    /**
     * 进栈
     * @param t 进栈元素
     */
    public void push(T t) {
        //表示当前数组已经没有多余空间(要扩容)
        if (topIndex > DEFAULT_SIZE - 1) {
            objs = AddSize(objs, DEFAULT_SIZE / 2);
        }
        objs[topIndex] = t;
        topIndex++;
    }

    /**
     * 出栈
     * @return true 表示出栈成功,false表示栈为空,出栈失败
     */
    public boolean pop() {
        if (topIndex < 0) {
            return false;
        }
        //清空栈顶
        objs[topIndex--] = null;
        return true;
    }

    /**
     * @param objs 表示要扩容的数组
     * @param size 表示要数组要增加多大
     * @return 返回扩容后的新数组
     */
    private Object[] AddSize(Object[] objs, int size) {
        int newSize = objs.length + size;
        Object[] newObj = new Object[newSize];
        System.arraycopy(objs, 0, newObj, 0, objs.length);
        return newObj;
    }
}
优点 缺点
存取定位方便 需要提前分配空间,当空间不足时则需要扩容,影响性能,如果不扩容就会造成溢出

栈的链式存储结构

栈的链式存储结构可以用线性表的链式存储结构来实现。
在这里插入图片描述


public class LinkStack<T> {

    //表示栈的大小
    private int size;
    //栈顶元素
    private Node top;

    private class Node<T> {

        private Node next;//存放后继节点
        private T data;//数据域

        public Node(T data, Node next) {
            this.next = next;
            this.data = data;
        }

        public Node() {
        }

    }

    /**
     * 入栈
     * @param data
     */
    public void push(T data) {
        top = new Node<>(data, top);
        size++;
    }

    /**
     * 出栈
     * @return
     */
    public T pop() {
        if (top == null) {
            return null;
        }
        Node<T> node = top;
        top = top.next;
        node.next = null;
        size--;
        return node.data;
    }
}

优点 缺点
不用提前申请空间,动态分配存储空间 因为多了存放指针的操作,会额外增加内存

总结:如果栈的元素数量固定,建议用链式存储结构,而元素数量变化不定,则建议用链式存储结构。

JAVA中的栈

JDK封装了Stack的类。位于java.util的包名下。

package java.util;
public class Stack<E> extends Vector<E> {
    /**
     * 无参的构造函数
     */
    public Stack() {
    }

    /*
     * 压栈
     */
    public E push() {
    	//压栈
        addElement(item);
		//返回压入栈中的元素
        return item;
    }

    /**
     * 出栈
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();
		//获取栈顶的元素
        obj = peek();
        //把栈顶元素置为空,并把可用数组长度减一
        removeElementAt(len - 1);

        return obj;
    }

}

主要看压栈的方法 addElement:

//这是个线程安全的方法
 public synchronized void addElement(E obj) {
        modCount++;
        //扩容
        ensureCapacityHelper(elementCount + 1);
        //压栈给栈顶赋值 lementData为vector的object[]数组
        elementData[elementCount++] = obj;
    }

比较复杂的是扩容的方法ensureCapacityHelper:

 private void ensureCapacityHelper(int minCapacity) {
        // 如果当前栈中的元素再加一比elementData的数组长度大,则需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //传入实际栈的数量
     private void grow(int minCapacity) {
        // 先把旧的数组长度赋值给oldCapacity 
        int oldCapacity = elementData.length;
        //capacityIncrement 为自定义要增加的长度(扩容因子),没有设置则默认为0,stack没有设置这个变量,这里数组的长度为newCapacity =oldCapacity +oldCapacity .
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
         //如果新产生的数组长度小于实际需要的数组长度,则使用实际长度。                              
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
         //如果新产生的数组长度大于 Integer.MAX_VALUE - 8  则等于Integer.MAX_VALUE 或	者Integer.MAX_VALUE - 8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            //真正在这里扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
   

Arrays.copyOf方法:


 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
     	//拿到数组类型,并新建newLength长度的数组。
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
            //把original的数组从0开始,复制到名为copy,下标为0开始的新数组上,到original数组长度跟newLength的最小值的地方(一般都是original.length)。
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        //返回带有元数据的新数组
        return copy;
    }
    

出栈方法 pop()调用了peek()与removeElementAt()

先看peek()

 public synchronized E peek() {
 		//获取栈中元素数量
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    } 
    
    //直接返回数组下标为index的元素
	public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + 	elementCount);
        }
        return elementData(index);
    }

再看出栈的主要方法removeElementAt:

 public synchronized void removeElementAt(int index) {
 		//计数器加1
        modCount++;
        //如果下标大于数组总长度抛异常
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
         //如果下标为负数抛异常
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        //获取需要复制数组元素的个数(用可用的数组减去栈顶的下标再减一,减一是因为下标是从0开始)
        int j = elementCount - index - 1;
        if (j > 0) {
        	//重新构造数组,这里主要是移除非栈顶的元素,栈没有用到。
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        //有效数量键1
        elementCount--;
        //清空数组中最后一个元素清空
        elementData[elementCount] = null; /* to let gc do its work */
    }

可以看到java提供的栈stack用了线性表的顺序存储结构。

java提供的stack可以直接使用,不用关心栈溢出问题,调用stack的push()、pop(),就可以进行入栈出栈操作。

但有一个缺点是当Stack快速入栈多个元素后再恢复回来,在元素不变的前提下,其实elementCount数组的长度会增加,这个数组会一直占有着内存,造成内存浪费。

栈的应用

  • Android中的atcivity栈。
  • 递归函数(如斐波那契数列的实现)。
  • 四则运算中的中缀表达式与后缀表达式的计算。

参考:大话数据结构

下一节 数据结构:队列

2019-03-17 17:33:57 qq_24095055 阅读数 210
  • 数据结构基础系列(3):和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

  • 栈也是一种数据结构
  • 相比数组,栈对应的操作是数组的子集
  • 只能从一端添加元素,也只能从一端取出元素
  • 这一端称为栈顶
  • 栈是一种后进先出的数据结构
  • Last In First Out(LIFO)
  • 在计算机的世界里,栈拥有着不可思议的作用

栈的应用

  • 无处不在的Undo操作(撤销)
  • 程序调用的系统栈

在这里插入图片描述
如图,当我们执行程序A到第二行时,要跳转去执行B而暂停A,这时系统就会将A2放入系统栈中,说明说明A暂停在了第二行中断了,在执行B时到第二行时会中断跳转到C中,将状态B2压入系统栈中,在执行完C后系统会在系统栈中依次取出之前中断的B2,A2继续执行。

栈的实现

Stack

  • void push(E):入栈
  • E pop():出栈
  • E peek():查看栈顶元素(不出)
  • int getSize():返回栈元素个数
  • boolean isEmpty():栈是否为空

这里我们使用基于动态数组的实现方式

/**
 * Created by binzhang on 2019/3/16.
 */
public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peak();
}

/**
 * Created by binzhang on 2019/3/16.
 */
public class ArrayStack<E> implements Stack<E> {

	// 这里用的是我们自己定义的泛型数组,在数组篇中有写
    Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peak() {
        return array.getLast();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append("[");
        for (int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] top");
        return res.toString();
    }
}

测试类编写:

public class Main {

    public static void main(String[] args) {

        ArrayStack<Integer> stack = new ArrayStack<>();

        for (int i = 0 ; i < 5 ; i ++){
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

输出:

Stack: [0] top
Stack: [0, 1] top
Stack: [0, 1, 2] top
Stack: [0, 1, 2, 3] top
Stack: [0, 1, 2, 3, 4] top
Stack: [0, 1, 2, 3] top

栈的时间复杂度

ArrayStack

  • void push(e) O(1) 均摊
  • E pop() O(1) 均摊
  • E peek() O(1)
  • int getSize() O(1)
  • boolean isEmpty() O(1)

栈的应用

  • undo操作-编辑器
  • 系统调用栈-操作系统
  • 括号匹配-编译器

使用栈解决有效的括号问题(LeetCode第二十号问题)

  • 题目描述

    给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
    有效字符串需满足:
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。

  • 示例

    示例 1:
    输入: "()"
    输出: true
    
    示例 2:
    输入: "()[]{}"
    输出: true
    
    示例 3:
    输入: "(]"
    输出: false
    
    示例 4:
    输入: "([)]"
    输出: false
    
    示例 5:
    输入: "{[]}"
    输出: true
    

    栈顶元素反应了在嵌套的层次关系中,最近的需要匹配的元素

  • 解答代码

    import java.util.Stack;
    class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            for (int i = 0 ; i < s.length() ; i ++){
                char c = s.charAt(i);
                if (c == '(' || c == '[' || c == '{'){
                    stack.push(c);
                }else{
                    if(stack.isEmpty())
                        return false;
                    char topChar = stack.pop();
                    if (c == ')' && topChar != '(')
                        return false;
                    if (c == ']' && topChar != '[')
                        return false;
                    if (c == '}' && topChar != '{')
                        return false;
                }
            }
            return stack.isEmpty();
        }
    
        public static void main(String[] args) {
            System.out.println((new Solution()).isValid("{}[]()")); // true
            System.out.println((new Solution()).isValid("([)]"));   // false
        }
    }
    

数据结构-栈

阅读数 235

数据结构之栈的应用——表达式求值

博文 来自: Katherineljn
没有更多推荐了,返回首页