第三章：栈和队列

数据结构第三章，涵盖了队列的基本概念、分类、操作、代码实现等多个方面的信息，适合计算机科学相关专业的学生或对数据结构感兴趣的学习者使用，能够帮助同学们系统地掌握队列的相关知识和编程实现方法。

第三章

• 栈
  • 递归定义
  • 定义
  • 基本操作
    • 初，销，空，长，获，插，删，遍
  • 存储结构
  • 栈
    • 顺序栈
      • 初始化
        • ①if（s.base＝＝NULL）return ERROR； ②s.top＝＝s.base；
      • 入栈
        • ①if（s.top-s.base＞＝s.stacksize）return ERROR； ②*s.top++＝e；／s.base［s.top++］＝e；
      • 出栈
        • ①if（s.top＝＝s.base）return ERROR； ②e＝*--s.top；／e＝s.base［--s.top］；
      • 读取
        • ①if（s.top＝＝s.base）return ERROR； ②e＝*（s.top-1）；
  • 栈的应用
    • 括号匹配问题
      • • void main （） ｛ initstack（s）； scanf（str）； for（i＝0；sti［i］；i++） switch（str［i］） ｛ case‘(’： case‘[’： case‘{’：push（s，str[i]）；break； case‘)’：gettop（S，x）； if（x＝‘（’）pop（S，y）；else｛printf（“ERROR”）；exit（0）；｝ break； case‘]’：gettop（S，x）； if（x＝‘[’）pop（S，y）；else｛printf（“ERROR”）；exit（0）；｝ break； case‘}’：gettop（S，x）； if（x＝‘{’）pop（S，y）；else｛printf（“ERROR”）；exit（0）；｝ break； ｝ if（stackempty（s））printf（“success”）； else printf（“Error”）； ｝
    • 进制转换问题
      • ①输入某个十进制数。 ②选择想要进行转换的进制数。 ③将十进制数对进制数进行求余。每次将余数入栈，接着将十进制数变成除以进制数以后的数。 ④重复③，直到十进制数为0停止。 ⑤接着将栈中元素依次出栈，直到栈为空停止。
        • # define K 8 Initstack（S）； scanf（“%d”，&n）； while（n） ｛ push（s，n%k）； n／＝k； ｝ while（!stackEmpty（s）） ｛ pop（s，e）； printf（“%d”，e）； ｝
• 队列
  • 定义
  • 基本操作
    • 初，销，空，长，获，插，删，遍
  • 存储结构
  • 队列
    • 顺序队列→循环队列
      • 初始化
        • ①if（Q.front＝＝NULL）return ERROR； ②Q.rear＝Q.front；
      • 入队
        • ①if（（Q.rear+1）%MAXSIZE＝＝Q.front）return ERROR； ②Q.base［Q.rear］＝e；／*Q.rear＝x； ③Q.rear＝（Q.rear+1）%MAXSIZE；
      • 出队
        • ①if（Q.rear＝＝Q.front）return ERROR； ②e＝Q.base［Q.front］；／x＝*Q.front； ③Q.front＝（Q.front+1）%MAXSIZE；
    • 链队列
      • 初始化
        • ①if（Q.front＝＝NULL）return ERROR； ②Q.rear＝Q.front； ③Q.front→next＝＝NULL；
      • 销毁
        • while（Q.front） ｛ Q.rear＝Q.front→next； free（Q.front）； Q.front＝Q.rear； ｝
      • 入队
        • if（P＝NULL）return ERROR； p→data＝e； p→next＝NuLL； Q.rear→next＝p； Q.rear＝p；
      • 出队
        • if（Q.front＝Q.rear）return ERROR； p＝Q.front→next； Q.front→next＝p→next； e＝p→data； free（p）； if（Q.rear＝＝p）Q.rear＝Q.front；