数据结构知识点（3）——栈与队列

content
{:toc}
栈的表示和操作的实现
顺序栈的表示和实现

顺序栈的存储结构

typedef struct     //栈的存储结构
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}SqStack;

（1） base为栈底指针，初始化完成后，栈底指针base始终指向栈底的位置，若base为NULL，则表明栈结构不存在；
（2） top为栈顶指针，其初值指向栈底。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1；
（3）栈空时，top和base的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置；
（4） stacksize为栈可使用的最大容量；

顺序栈的初始化

Status InitStack(SqStack &S)    //栈的初始化
{
     S.base=new ElemType[MAXSIZE];    //为顺序栈分配一个MAXSIZE的数组空间
     if(!S.base) return ERROR;
     S.top=S.base;
     S.stacksize=MAXSIZE;
     return OK;
}

压栈

Status Push(SqStack &S,ElemType e)    //压栈
{
    if(S.top-S.base==S.stacksize) return ERROR;    //判断是否到达最大容量
    *S.top=e;
    ++S.top;
}

出栈

Status Pop(SqStack &S,ElemType &e)    //出栈
{
    if(S.top==S.base) return ERROR;     //判断栈是否为空
    e=*--S.top;
    return OK;
}

取栈顶元素

Status GetTop(SqStack S)    //获取栈顶元素
{
    if(S.top!=S.base)    //判断栈是否为空
       return *(S.top-1);
}

链栈的表示和实现

链栈的存储结构

typedef struct StackNode
{
    ElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

链栈的存储结构与点链表的存储结构相同，由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的，因此链栈不需设置头结点。
初始化
1
2
3
4
5
Status InitStack(LinkStack &S)
{
    S=NULL;
    return OK;
}

压栈

Status Push(LinkStack &S,ElemType e)
{
    StackNode *p;
    InitStack(p);    //为结点开辟内存空间
    p->data=e;
    p->next=S;
    S=p;
    return OK;
}

出栈

Status Pop(LinkStack &S,ElemType &e)
{
    StackNode *p;
    e=S->data;
    p=S;
    S=S->next;
    delete p;
    return OK;
}

取栈顶元素

ElemType GetTop(LinkStack S)
{
    if(S!=NULL)	return S->data;
    return ERROR;
}

队列的表示和操作的实现

循环队列—队列的顺序表示和实现

队列的存储结构

typedef struct     
{
    ElemType *base;
    int front; //整型变量，在此叫做头指针
    int rear;  //整型变量，在此叫做尾指针
}SqQueue;

（1）初始化创建空队列时，令front=rear=0；
（2）每当插入新的队列尾元素时，尾指针rear增1；每当删除队列头元素时，头指针front增1；
（3）在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一位置；
（4）队空的条件：Q.front=Q.rear
（5）队满的条件：(Q.rear+1)%MAXSIZE==Q.front
初始化
1
2
3
4
5
6
7
Status InitQueue(SqQueue &Q)    //初始化
{
    Q.base=new ElemType[MAXSIZE];   //Q.base指向数组空间的首地址
    if(!Q.base) return ERROR;
    Q.front=Q.rear=0;
    return OK;
}

求队列长度

Status QueueLength(SqQueue Q)    //队列的长度
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

入队

Status EnQueue(SqQueue &Q,ElemType e)    //进队列
{
    if((Q.rear+1)%MAXSIZE==Q.front)
        return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXSIZE;     //队尾指针加1
    return OK;
}

出队

Status DeQueue(SqQueue &Q,ElemType &e)    //出队列
{
    if(Q.rear==Q.front) return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXSIZE;    //队头指针加1
    return OK;
}

获取队头元素

ElemType GetHead(SqQueue Q)     //获取队列头元素
{
    if(Q.front!=Q.rear)
        return Q.base[Q.front];
}

链队—队列的链式表示和实现

链队的初始化

typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

一个链队显然需要两个分别指向队头和队尾的指针才能确定；
这里为操作方便，给链队添加一个头结点，并令头指针指向头结点；
初始化
1
2
3
4
5
6
Status InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=new QNode;
    Q.front->next=NULL;
    return OK;
}

链队的入队

Status EnQueue(LinkQueue &Q,ElemType e)
{
    QNode *p;
    p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

链队的出队

Status DeQueue(LinkQueue &Q,ElemType &e)
{
    if(Q.front==Q.rear) return ERROR;
    QNode *p;
    p=Q.front->next;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
        delete p;
        return OK;
}

取队头元素

ElemType GetHead(LinkQueue Q)
{
    if(Q.front!=Q.rear)
        return Q.front->next->data;
}

栈的表示和操作的实现

顺序栈的表示和实现

链栈的表示和实现

队列的表示和操作的实现

循环队列—队列的顺序表示和实现

链队—队列的链式表示和实现