栈和队列

栈

栈是一种只允许在一端插入和删除结点的线性表，允许被插入和删除的一端称为栈顶，另一端则称为栈底

顺序栈

定义数据元素的结构体和栈的结构体

// 栈中允许储存的元素的最大个数
#define MAX_LENGTH 100

// 栈中的数据元素
typedef int ElemType;

// Stack代表栈
typedef struct Stack {
    ElemType data[MAX_LENGTH];  // 存放栈中数据
    int top;                    // 指向栈顶元素的指针，初始值为-1
} Stack;

初始化栈

/**
 * 初始化栈
 * @param stack
 */
void initStack(Stack *stack) {
    // 该指针指向栈顶，初始值为-1
    // 由此，若栈中仅有一个元素时，该指针的值为0
    stack->top = -1;
}

判断栈是否为空

/**
 * 判断栈是否为空
 * @param stack
 * @return
 */
bool isEmpty(Stack stack) {
    return (stack.top == -1);
}

数据入栈

/**
 * 进栈
 * @param stack
 * @param elemType
 * @return
 */
bool push(Stack *stack, ElemType elemType) {
    // 判断栈是否已满
    if (stack->top == MAX_LENGTH - 1)
        return false;

    // 数据入栈
    stack->top++;
    stack->data[stack->top] = elemType;
    return true;
}

数据出栈

/**
 * 出栈
 * @param stack
 * @param elemType
 * @return
 */
bool pop(Stack *stack, ElemType *elemType) {
    // 判断栈是否为空
    if (stack->top == -1)
        return false;

    // 数据出栈
    *elemType = stack->data[stack->top];
    stack->top--;
    return true;
}

读取栈顶元素

/**
 * 仅读取栈顶元素，不做出栈
 * @param stack
 * @param elemType
 * @return
 */
bool getTop(Stack *stack, ElemType *elemType) {
    // 判断栈是否为空
    if (stack->top == -1)
        return false;

    // 取元素，但不出栈
    *elemType = stack->data[stack->top];
    return true;
}

共享栈

两个顺序栈共享一个一维数组的数据空间

定义数据元素的结构体和栈的结构体

// 栈中允许储存的元素的最大个数
#define MAX_LENGTH 100

// 栈中的数据元素
typedef int ElemType;

// Stack代表栈
typedef struct ShareStack {
    ElemType data[MAX_LENGTH];  // 存放共享栈的数据
    int top1;                   // 指向1号栈的栈顶顶元素，初始值为-1
    int top2;                   // 指向2号栈的栈顶顶元素，初始值为MAX_LENGTH
} ShareStack;

初始化栈

/**
 * 初始化栈
 * @param stack
 */
void initStack(ShareStack *stack) {
    stack->top1 = -1;
    stack->top2 = MAX_LENGTH;
}

判断栈是否为空

/**
 * 判断栈1是否为空
 * @param stack
 * @return
 */
bool Stack1Empty(ShareStack stack) {
    return (stack.top1 == -1);
}

/**
 * 判断栈2是否为空
 * @param stack
 * @return
 */
bool Stack2Empty(ShareStack stack) {
    return (stack.top1 == MAX_LENGTH);
}

数据入栈

/**
 * 进栈1
 * @param stack
 * @param elemType
 * @return
 */
bool push1(ShareStack *stack, ElemType elemType) {
    // 判断栈是否已满
    if (stack->top2 - stack->top1 == 1)
        return false;

    // 数据入栈
    stack->top1++;
    stack->data[stack->top1] = elemType;
    return true;
}

/**
 * 进栈2
 * @param stack
 * @param elemType
 * @return
 */
bool push2(ShareStack *stack, ElemType elemType) {
    // 判断栈是否已满
    if (stack->top2 - stack->top1 == 1)
        return false;

    // 数据入栈
    stack->top2--;
    stack->data[stack->top2] = elemType;
    return true;
}

数据出栈

/**
 * 出栈1
 * @param stack
 * @param elemType
 * @return
 */
bool pop1(ShareStack *stack, ElemType *elemType) {
    // 判断栈是否为空
    if (stack->top1 == -1)
        return false;

    // 数据出栈
    *elemType = stack->data[stack->top1];
    stack->top1--;
    return true;
}

/**
 * 出栈2
 * @param stack
 * @param elemType
 * @return
 */
bool pop2(ShareStack *stack, ElemType *elemType) {
    // 判断栈是否为空
    if (stack->top2 == MAX_LENGTH)
        return false;

    // 数据出栈
    *elemType = stack->data[stack->top2];
    stack->top2++;
    return true;
}

读取栈顶元素

/**
 * 仅读取栈1的栈顶元素，不做出栈
 * @param stack
 * @param elemType
 * @return
 */
bool getTop1(ShareStack *stack, ElemType *elemType) {
    // 判断栈是否为空
    if (stack->top1 == -1)
        return false;

    // 取元素，但不出栈
    *elemType = stack->data[stack->top1];
    return true;
}

/**
 * 仅读取栈2的栈顶元素，不做出栈
 * @param stack
 * @param elemType
 * @return
 */
bool getTop2(ShareStack *stack, ElemType *elemType) {
    // 判断栈是否为空
    if (stack->top2 == MAX_LENGTH)
        return false;

    // 取元素，但不出栈
    *elemType = stack->data[stack->top2];
    return true;
}

队列

顺序储存结构

定义数据元素的结构体和栈的结构体

// 队列中允许储存的元素的最大个数
#define MAX_LENGTH 100

// 数据元素
typedef int ElemType;

typedef struct Queue {
    ElemType data[MAX_LENGTH];  // 数据域
    int front, rear;            // 队头指针和队尾指针
} Queue;

初始化队列

void init(Queue *queue) {
    queue->front = 0;
    queue->rear = 0;
}

判断指定队列是否为空队

bool isEmpty(Queue queue) {
    return queue.front == queue.rear;
}

数据入队

bool enQueue(Queue *queue, ElemType elem) {
    // 判断是否队满
    if ((queue->rear + 1) % MAX_LENGTH == queue->front)
        return false;

    // 数据入队
    queue->data[queue->rear] = elem;
    queue->rear = (queue->rear + 1) % MAX_LENGTH;
    return true;
}

数据出队

bool deQueue(Queue *queue, ElemType *elem) {
    // 判断是否队空
    if (queue->front == queue->rear)
        return false;

    // 数据出队
    *elem = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_LENGTH;
    return true;
}

链式储存结构

带头指针的链式储存结构队列，链式储存结构的队列不限长度存入数据

定义数据元素的结构体和栈的结构体

// 数据元素
typedef int ElemType;

// 数据节点
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node;

// 代表队列
typedef struct {
    Node *front;    // 指向头结点
    Node *rear;     // 指向尾节点
} LinkQueue;

初始化队列

void init(LinkQueue *linkQueue) {
    linkQueue->front = (Node*)malloc(sizeof(Node));
    linkQueue->rear = linkQueue->front;

    linkQueue->front->next = NULL;
}

判断队列是否为空

bool isEmpty(LinkQueue linkQueue) {
    return linkQueue.front == linkQueue.rear;
}

数据入队

void enQueue(LinkQueue *linkQueue, ElemType elem) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = elem;
    newNode->next = NULL;

    // 新结点入链
    linkQueue->rear->next = newNode;
    linkQueue->rear = newNode;
}

数据出队

bool deQueue(LinkQueue *linkQueue, ElemType *elem) {
    if (linkQueue->rear == linkQueue->front)
        return false;

    Node *temp = linkQueue->front->next;
    *elem = temp->data;

    linkQueue->front->next = temp->next;

    // 如果是最后一个结点出队，重置尾节点
    if (linkQueue->rear == temp)
        linkQueue->rear = linkQueue->front;

    free(temp);

    return true;
}