栈和队列基础知识

栈和队列

栈(Stack)

只允许在一端进行插入和删除操作的线性表，先进后出。本次只说明顺序存储实现栈。

初始化栈

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top; // top=-1 栈空,top=MaxSize-1 栈满
}SqStack;
void InitStack(SqStack &s) {
    s.top = -1;
}

判断栈为空

bool StackEmpty(SqStack s) {
    if (s.top == -1)
        return true;
    return false;
}

入栈

bool Push(SqStack &s, ElemType x) {
    if (s.top != MaxSize - 1) {
        s.data[++s.top] = x;
    }
}

出栈

bool Pop(SqStack &s,ElemType &m){
    if(!StackEmpty(s)){
        m = s.data[s.top--];
    }
}

队列(Queue)

也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，先进先出。插入元素称为入队，删除元素称为出队。队头（front）：允许删除的一端，又称队首。队尾（rear）：允许插入的一端。

循环队列数组实现

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; // 最大存储空间为MaxSize-1，留一个存储空间来判断循环队列是否满
    int front,rear;
} SqQueue;

初始化

void InitQueue(SqQueue &q) {
    q.front = q.rear = 0;
}

是否为空

bool IsEmpty(SqQueue q) {
    return q.front == q.rear;
}

入队

bool EnQueue(SqQueue &q, ElemType x) {
    if ((q.rear + 1) % MaxSize == q.front) {
        return false;
    }
    q.data[q.rear] = x;
    q.rear = (q.rear + 1) % MaxSize;
    return true;
}

出队

bool DeQueue(SqQueue &q, ElemType &e) {
    if (IsEmpty(q)) {
        return false;
    }
    e = q.data[q.front];
    q.front = (q.front + 1) % MaxSize;
    return true;
}

队列的链式存储

队列的链式表示称为链队列，实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

初始化

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode;
typedef struct {
    LNode *front;
    LNode *rear;
} LQueue;
void InitQueue(LQueue &q) {
    q.front = q.rear = (LNode *) malloc(sizeof(LNode));
    q.front->next = NULL;
}

判断为空

bool IsEmpty(LQueue q) {
    return q.front == q.rear;
}

入队

void EnQueue(LQueue &q, ElemType e) {
    LNode *p = (LNode *) malloc(sizeof(LNode));
    p->data=e;
    q.rear->next=p;
    q.rear=p;
    p->next=NULL;
}

出队

bool DeQueue(LQueue &q, ElemType &e) {
    if (IsEmpty(q)) {
        return false;
    }
    LNode *p = q.front->next;
    e=p->data;
    q.front->next = p->next;
    if (q.rear == p) {
        q.rear = q.front;
    }
    free(p);
    return true;
}