数据结构与算法-线性结构篇（二）（C语言版）

栈

顺序表实现

#include <stdio.h>
#include <stdlib.h>

/**
 * 顺序表实现栈
 */
typedef struct Stack{
    int * arr;
    int capacity;
    // 表示栈顶位置
    int top;
} * StackArr;

/**
 * 初始化栈
 * @param stack
 */
void initStackArr(StackArr stack){
    // 分配内存
    stack->arr = malloc(sizeof (StackArr) * 10);
    stack->capacity = 10;
    // 栈为空时，默认为-1
    stack->top = -1;
}

/**
 * 入栈
 */
_Bool push(StackArr stack, int data) {
    // 满栈，需扩容
    if(stack->top == stack->capacity - 1) {
        int newCapacity = stack->capacity + (stack->capacity>>1);
        int * newArr = realloc(stack, sizeof(StackArr) * newCapacity);
        stack->arr = newArr;
        stack->capacity = newCapacity;
    }
    stack->arr[++stack->top] = data;
    return 1;
}

/**
 * 出栈
 */
int pop(StackArr stack) {
    // 栈为空
    if(stack->top == -1) {
        return INT_MAX;
    }
    return stack->arr[stack->top--];
}

void printStack(StackArr stack) {
    while(stack->top != -1) {
        printf("%d\t", pop(stack));
    }
}


int main() {
    struct Stack stack;
    initStackArr(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    printStack(&stack);
}

链表实现

#include <stdio.h>
#include <stdlib.h>

/**
 * 链表实现栈
 */
typedef struct StackNode{
    int data;
    struct StackNode * next;
} * StackLinkList;

/**
 * 初始化栈
 * @param stack
 */
void initStackLinkList(StackLinkList stackHead){
    stackHead->next = NULL;
}

/**
 * 入栈（头插法）
 */
_Bool push(StackLinkList stackHead, int data) {
    struct StackNode * newNode = malloc(sizeof (StackLinkList));
    newNode->data = data;
    newNode->next = stackHead->next;
    stackHead->next = newNode;
    return 1;
}

/**
 * 出栈
 */
int pop(StackLinkList stackHead) {
    struct StackNode * temp = stackHead->next;
    stackHead->next = temp->next;
    int data = temp->data;
    free(temp);
    return data;
}

void printStack(StackLinkList stackHead) {
    while(stackHead->next) {
        stackHead = stackHead->next;
        printf("%d\t", stackHead->data);
    }
}


int main() {
    struct StackNode stack;
    initStackLinkList(&stack);
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
    pop(&stack);
    printStack(&stack);
}

队列

顺序表实现

#include <stdio.h>
#include <stdlib.h>

/**
 * 顺序表实现循环队列
 */
typedef struct Queue{
    int * arr;
    // 队列的最大容量
    int capacity;
    // 队头，队尾
    int front, rear;
} * QueueArr;

/**
 * 初始化队列
 */
void initQueue(QueueArr queueArr){
    queueArr->arr = malloc(sizeof (int) * 10);
    queueArr->capacity = 10;
    // 牺牲一个存储单元
    queueArr->front = queueArr->rear = 0;
}

/**
 * 入队
 */
_Bool offerQueue(QueueArr queueArr, int data) {
    int currentRear = (queueArr->rear + 1) % queueArr->capacity;
    // 队列满
    if(currentRear == queueArr->front) {
        return 0;
    }
    queueArr->arr[currentRear] = data;
    queueArr->rear++;
    return 1;
}

/**
 * 出队
 */
int pollQueue(QueueArr queueArr) {
    // 队列空
    if(queueArr->front == queueArr->rear) {
        return INT_MAX;
    }
    queueArr->front = (queueArr->front + 1) % queueArr->capacity;
    return queueArr->arr[queueArr->front];
}

void printQueue(QueueArr queueArr){
    printf("<<< ");
    int i = queueArr->front;   //遍历队列需要从队首开始
    do {
        i = (i + 1) % queueArr->capacity;   //先向后循环移动
        printf("%d ", queueArr->arr[i]);  //然后打印当前位置上的元素
    } while (i != queueArr->rear);   //当到达队尾时，结束
    printf("<<<\n");
}

_Bool isEmpty(QueueArr queueArr) {
    return queueArr->front == queueArr->rear;
}


int main() {
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)) {
        printf("%d ", pollQueue(&queue));
    }
}

链表实现

#include <stdio.h>
#include <stdlib.h>

/**
 * 链表实现循环队列
 */
 // 节点
typedef struct Node{
    int data;
    struct Node * next;
} * LNode;

// 队列的头尾指针
typedef struct Queue {
    struct Node * front, * rear;
} * LQueue;

/**
 * 初始化队列
 */
void initQueue(LQueue queue, LNode lNode){
    // 头节点
    lNode = malloc(sizeof (LNode));
    // 队头和队尾指针都指向该头节点
    queue->front = queue->rear = lNode;
}

/**
 * 入队
 */
_Bool offerQueue(LQueue queue, int data) {
    LNode newNode = malloc(sizeof (LNode));
    if(newNode == NULL) {
        return 0;
    }
    newNode->data = data;
    newNode->next = NULL;
    queue->rear->next = newNode;
    queue->rear = newNode;
    return 1;
}

/**
 * 出队
 */
int pollQueue(LQueue queue) {
    // 队列空
    if(queue->front == queue->rear) {
        return INT_MAX;
    }
    LNode tempNode = queue->front->next;
    int data = tempNode->data;
    // 队列中只有一个元素，队尾需回到头节点
    if(tempNode->next == NULL) {
        queue->rear = queue->front;
    }
    queue->front->next = tempNode->next;
    free(tempNode);
    return data;
}

void printQueue(LQueue queue){
    printf("<<< ");
    LNode node = queue->front->next;
    while (node) {
        printf("%d ", node->data);
        if(node == queue->rear) break;    //当已经打印最后一个元素后，再结束
        else node = node->next;
    }
    printf("<<<\n");
}

_Bool isEmpty(LQueue lQueue) {
    return lQueue->front == lQueue->rear;
}




int main() {
    struct Queue queue;
    struct Node node;
    initQueue(&queue, &node);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)) {
        printf("%d ", pollQueue(&queue));
    }
}