第三章栈和队列

栈：

限定仅在表尾进行插入和删除的操作线性表

push 入栈

pop 出栈

顺序栈

1.给顺序栈分配一个最大容量的MAXSIZE的数组

初始化栈

1.  //给顺序栈分配一个最大容量 maxsize 的数组
    S.base=new SELemType[MAXSIZE];
    2// 将栈顶初始初始化为base  
    s.top=s.base;
2.  //将栈的大小设置为最大容量  
    S.stackSize=MAXSIZE;

入栈操作

1. // 判断栈是否满了，若满，返回false
if(s.top-s.base==s.stackSize) {return false;}
2. //将新元素加入到当前top指针的空间，再将top指针向上移动一位
    *s.top=e;  s.top++;

出栈操作

1. //判断栈是否为空栈
    if(s.base==s.top)
        return false
2. //不是空栈 ，将栈顶元素向下移动一位，再取出栈顶指针指向的元素
     s.top--;  e=*s.top;

链式栈

使用链式栈前提，不用设置头节点

初始化栈

S=NULL;

入栈

//单链表插入 新节点p 入栈进去 S
      P.data=e;
      P.next=S;
      S=p;
  

出栈

//判断栈是否否为空 
    if(S==NULL)
        return false;
 2. 将栈顶元素赋值给e  e=s.data;
 3. 将s 临时给p  p=s;
 4.   s=s->next;  修改栈顶指针
 5.   free(p);   释放栈

队列

是一种先进先出的线性表，它允许再表的一端进行插入元素表的另一端的删除元素的表

循环队列

队列是一种先进先出线性表，随着入队和出队操作交替进行，会使队尾指针和对头指针整体向上移动，当队尾指针移动到最后一个元素，若再有元素入队，就会出现假溢出现象，此时队列种还有可用空间，为了解决这假溢出，我们将队列的头和尾进行相接变成一种循环结构，此就为循环队列。

循环队列如何处理队满

2 少用一个空间表示队满 队满的元素是n-1

（rear+1）%maxSize=font;