一、栈

1、顺序栈（top=0）

1）定义

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top;
}SqStack;

2）初始化

void InitStack(SqStack& S) {
    S.top = 0;
}

3）判断是否为空

bool StackEmpty(SqStack S) {
    if (S.top == 0)
        return true;
    else
        return false;
}

4）进栈

bool Push(SqStack& S, ElemType x) {
    if (S.top == MaxSize)
        return false;
    S.data[S.top] = x;
    S.top++;
    return true;
}

5）出栈

bool Pop(SqStack& S, ElemType& x) {
    if (StackEmpty(S))
        return false;
    x = S.data[S.top - 1];
    S.top--;
    return true;
}

6）读栈顶元素

bool GetTop(SqStack S, ElemType& x) {
    if (StackEmpty(S))
        return false;
    x = S.data[S.top-1];
    return true;
}

2、共享栈

1)定义

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int top0;
    int top1;
}ShStack;

2)初始化

void InitStack(ShStack& S) {
    S.top0 = -1;
    S.top1 = MaxSize;
}

3、链栈（不带头结点）

1）定义

typedef int ElemType;
typedef struct Linknode{
    ElemType data;
    struct Linknode* next;
}Linknode, *LiStack;

2）初始化

void InitStack(LiStack& L) {
    L = NULL;
}

3）判断是否为空

bool StackEmpty(LiStack L) {
    if (L == NULL)
        return true;
    else
        return false;
}

4）进栈

bool Push(LiStack& L, ElemType x) {
    if (StackEmpty(L)) {
        L = (Linknode*)malloc(sizeof(Linknode));
        L->data = x;
        L->next = NULL;
        return true;
    }
    Linknode* s = (Linknode*)malloc(sizeof(Linknode));
    if (s == NULL)
        return false;
    s->data = x;
    s->next = L;
    L = s;
    return true;
}

5）出栈

bool Pop(LiStack& L, ElemType& x) {
    if (StackEmpty(L))
        return false;
    Linknode* temp = L;
    L = L->next;
    free(temp);
    return true;
}

二、队

1、顺序实现

1）定义

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

2）初始化队列（循环队列）

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

3）判空

bool QueueEmpty(SqQueue Q) {
    if (Q.front == Q.rear)
        return true;
    else
        return false;
}

4）判断队满

bool QueueFull(SqQueue Q) {
    if ((Q.rear + 1) % MaxSize == Q.front)
        return true;
    else
        return false;
}

5）入队

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

6）出队

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

2、链式实现（带头结点）

1）定义

typedef int ElemType;
typedef struct LinkNode{
    ElemType data;
    LinkNode* next;
}LinkNode;
typedef struct {
    LinkNode* front, * rear;
}LinkQueue;

2）初始化

void InitQueue(LinkQueue& Q) {
    Q.front = Q.rear = NULL;
}

3）判断空

bool IsEmpty(LinkQueue Q) {
    if (Q.rear == NULL)
        return true;
    else
        return false;
}

4）入队

bool EnQueue(LinkQueue& Q, ElemType x) {
    LinkNode* temp = (LinkNode*)malloc(sizeof(LinkNode));
    if (temp == NULL)
        return false;
    temp->data = x;
    temp->next = NULL;
    if (IsEmpty(Q) == true) {
        Q.front = Q.rear = temp;
        return true;
    }
    Q.rear->next = temp;
    Q.rear = temp;
    return true;
}

5）出队

bool DeQueue(LinkQueue& Q, ElemType& x) {
    if (IsEmpty(Q))
        return false;
    x = Q.front->data;
    LinkNode* temp = Q.front;
    Q.front = temp->next;
    free(temp);
    return true;
}

三、括号匹配（栈实现）

#include<stdlib.h>
#include<stdio.h>
#include "stacks.h"
bool bracketCheck(char str[], int length) {
    SqStack S;
    InitStack(S);
    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '{' || str[i] == '[')
            Push(S, str[i]);
        if (str[i] == '}' || str[i] == ')' || str[i] == ']') {
            if (StackEmpty(S))
                return false;
            char topElem;
            Pop(S, topElem);
            if (str[i] == ')' && topElem != '(')
                return false;
            if (str[i] == ']' && topElem != '[')
                return false;
            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }
    return StackEmpty(S);
}
int main() {
    char str[6] = { '(','{','}',')',']',')' };
    bool results = bracketCheck(str, 6);
    printf("%d", (int)results);
}