数据结构——栈和队列学习篇(一)

前言

这一部分主要是对栈和队列的学习，只要把链表学好，再看栈和队列的时候就会感觉计较简单了
毕竟栈和队列属于线性表

栈学习

栈：是限定仅在表尾进行插入或删除操作的线性表

栈顶：表尾端称为栈顶

栈底：表头端称为栈底

栈后进先出的线性表

顺序栈的定义

#define MAXSIZE 100
typedef struct{
    SElemType *base;//栈底指针
    SElemType *top;//栈顶指针
    int stacksize;//栈可用最大容量 
}SqStack;

注意： 当top和base的值相等时，表示栈为空栈

栈的初始化

Status InitStack (SqStack &S)
{//构造一个空栈S 
    S.base=new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间 
    if(!S.base)  //存储分配失败 
    exit(OVERFLOW);
    S.top=S.base;//top初始化为base，空栈 
    S.stacksize=MAXSIZE;// stacksize置为栈的最大容量MAXSIZSEIZ 
    return OK; 
}

栈的入栈

Status Push(SqStack &S, SElemType e)
{//插入元素e为新的栈顶元素 
    if(S.top-S.base==S.stacksize) return ERROR;//栈满
    *S.top++=e; //元素e压入栈顶，栈顶指针加1
    return OK; 
 }

栈的出栈

Status Pop(SqStack &S, SElemType e)
{//删除S的栈顶元素，用e进行返回 
    if(S.to==S.base) return ERROR;//栈空 
    e=*--S.top; //栈顶指针减1，将栈顶元素赋给e 
    return OK; 
 }

取栈的栈顶元素

Status GetTop(SqStack S)
{//返回S的栈顶元素，不修改栈顶指针 
    if(S.top!=S.base)//栈非空 
    return *(S.top-1)//返回栈顶元素的值，栈顶指针不变 
 }

链栈的表示和实现

链栈的存储

Status struct StackNode
{
    ElemType data;
    struct StackNode *next;
 } StackNode,*LinkStackl;

链栈的初始化

Status InitStack(LinkStack &S)
{//构造一个空栈S，栈顶指针置空 
    S=NULL;
    return 0;
 }

链栈的入栈

status Push(LinkStack &S, SElemType e)
{//在栈顶插入元素e 
    p=new StackNode; //生成新结点
    p->data=e; //将新结点的数据域置为e
    p->next=S;//将新结点插入栈顶
    S=p;//修改栈顶指针为p
    return OK; 
 }

链栈的出栈

status Pop(LinkStack &S, SElemType &e)
{//删除S的栈顶元素，用e进行返回
    if(S==NULL)return ERROR;//栈空 
    e=S->data;//将栈顶元素赋给e 
    p=S;//用p临时保存栈顶元素空间， 
    S=S->next;//修改栈顶指针 
    delete p; //删除栈顶元素 
    return OK; 
 }

队列学习

队尾：允许插入的一端称为队尾

队头：允许删除的一端称为队头

先进先出的原则运算

只能是队列的队头进行删除，队列的队尾元素进行插入

队列的存储结构

#define MAXQSIZE 100//队列可能达到的最大长度 
typedef struct
{
    QElemType *base;
    int front;//头指针 
    int rear;//尾指针 
 } SqQueue;

其中的front表示头指针(队列),rear表示尾指针(队列)

循环队列

以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，

需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作。

循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，

则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。

判断循环队列是“空”还是“ 满”，有以下两种处理方法：

1）设置状态标志位以区别空还是满

2）少用一个元素，约定“队头front在队尾rear的下一个位置（指的是环的下一个位置）”作为“满”的标志

C语言中，不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；

如果用户无法预估所用队列的最大长度，则宜采用链队列。

定义front为队列头元素的位置，rear为队列尾元素的位置，MAXSIZE为循环队列的最大长度。注意以下几点，循环队列迎刃而解：

1）求元素的个数：(rear - front + MAXSIZE) % MAXSIZE

2）front/rear指向逻辑的下一个空间 front =（front+1)%MAXSIZE，rear = (rear+1)%MAXSIZE

3）判空：front == rear

4）判满：(rear+1+MAXSZIE)% MAXSIZE == front

初始化

Status InitQueue(SqQueue &Q)
{
    Q.base=new QElemType[MAXQSIZE];
    if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
 }

循环队列的长度

入队

出队

取循环队列的队头元素

链式队列

链式存储结构

变化过程

链式队列初始化

链式队列入队

链式队列出队

注意：在链式队列出队操作时需要考虑到，当队列中最后一个元素被删除后，队尾指针也丢失了，因此需要对队尾指针重新赋值