美文网首页程序员
3--4.栈与队列

3--4.栈与队列

作者: lumo的二次学习笔记 | 来源:发表于2017-12-08 20:24 被阅读0次

[TOC]

写在前面

本篇文章整理《数据结构(C++语言版)》关于栈与队列这种线性结构知识点。
整个数据结构部分章节列表如下:
1 向量
-- 1.1 遍历
-- 1.2 唯一化
-- 1.3 查找

2 列表
-- 2.1 列表节点
---- 2.1.1前插入算法
-- 2.2 列表模板类
---- 2.2.1 列表初始化

3 栈
--3.1 栈应用
---- 3.1.1 括号匹配
---- 3.1.2 栈混洗甄别
---- 3.1.3 中缀表达式
4 队列

3 栈

后进先出(LIFO)是栈这种结构最大的特点。对栈而言,只有一端的可访问称作,顶端top。

栈结构示意及基础功能
栈也是一种线性结构,即满足逻辑地址连续,故可直接基于向量或列表派生。
//基于vector结构的栈初始化
template<typename T>
class Stack: public Vector<T>{
public:
  void push(T const& e) { insert( size(), e);}  //入栈,等效于作为向量末元素插入
  T pop() { return remove( size() -1); }  //出栈,等效于删除向量末元素
  T& top() { return ( *this ) [ size() - 1 ]; }  //取顶,直接返回向量的末元素
};

3.1 栈应用

基于栈结构的应用,就是要充分利用其后进先出LIFO的特性。

3.1.1 括号匹配

解决问题:判断一个只含括号的表达式是否匹配。
算法:从表达式左侧开始扫描,当扫描到左括号(则压入栈中,若扫描到右括号)则弹出栈顶元素,继续扫描下去。当且仅当最后扫描完成时,栈类所有左括号(均已弹出,栈为空栈时该表达式括号匹配。

括号匹配算法示意图
代码实现
bool paren( char exp[], int lo, int hi ) { //exp[lo, hi)
  Stack<char> s;
  for(int i=lo; i < hi; i++){
    if( '(' == exp[i] ) s.push(exp[i]);  //若左括号,入栈
    else if( !s.empty() ) s.pop();  //若右括号,且栈非空,弹出栈顶
      else return false;  //若括号表达式未扫描结束,栈已空,则不匹配
  }
  return s.empty();
}

TIPS:字符串与字符数组
字符串以空字符\0结尾,用来标记字符串的结尾。
char dog[4] = {'a', 'b', 'c', 'd'}; //不是字符串,是char数组
char cat[4] = {'a', 'b', 'c', '\0'}; //是字符串,也是char数组
另一种操作方法是通过双引号声明字符串,若声明长度比实际长度长,则空字符将自动补全到实际长度之后
char bird[5] = "abc"; //实际为 abc\0\0
char bird[] = "abc"; //编译器自己判断字符串长度

3.1.2 栈混洗甄别

解决问题:将栈A中的元素通过栈S转移入栈B中。对元素的移入移出操作只允许以入栈出栈方式。进而判断栈B中元素序列是否是一种栈混洗。

栈混洗
算法:不妨设栈A的元素为升序排列。对栈B中第i个元素,当其从栈S弹出前,S栈顶端以下元素按降序排列。即,若栈S顶元素小于B[i],则依次将A中元素入栈;若栈S顶元素等于B[i],则S出栈,继续判断B[i+1];若栈S顶元素大于B[i],则不是栈混洗
该算法的一个典型应用场景为火车调度问题。
代码实现
/*
判断栈B中序列是否为一种栈混洗
为了简化问题,栈A、B元素确定,因此可以通过数组等方式实现。
/*
int A = 1;
int B[] = {2, 3, 1, 4, 5};
bool Stackverfi(int A, const int* array_B){
  Stack<int> S;
  for(int i = 0; i < 5; i++){
    while( S.top() < B[i] ){
      S.push(A++);
      std::cout << "push\n";
    }
    if( S.top() == B[i] ){ 
      S.pop();
      std::cout << "pop\n";
    }
    else{
      std::cout << "NO!!!";
      return false;
    }
  }
}

3.1.3 中缀表达式

算法:对于一个正确的算数表达式,先准备两个栈A,B分别用于存储运算符和运算数。扫描到运算数,则入栈A中;扫描到运算符时,与栈B的栈顶运算符比较,若栈顶运算符优先级较低,则入栈;若栈顶运算符优先级较高,则弹出栈B顶运算符,弹出栈A两个运算数(若为单元素操作符,只弹出一个元素),将运算结果压入栈A

采用一个栈结构的算法实例

4 队列

队列的特性与栈结构正好相反,其主要性能是先进先出(FIFO)。具体实现方式与栈结构类似,这里不过多叙述。

相关文章

  • 3--4.栈与队列

    [TOC] 写在前面 本篇文章整理《数据结构(C++语言版)》关于栈与队列这种线性结构知识点。整个数据结构部分章节...

  • Swift 队列&栈 相关操作

    栈 LIFO(后进先出) 队列 FIFO(先进先出) 队列与栈相互的实现 栈 - 队列实现 队列 - 栈实现 相关...

  • 数据结构学习 | 队列和栈

    栈 后进先出 栈顶允许插入(压栈)、删除(弹栈) 应用:数制转换数制转换与栈 队列 先进先出 队列头部允许删除,队...

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 常见数据结构

    栈、队列、数组、链表、树、哈希表 栈 与 队列 首先我们需要了解【栈】与【列队】的区别,它们的最大区别就是数据进出...

  • 栈和队列

    用栈定义队列(出入栈) 用队列定义栈(数据队列和辅助队列)

  • LeetCode刷题笔记(三)栈与队列

    三. 栈与队列 python中的栈直接用list实现,队列用deque,需要导入外部包。 155. 最小栈 题目:...

  • 实 验 四 栈和队列

    一、实验目的与要求:## 1、理解栈和队列抽象数据类型。 2、掌握栈和队列的存储结构和操作实现。 3、理解栈和队列...

  • 数据结构的各种代码

    第 02 章 线性表 顺序存储结构 链式存储结构 第 03 章 栈与队列 顺序栈 链栈 两栈共享空间 循环队列 链...

  • 数据结构——栈和队列

    用数组实现栈和队列 用栈实现队列 用队列实现栈 栈和队列的经典算法题最小间距栈宠物收养所 数组实现栈和队列 用数组...

网友评论

    本文标题:3--4.栈与队列

    本文链接:https://www.haomeiwen.com/subject/ndwdixtx.html