Stack and Queue的模板案例

#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
using namespace std;  
  
#define MaxSize 50  
#define InitSize 100  
  
typedef int ElemType;  
  
// 栈  
typedef struct {  
    ElemType data[MaxSize];         // 静态数组存放栈中元素  
    int top;                        // 栈顶指针  
}SqStack;  
  
// 初始化  
void InitStack(SqStack &S) {  
    S.top=-1;       // 初始栈顶指针(默认空栈为-1)  
}  
// 判断栈是否为空  
bool StackEmpty(SqStack S) {  
    if (S.top==-1)  
        return true;  
    else  
        return false;  
}  
// 进栈操作  
bool StackPush(SqStack &S, ElemType x) {  
    if (S.top == MaxSize-1)     // 栈满  
        return false;  
    S.data[++S.top]=x;          // 栈顶指针要先加 1 注意！！！！！  
    return true;  
}  
// 出栈操作  
bool StackPop(SqStack &S, ElemType &x) {  
    if (S.top==-1)      // 栈空  
        return false;  
    x=S.data[S.top--];  // 先出栈，栈顶指针再减 1 注意区别！！！！！  
    return true;  
}  
// 读取栈顶元素  
bool StackGetTop(SqStack S, ElemType &x) {  
    if (S.top==-1)  
        return false;  
    x=S.data[S.top];  
    return true;  
}  
  
// 栈的链式存储  
typedef struct LNode {  
    ElemType data;  
    struct LNode *next;  
}LNode, *LiStack;  
  
// 初始化  
void InitLinkStack(LiStack &L) {  
    L=NULL;  
}  
// 入栈  
bool LinkStackPush(LiStack &L, ElemType e) {  
    LNode *s=(LNode *)malloc(sizeof(LNode));  
    if (s==NULL)  
        return false;  
    s->next=L;  
    s->data=e;  
    L=s;  
    return true;  
}  
// 出栈  
bool LinkStackPop(LiStack &L, ElemType &e) {  
    if (L==NULL)  
        return false;  
    LNode *q=L;  
    e=q->data;  
    L=q->next;  
    free(q);  
    return true;  
}  
// 获取栈顶元素  
bool LinkStackGetTop(LiStack L, ElemType &e) {  
    if (L==NULL)  
        return false;  
    e=L->data;  
    return true;  
}  
  
// 队列  
typedef struct {  
    ElemType data[MaxSize];  
    int front, rear;  
}SqQueue;  
  
// 初始化  
void InitQueue(SqQueue &Q) {  
    Q.rear=Q.front=0;       // 队头,队尾指向0  
}  
// 判断队列是否为空(非循环队列)  
bool _isQueueEmpty(SqQueue Q) {  
    if (Q.rear==Q.front)  
        return true;  
    return false;  
}  
// 判断队列是否已满(非循环队列)不一定实用所有情况  
bool _isQueueFull(SqQueue Q) {  
    if (Q.rear-Q.front+1==MaxSize)  
        return true;  
    return false;  
}  
// 入队  
bool _EnQueue(SqQueue &Q, ElemType x) {  
    if(_isQueueFull(Q))      // 此处应该是判断队列是否满的操作,前面代码不一定实用所有情况  
        return false;  
    Q.data[Q.rear]=x;  
    Q.rear=Q.rear+1;  
    // Q.rear=(Q.rear+1)%MaxSize;  
    // 考虑把队列循环起来  
    return true;  
    /*  
     * 我们可以发现这种队列存储空间利用有限  
     * 当我们在入队的时候又有出队操作的时候  
     * 可以发现队尾指针 rear+1==MaxSize 的时候  
     * 我们会误以为队列已经满了  
     * front前面已经出队的位置没有能够充分利用  
     * 循环队列就出现了  
     */}  
// 判断队列是否为空  
bool isQueueEmpty(SqQueue Q) {  
    if (Q.rear==Q.front)  
        return true;  
    return false;  
}  
// 判断队列是否已满  
bool isQueueFull(SqQueue Q) {  
    if ((Q.rear+1)%MaxSize==Q.front)  
        return true;  
    return false;  
}  
// 入队  
bool EnQueue(SqQueue &Q, ElemType e) {  
    if (isQueueFull(Q))  
        return false;  
    Q.data[Q.rear]=e;  
    Q.rear=(Q.rear+1)%MaxSize;  
    return true;  
}  
// 出队  
bool DeQueue(SqQueue &Q, ElemType &x) {  
    if (isQueueEmpty(Q))  
        return false;  
    x=Q.data[Q.front];  
    Q.front=(Q.front+1)%MaxSize;  
    return true;  
}  
// 获取队头元素  
bool QueueGetHead(SqQueue Q, ElemType &x) {  
    if (isQueueEmpty(Q))  
        return false;  
    x=Q.data[Q.front];  
    return true;  
}  
  
// 队列的链式实现  
typedef struct QLNode {     // 链式队列的节点  
    ElemType data;  
    struct QLNode *next;  
}QLNode;  
  
typedef struct {            // 链式队列  
    QLNode *front, *rear;   // 队列的队头和队尾指针  
}LinkQueue;  
  
// 初始化(带头节点)  
void InitQueue_WithHeadNode(LinkQueue &Q) {  
    // 初始化的时候 front, rear 都指向头节点  
    Q.front=Q.rear=(QLNode *)malloc(sizeof(QLNode));  
    Q.front->next=NULL;  
}  
// 判断是否为空(带头节点)  
bool isLinkQueueEmpty_WithHeadNode(LinkQueue Q) {  
    if (Q.front==Q.rear)  
        return true;  
    return false;  
}  
// 初始化(不带头节点)  
void InitQueue_WithOutHeadNode(LinkQueue &Q) {  
    // 初始时 front, rear 都指向NULL  
    Q.front=NULL;  
    Q.rear=NULL;  
}  
// 判断是否为空(不带头节点)  
bool isLinkQueueEmpty_WithOutHeadNode(LinkQueue Q) {  
    if (Q.front==NULL)  
        return true;  
    return false;  
}  
// 入队(带头节点)  
void EnLQueue_WithHeadNode(LinkQueue &Q, ElemType x) {  
    QLNode *s=(QLNode *)malloc(sizeof(QLNode));  
    s->data=x;  
    s->next=NULL;  
    Q.rear->next=s;     // 新节点插入到 rear->next 节点之后  
    Q.rear=s;           // 修改 rear 指针;  
}  
// 入队(不带头节点)  
void EnLQueue_WithOutHeadNode(LinkQueue &Q, ElemType x) {  
    QLNode *s=(QLNode *)malloc(sizeof(QLNode));  
    s->data=x;  
    s->next=NULL;  
    if (Q.front==NULL) {    // 第一个元素特殊处理  
        Q.front=s;  
        Q.rear=s;  
    } else {  
        Q.rear->next=s;     // 新节点插入到 rear->next 节点之后  
        Q.rear=s;           // 修改 rear 指针  
    }  
}  
// 出队(带头结点)  
bool DeLQueue_WithHeadNode(LinkQueue &Q, ElemType &x) {  
    if (Q.front==Q.rear)  
        return false;       // 空队  
    QLNode *p=Q.front->next;  
    x=p->data;              // x 返回的是队头元素  
    Q.front->next=p->next;  // 头节点的 next 指向 p->next (该删除的的元素的下一个元素)  
    if (Q.rear==p)          // 如果是最后一个节点  
        Q.rear=Q.front;  
    free(p);  
    return true;  
}  
// 出队(不带头结点)  
bool DeLQueue_WithOutHeadNode(LinkQueue &Q, ElemType &x) {  
    if (Q.front==NULL)  
        return false;       // 队空  
    QLNode *p=Q.front;  
    x=p->data;  
    Q.front=p->next;  
    if (Q.rear==p) {  
        Q.front=NULL;  
        Q.rear=NULL;  
    }  
    free(p);  
    return true;  
}