考研数据结构——栈和队列-蒲公英云

考研数据结构——栈和队列

怕什么前路太长，进一寸有一寸的欢喜

栈：是线性表。是只能在一端进行插入和删除的线性表。

栈的基本操作：

InitStack(&S):初始化
StackEmpty(S):判空
Push(&S,x)插入元素入栈
Pop(&S,&x)取出栈顶元素
GetTop(S,&x)读取栈顶元素
ClearStack(&S):销毁栈

顺序栈：

#define MaxSize 50
typedef struct{
    Elemtype data[MaxSize];
    int top;
}SqStack;
初始化：
void InitStack(&s){
    s.top = -1;
}
判空：
bool StackEmpty(S){
    if(S.top==-1) teturn true;
    else return false;
}
入栈：
bool Push(SqStack &S,Elemtype x){
    if(S.top==MaxSize-1) return false;
    S.data[++S.top] = x;
    teturn true;
}
出栈：
bool Pop(SqStack &S,Elemtype &x){
    if(S.top==-1) return false;
    x = S.data[S.top--];
    return true;
}

共享栈：两个栈空间相互调节，只有在整个存储空间被占满时才发生上溢。

链栈：不存在栈满上溢的情况，用单链表实现，所有操作都是在单链表表头进行，链栈没有头结点。

队列：是线性表，是从尾进从头出的线性表。

#define MaxSize 50
typedef struct{
    Elemtype data[MaxSize];   //队列是用数组定义的。
    int front,rear;
}SqQueue;
循环队列：
初始化：
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
}
判断空：
bool isEmpty(Q){
    if(Q.rear==Q.front) return true;
    else return false;
}
入队：
bool EnQueue(SqQueue &Q,Elemtype x){
    if((Q.rear+1)%MaxSize==Q.front) return false;
    Q.data[rear] = x;
    Q.rear = (Q.rear+1)%MaxSize;
    return true;
}
出队：
bool DeSqQueue(SqQueue &Q,Elemtype x){
    if(Q.rear==Q.front) return false;
    s = Q.data[rear];
    Q.rear = (Q.rear+1)%MaxSize;
    return true;
}

链队：带有头指针和尾指针的单链表。

链式存储定义：
typedef struct LinkNode{
    Elemtype data[];
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front,*rear;
}LinkQueue;
初始化：
void InitQueue(LinkQueue &Q){
    Q.front = ()malloc();
    Q.front->next = NULL;
}
判空：
bool IsEmpty(LinkQueue &Q){
    if(Q.front==Q.rear) return true;
    return false;
}
入队：
void InsertLinkQueue(LinkQueue &Q,Elemtype x){
    LinkNode *s;
    s = (LinkNode*)malloc(sizeof(LNode));
    s->data = x;
    Q.rear->next = s;
    Q.rear = s;
}
出队：
bool DeQueue (LinkQueue &Q,Elemtype e){
    if(Q.front==Q.rear) return false;
    LinkNode *p;
    p = Q.fornt->next;
    e = p->data;
    Q.front->next = p->next;
    if(p==Q.rear) Q.front=Q.rear;
    free(p);
    return true;
}