3.数据结构笔记学习--栈和队列

• 栈的基本概念：
  • 栈的定义：一种只能在一端进行插入或者删除的线性表，这一端称为栈顶
  • 栈的特点：先进后出
  • 栈的存储结构：顺序栈和链式栈

• 队列的基本概念：
  • 队列的定义：允许在表的一端（队尾）进行插入，在另一端（队头）进行删除的线性表
  • 队列的特点：先进先出
  • 队列的存储结构：顺序队和链队

• 栈和队列的存储结构、算法：
  • 顺序栈的定义：

    typedef struct
    {
        int data[maxSize];  //存放栈中的元素
        int top;        //栈顶指针
    }SqStack;

  • 链栈结点定义：

    typedef struct LNode
    {
        int data;       //数据域
        int LNode *next;//指针域
    }LNode;

  • 顺序队列定义：

    typedef struct 
    {
        int data[maxSize];       
        int front;//队首指针
        int rear; //队尾指针
    }SqQueue;

  • 链队定义：
    • 队结点类型定义：

      typedef struct QNode
      {
          int data;       
          struct QNode *next; //指针域
      }QNode;

    • 链队类型定义：

      typedef struct 
      {
          QNode *front;
          QNode *rear;
      }LiQueue;

• 顺序栈的基本算法操作：
  • 顺序栈st的要素
    • 两个状态：
      • 栈空状态：st.top==-1
      • 栈满状态：st.top==maxSize-1;

• • • 两个操作：
      • 元素x进栈操作 ++（st.top);   st.data[st.top]=x;
      • 元素x出栈操作 x=st.data[st.top];  --(st.top);

• • • 非法状态，上溢和下溢

• • 初始化栈的算法：

    void initStack(Sqstack &st) //初始化栈
    {
        st.top = -1;   //将栈顶设置为-1
    }

  • 判断栈空的算法：

    int isEmpty(Sqstack st) 
    {
       if(st.top==-1)
            return 1;
       else
            return 0;
    }

  • 进栈算法：

    int Push(SqStack &st, int x)
    {
        if(st.top == maxSize-1)
            return 0;
        ++(st.top);                        //先移动指针再进栈
        st.data[st.top]=x;
            return 1;
    }

  • 出栈算法：

    int Pop(SqStack &st, int &x)
    {
        if(st.top == -1)
            return 0;
        x = st.data[st.top];   //先取出元素，再进行指针的移动
        --(st.top);
            return 1;
    }

• • 考题中实用的栈操作写法：
    • 声明一个栈并且初始化：      int stack[maxSize];  int top=-1;    //声明加初始化都有了
    • 元素x进栈：                          stack[++top]=x;
    • 元素x出栈：                           x=stack[top--];
    • //++top 与top++的区别 ：a=++top 是 top 先自增1，再将top值给a； 而b=top++ 是top先给b，再进行top自增1

• 链栈的基本算法操作：
  • 链栈的要素：
    • 状态：
      • 栈空状态：1st ->next = null;
    • 两个操作：
      • 元素进栈：   

        p->next = 1st->next;
        1st->next = p;    //头插法建立链表的插入操作

      • 出栈操作：

        p = 1st->next;
        x = p->data;
        1st->next = p->next;
        free(p);   //单链表删除操作

  • 链栈的初始化算法：

    void InitStack(LNode *&1st)
    {
        1st = (LNode*) malloc(sizeof(LNode));  //制造一个头结点
        1st->next = NULL;
    }

     

  • 判断栈空的算法：

    int isEmpty(LNode *1st)
    {
        if(1st->next = NULL)
            return 1;
        else 
            return 0;
    }

     

  • 进栈算法：

    void push(LNode *1st,int x)
    {
        LNode *p;
        p = (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
        
        
        P->data = x;
        p->next = 1st->next;
        1st->next = p;
    }

     

  • 出栈算法：

    void Pop(LNode *1st,int &x)
    {
        LNode *p;
        if(1st->next==NULL)
            return 0;
        
    //单链表删除操作
        p = 1st->next;
        x = p->data;
        1st->next = p->next;
        free(p);
        return 1;
    }

     

3.数据结构笔记学习--栈和队列

原文：https://www.cnblogs.com/frl520/p/9419172.html