数据结构PT2——堆栈/队列

一、堆栈（FILO）

堆栈是一种线性结构，也是一种特殊的线性表

1:堆栈的顺序存储实现

    栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#define MaxSize
typeof struct SNode *Stack
struct SNode{
    ElementType Data[MaxSize]
    int Top;
};

①入栈

void Push(Stack PtrS,ElementType item)
{
    if(PtrS -> Top == MaxSize - 1){
        printf("堆栈满");return}
    else
    {
        PtrS -> Data[++(PtrS -> Top)] = item;    //item到栈顶，先用再＋
        return;
     }
}

②出栈

void Pop(Stack PtrS)
{
    if(PtrS -> Top == - 1){
        printf("堆栈空");return ERROR;}
    else
    {
        return (PtrS -> Data[(PtrS -> Top)- -]);    //先减再用
     }
}

2:堆栈的链式存储实现

栈的链式存储结构实际上是一个单链表，叫链栈

typedef struct SNode *Stack;
struct SNode{
    ElementType Data;
    struct SNode *Next;
};

①堆栈初始化/是否为空

实际上是创建一个 堆栈的头节点，返回指针

Stack CreateStack(){
    Stack S;
    S = (Stack) malloc (sizeof(struct SNode));
    S -> Next = NULL;
    return S;
}

int IsEmpty(Stack S)
{
    return(S -> Next == NULL);
}

②入栈

void Push(ElementType item, Stack S)    //S是指向栈的指针，单纯是一个指针，并没有元素
{
    struct SNode *TmpCell;
    TmpCell = (struct SNode*) malloc(sizeof(struct SNode));    //创建新节点
    TmpCell -> Element = item;
    TmpCell -> Next =  S -> Next;    //S就如上定义，是一直指向栈顶的，S的Next是一直指向栈顶元素，这时候就是把有元素的Next指针指向了原栈顶元素
    S -> Next = TmpCell;    //然后栈顶指针S继续指向栈顶
}

③出栈

ElementType Pop(Stack S)
{
    struct SNode *FirstCell;    //指向该结构的指针
    ElementType TopElem;    //存储栈顶的值
    if(IsEmpty(S)){
        printf("堆栈空");return NULL;
    }
    else{
        FirstCell = S -> Next;    //拿一个临时指针来指向栈顶元素
        S -> Next = FirstCell -> Next;    //把S指向该栈顶的下一个元素
        TopElem = FirstCell -> Element;    //元素赋值给该Element变量
        free(FirstCell);    //释放临时指针
        return TopElem;
    }
}

二、队列（FIFO）

队列是一种手操作约束的线性表

1:队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front和一个记录队列尾位置的变量rear组成(加入元素，rear+1，删除元素，front+1)

#define MaxSize
struct QNode{
    ElementType Data[MaxSize];
    int rear;
    int front;
};
typedef struct QNode *Queue;

①入队列

void AddQ(Queue PtrQ,ElementAType item)
{
    if(PtrQ -> rear + 1) % MaxSize == PtrQ -> front){
       print("队列满");
       return;
    PtrQ -> rear = (PtrQ -> rear + 1)%MaxSize;
    PtrQ -> Data[PtrQ -> rear] = item;
}

②出队列

ElementType DeleteQ(Queue PtrQ)
{
    if(PtrQ -> front = = PtrQ -> rear){
        print("队列空");
        return ERROR;
    }else{
        PtrQ -> front = (PtrQ -> front + 1)%MaxSize;
        return PtrQ -> Data[PtrQ -> front];
    }
}

2：队列的链式存储实现

struct Node{
    ElementType Data;
    struct Node *Next;
};
struct QNode{
    struct Node *rear;    //指向队尾
    struct Node *front;    //指向队头
};
typedef struct QNode *Queue;
Queue PtrQ;

①入队

②出队

ElementType DeleteQ(Queue PtrQ)
{
    struct Node *FrontCell;
    ElementType FrontElem;
    if(PtrQ -> front = = NULL){
        printf("队列空");return ERROR;
    }
    if(PtrQ -> front = = PtrQ -> rear);
        PtrQ -> front = PtrQ -> rear = NULL;
    else
        PtrQ -> front = PtrQ -> front -> Next;
    FrontElem = FrontCell -> Data;
    free(FrontCell);
    return FrontElem;
}