【图解数据结构】栈全面总结

《【图解数据结构】栈全面总结》

 目录

一、前言

二、基本概念

三、栈的表示和实现

1.顺序栈

2.链栈

四、栈的常见算法实现

1.初始化

2.判空

3.判满

4.顺序栈取栈顶元素

5.顺序栈入栈

6.顺序栈出栈

五、双栈

1.双端顺序栈进栈操作

2.双端顺序栈出栈操作

六、栈的应用举例

1.回文游戏

2.多进制输出

3.表达式求值

4.地图染色

七、总结与提高

一、前言

  • 掌握栈这种抽象数据类型的特点,在相应的实际问题中正确应用相关代码
  • 掌握栈类型的两种实现方法

二、基本概念

  • 定义:只允许在一端进行插入或删除的线性表
  • 栈顶(top):允许进行插入或删除的一端
  • 栈底(bottom):与栈顶相对应的一端
  • 《【图解数据结构】栈全面总结》
  • 特点:先进后出

三、栈的表示和实现

1.顺序栈

  • 定义:一组地址连续的存储单元依次存放自栈底到栈顶的数据元素
  • top :用来表示栈顶元素的位置
    • top==-1表示空栈
    • top==NULL表示栈不存在
    • top>stacksize元素溢出

结构体定义:

#define n 500//定义顺序栈大小
struct stack
{
    int top;//栈顶指针
    int a[n];//顺序栈数组
}SeqStack;

2.链栈

结构体定义:

typedef struct node
{
    int data;//定义数据类型
    struct node*next;//定义链栈

}ChaiinStack;

特点: 

  •  链栈没有栈满问题,大小可以随时扩充
  • 插入和删除在栈顶处实行
  • 链式栈的栈顶在链头
  • 与单链表存储结构一致,与顺序表逻辑结构一致

四、栈的常见算法实现

动态图:

《【图解数据结构】栈全面总结》

 算法讲解:

  • push入栈,指针top向上移动

  • pop出栈,指针top向下移动

1.初始化

void InitStack(SeqStack *S)
{	/*构造一个空栈S*/
  	S->top = -1;
}

2.判空

/*顺序栈判栈空*/
int IsEmpty(SeqStack *S)
 {     /*判断栈S为空栈时返回值为真,反之为假*/
	 return(S->top==-1?TRUE:FALSE);
 }

3.判满

/*顺序栈判栈满*/
int IsFull(SeqStack *S)	
{   /*判断栈S为满栈时返回值为真,反之为假*/
	return(S->top==Stack_Size-1?TRUE:FALSE);
}

4.顺序栈取栈顶元素

int GetTop(SeqStack *S,StackElementType *x)
{  	/* 将栈S的栈顶元素弹出,放到x所指的存储空间中,但栈顶指针保持不变 */
	if(S->top == -1)      /*栈为空*/
		return(FALSE);
	else
	{
  		*x = S->elem[S->top];
  		return(TRUE);
	}	
}

5.顺序栈入栈

/*顺序栈出栈*/
int Pop(SeqStack *S,StackElementType *x)
{  
	/* 将栈S的栈顶元素弹出,放到x所指的存储空间中 */
	if(S->top == -1)    /*栈为空*/
		return(FALSE);
	else
	{
  		*x = S->elem[S->top];
		S->top++;    /* 修改栈顶指针 */
  		return(TRUE);
	}
}

6.顺序栈出栈

/*顺序栈出栈*/
int Pop(SeqStack *S,StackElementType *x)
{  
	/* 将栈S的栈顶元素弹出,放到x所指的存储空间中 */
	if(S->top == -1)    /*栈为空*/
		return(FALSE);
	else
	{
  		*x = S->elem[S->top];
		S->top--;    /* 修改栈顶指针 */
  		return(TRUE);
	}
}

五、双栈

《【图解数据结构】栈全面总结》

 《【图解数据结构】栈全面总结》

算法详解: 

  • 两个顺序栈stack1,stack2
  • 顺序栈1从左到右依次入栈,top1++
  • 顺序栈1从右向左依次入栈,top2–
  • 栈满条件:top1+1==top2

1.双端顺序栈进栈操作

/*双端顺序栈进栈操作。*/
int Push(DqStack *S, StackElementType x, int i)
{	/*把数据元素x压入i号堆栈*/
	if(S->top[0]+1==S->top[1])    /*栈已满*/
		return(FALSE);
	switch(i)
	{
	case 0:
		S->top[0]++;	S->Stack[S->top[0]]=x;	break;
	case 1:
		S->top[1]--;	S->Stack[S->top[1]]=x;	break;
	default:  /*参数错误*/
        return(FALSE)
 	}
	return(TRUE);
}

2.双端顺序栈出栈操作

/*双端顺序栈出栈操作。*/
int Pop(DqStack *S,StackElementType *x,int i)
{	/* 从i 号堆栈中弹出栈顶元素并送到x中 */
	switch(i)
	{
	case 0:
		if(S->top[0]==-1)  return(FALSE);
		*x=S->Stack[S->top[0]];   S->top[0]--;	break;
	case 1:
		if(S->top[1]==M)  return(FALSE);
		*x=S->Stack[S->top[1]];	S->top[1]++;	break;
	default:
		return(FALSE);
	}
	return(TRUE);
}

六、栈的应用举例

1.回文游戏

  1. 读入给定的字符串
  2. 吸收空格,输出和原串比较
  3. 如果和原串相等,则是回文串

2.多进制输出

  1. 把十进制转化为八进制
  2. %8取余数放入栈,/8继续操作
  3. 把栈中的元素输出

3.表达式求值

《【图解数据结构】栈全面总结》

  • 给出中缀表达式,利用栈的特点求出后缀表达式 

4.地图染色

《【图解数据结构】栈全面总结》

七、总结与提高

  • 对于使用C++编程来说,上文顺序栈的判空、判满、插入、删除等等一系列代码,不需要你完全掌握,C++的STL标准库中为你准备好了函数等你调用。

 C++stack头文件:

#include<stack>
//#include<bits/stdc++.h>或者万能头文件
using namespace std;

 C++stack具体操作:

  • 用stack定义s类(定义什么都可以,只要把s变成定义的字母就可以调用C++中的函数),具体使用方法为:
函数用法
s.empty()判断栈是否为空,不为空返回1,为空返回0
s.size()返回栈中元素个数
s.top()返回栈顶元素,但不删除该元素
s.pop()返回栈顶元素,删除该元素
s.push()将元素插入栈

力扣习题:

        一、栈实现队列

        二、后缀表达式

        三、回文链表

        四、栈的压入与弹出序列

        五、计算器

        六、甲板上的战舰

附录:

    原文作者:知心宝贝
    原文地址: https://blog.csdn.net/qq_53673551/article/details/122012979
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞