栈和队列

Posted 2025-01-15 Updated 2025-01- 16

By Administrator

29~38 min read

栈（stack）是一种遵循先入后出（后入先出）逻辑的线性数据结构。

我们可以将栈类比为桌面上的一摞盘子，如果想取出底部的盘子，则需要先将上面的盘子依次移走。我们将盘子替换为各种类型的元素（如整数、字符、对象等），就得到了栈这种数据结构。

如图 5-1 所示，我们把堆叠元素的顶部称为“栈顶”，底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

栈的先入后出规则

使用链表实现栈数据结构

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

typedef struct node {
    int data;
    struct node* next;
} Node;

typedef struct linkedListStack {
    int size; // 栈长度
    Node* top; // 栈顶元素
} LinkedListStack;


// 初始化化栈
LinkedListStack* init() {
    LinkedListStack* stack = malloc(sizeof(LinkedListStack));
    stack->size = 0; // 初始化栈中还没有元素
    stack->top = NULL;
    return stack;
}

// 创建栈元素
Node* createElement(int data) {
    Node* element = malloc(sizeof(Node));
    element->data = data;
    element->next = NULL;

    return element;
}


// 获取栈长度
int size(LinkedListStack* stack) {
    if (stack == NULL) {
        return 0;
    }
    return stack->size;
}


// 栈 push 方法 （更换栈顶元素） --> 入栈
void push(LinkedListStack* stack, int data) {
    Node* newElement = createElement(data);

    // 原来栈顶的元素，被新的元素指向 
    newElement->next = stack->top;

    // 更新栈顶指向的元素
    stack->top = newElement;

    // 新增元素栈长度 + 1 
    stack->size++;
}


// 栈 pop 方法（删除栈顶元素 , 返回被删除元素的值） ---> 出站
int pop(LinkedListStack* stack) {

    // 保证栈中是存在元素的
    if (!stack) {
        return __INT_MAX__;
    }

    if (!size(stack)) {
        return __INT_MAX__;
    }


    Node* temp = stack->top;
    int res = temp->data;
    stack->top = stack->top->next;

    // 释放原来的栈顶元素
    free(temp);

    // 栈长度减 一 
    stack->size--;

    return res;
}



// 获取栈顶元素的数据
int peek(LinkedListStack* stack) {

    if (stack && stack->top) {
        return  stack->top->data;
    } else {
        return __INT_MAX__;
    }
}

// 销毁栈
/* void delLinkedListStack(LinkedListStack** stakc) {
    // 先一个一个的销毁栈的元素
    while ((*stakc)->top) {
        Node* temp = (*stakc)->top;
        (*stakc)->top = (*stakc)->top->next;
        free(temp);
    }
    // 释放栈空间
    if (*stakc != NULL) {
        free(*stakc);
        *stakc = NULL;
    }
}
 */



 // 销毁栈
void delLinkedListStack(LinkedListStack** stakc) {
    if (*stakc == NULL) return;

    // 一个元素一个元素的出站
    for (int i = 0; i < (*stakc)->size; i++) {
        pop(*stakc);
    }

    // 释放栈
    free(*stakc);
    *stakc = NULL;
}




int main(int argc, char const* argv[]) {
    LinkedListStack* stack = init();

    push(stack, 2);
    push(stack, 3);

    printf("1栈顶元素： %d \n", peek(stack));

    printf("被删除的元素：%d \n", pop(stack));

    printf("2栈顶元素： %d \n", peek(stack));

    printf("size =  %d \n", size(stack));

    delLinkedListStack(&stack);
    // printf("%d \n", stack->size);
    printf("%d \n", stack == NULL);

    return 0;
}

使用数组实现栈数据结构

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

#define MAX_SIZE 100

typedef struct arrayStack {
    // int top; // 栈顶指针
    int size; // 栈大小
    int* data; // 栈保存的数据
} ArrayStack;


// 初始化化栈
ArrayStack* init() {
    ArrayStack* stack = malloc(sizeof(ArrayStack));

    stack->size = 0; // 栈大小
    // stack->top = -1;  // 栈指针
    stack->data = malloc(sizeof(int) * MAX_SIZE); // 申请空间
    return stack;
}



// 获取栈长度
int size(ArrayStack* stack) {
    if (stack != NULL) {
        return stack->size;
    }
    return 0;
}


// 栈 push 方法 （更换栈顶元素） --> 入栈
void push(ArrayStack* stack, int data) {
    // stack->size++; // 栈长度加一 
    // stack->top++;  // 栈顶指针向前走一步
    // stack->data[stack->top] = data;


    stack->data[stack->size++] = data;
}


// 栈 pop 方法（删除栈顶元素 , 返回被删除元素的值） ---> 出站
int pop(ArrayStack* stack) {
    // int val = stack->data[stack->top];
    // stack->size--;
    // stack->top--;
    // return val;

    return stack->data[stack->size--];
}



// 获取栈顶元素的数据
int peek(ArrayStack* stack) {
    return stack->data[stack->size - 1];
}




// 销毁栈
void delLinkedListStack(ArrayStack** stakc) {
    free((*stakc)->data);
    free(*stakc);
    *stakc = NULL;
}


int main(int argc, char const* argv[]) {

    // 特点：头元素随着元素新增，而移动
    // 新增元素：新增到数组末尾
    ArrayStack* array = init();
    push(array, 1);
    push(array, 2);
    push(array, 3);
    push(array, 4);
    push(array, 5);
    peek(array);
    printf("栈顶元素：%d \n", peek(array));
    pop(array);
    printf("栈顶元素：%d \n", peek(array));
    return 0;
}

数组实现栈数据结构-nvcx.png

队列

链表实现队列数据结构

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

// 节点
typedef struct node {
    int data;
    struct node* next;
} Node;

// 创建节点
Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;

    return node;
}

// 队列结构体
typedef struct linkedListQueue {
    Node* top; // 对首
    Node* last; // 队尾
    int size; // 队列长度
} LinkedListQueue;


// 创建队列数据结构
LinkedListQueue* newLinkedListQueue() {
    LinkedListQueue* queue = malloc(sizeof(LinkedListQueue));
    queue->top = NULL; // 对首
    queue->last = NULL; // 队尾
    queue->size = 0;
    return queue;
}

// 队列：先进先出 ， 后进后出 , 从链表的尾部插入的新节点
void push(LinkedListQueue* queue, int data) {
    Node* newNode = createNode(data);
    if (queue->size == 0) {
        queue->top = newNode;
    } else {
        queue->last->next = newNode;
    }
    queue->last = newNode;
    queue->size++;

}


// 获取对首数据
int peek(LinkedListQueue* queue) {
    if (queue->size == 0) {
        perror("队列为空：");
        return -1;
    }
    return queue->top->data;
}

// 出队 --> 删除链表的头部元素
int pop(LinkedListQueue* queue) {
    if (queue->size == 0) {
        perror("队列为空：");
        return -1;
    }

    // 出队，就是对首指向，原来对首的下一个元素
    Node* temp = queue->top;
    int val = queue->top->data;
    queue->top = queue->top->next; // 对首移动了

    queue->size--; // 队列长度减一
    // 问题：当队列只有一个元素的时候 （ 对首和队尾都指向都应元素 ） , 
     // 如果只让对首往前走了一步， 队尾没有进行处理，队列就会成为一个野指针了，所以要对队尾进行处理
    if (queue->size == 0) {
        queue->last = NULL;
    }

    free(temp);
    return  val;
}

// 销毁队列
void delLinkedListQueue(LinkedListQueue** queue) {
    if ((*queue) == NULL || (*queue)->size == 0) {
        *queue = NULL;
        return;
    }

    // 不断更新对首，不断释放对首
    while ((*queue)->top != NULL) {
        Node* temp = (*queue)->top;
        (*queue)->top = (*queue)->top->next;
        free(temp);
    }

    // 释放队列的元素了 ， 释放队列 , 一旦队列这个结构体被释放掉，
    // 队列中的成员也就无法使用了（无需处理对尾）
    free(*queue);
    *queue = NULL;

}

/* 
链表队列特点：
 - 1. 先进先出
 - 2. 链表的队列使用 尾插 ， 获取元素从头获取元素
 - 3. 

 */
int main(int argc, char const* argv[]) {
    LinkedListQueue* queue = newLinkedListQueue();
    push(queue, 1);
    push(queue, 2);
    push(queue, 3);
    printf("对首数据: %d \n", peek(queue));

    printf("出队: %d \n", pop(queue));
    printf("出队: %d \n", pop(queue));
    // printf("出队: %d \n", pop(queue));
    delLinkedListQueue(&queue);
    printf("释放队列: %d \n", queue == NULL);



    return 0;
}

总结：

队列：先进先出。
从链表尾部插入新元素，获取元素的从头部开始获取。
链表的头节点也是存储

链表实现栈数据结构.png

环形数组实现队列数据结构

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5

// 队列结构体
typedef struct arrayQueue {
    int top;
    int last;
    int* data;
    int size; // 队列长度
} ArrayQueue;


// 创建队列数据结构
ArrayQueue* newArrayQueue() {
    ArrayQueue* queue = malloc(sizeof(ArrayQueue));
    queue->top = -1; // 刚开始初始化，队列的对首和队尾都都不指向任何元素
    queue->last = -1;
    queue->data = malloc(sizeof(int) * MAX_SIZE); // 存储数据的数组
    queue->size = 0;
    return queue;
}

// 队列：先进先出 ， 后进后出 ，
// 数组队尾当到了数组的末尾的时候需要将,队尾移动数组开头 也就是队尾移动后，队尾的值大于数组长度 , 就需要余数回到数组开头 ，循环
void push(ArrayQueue* queue, int data) {
    if (queue->size == MAX_SIZE) {
        perror("队列满了 ");
        return;
    }

    // 队尾下标移动
    // queue->last++;
    // if (queue->last >= MAX_SIZE) {
    //     queue->last = queue->last % MAX_SIZE; //回到数组头部
    // }

    queue->last = (queue->last + 1) % MAX_SIZE;
    queue->data[queue->last] = data;

    // 插入第一个元素的时候，对首就是队尾 （下标在同一个地方）
    if (queue->size == 0) {
        queue->top = queue->last;
    }
    // 队列长度+ 1 
    queue->size++;
}


// 获取对首数据
int peek(ArrayQueue* queue) {
    // 获取对首元素的数据
    if (queue->size) {
        return queue->data[queue->top];
    }
    perror("队列中没有数据了 \n");
    return -1;

}

// 出队 --> 删除链表的头部元素
int pop(ArrayQueue* queue) {
    if (queue->size == 0) {
        perror("队列为空 ");
        return -1;
    }

    // 获取对首元素
    int val = peek(queue);

    // // 对首指针往前移动
    // queue->top++;

    // // 判断头指针是否超过了整个数组的最大值 ，如果对首的下标超过了整个队列 ， 对首从新指向新的位置
    // if (queue->top >= MAX_SIZE) {
    //     queue->top = queue->top % MAX_SIZE;
    // }

    // 回到数组的 0 索引位置 , top 指针往前走和 queue.size-- ， 
    // 就可以控制队列通过方法只能访问到有效的数据（比如不在 top - last 管理范围的数据通过方法是获取不到的）
    queue->top = (queue->top + 1) % MAX_SIZE;
    queue->size--;
    return val;
}

// 销毁队列
void delLinkedListQueue(ArrayQueue** queue) {
    // 释放数组
    free((*queue)->data);
    // 释放队列
    free(*queue);

    *queue = NULL;
}

/*
链表队列特点：
 - 1. 先进先出
 */
int main(int argc, char const* argv[]) {
    ArrayQueue* queue = newArrayQueue();
    push(queue, 1);
    push(queue, 2);
    push(queue, 3);
    push(queue, 4);
    push(queue, 5);
    push(queue, 6);

    printf("对首的位置 %d \n", queue->top);
    printf("对尾的位置 %d \n", queue->last);

    printf("对首： %d \n", peek(queue));
    printf("数组元素：");
    for (int i = 0; i < MAX_SIZE; i++) {
        printf("%d ", queue->data[i]);
    }
    printf("\n");

    printf("出站：");
    while (queue->size) {
        printf("%d ", pop(queue));
    }
    printf("\n");

    delLinkedListQueue(&queue);
    printf("是否已经销毁：%d \n", queue == NULL);

    return 0;
}

数组实现栈数据结构.png

总结：

队列特点：先进先出，后进后出
push 入队的内容放在 last ，所以要控制 last 的值，last 不能超过整个数组的长度，如果超过了回到数组的 0 元素的位置填充新的数据
pop 出对获取的内容从 top ，所以要控制 top 的值， top 不能超过整个数组的长度，如果超过了回到数组的 0 元素的位置填充新的数据
当只有一个元素的的时候 top 和 last 都指向同一个元素
top 和 last 不能相等，一旦相等就代表队列已经满了。

栈和队列总结

栈：

先入后出（后入先出）
出栈和入栈都在同一端进行操作
数组实现栈：将新增的元素插入的数组的最后面（尾进尾出）
单向链表实现栈：将新增元素插入的头部（头进头出）

队列：

先进先出（后进后出）
出列和入列需要再不同的端进行操作。
循环数组实现队列：新元素从尾入列，从头出列
单向链表实现队列：需要有两个指针，一个指向对首，一个指向队尾，对首出队，队尾入列。

数据结构与算法

License: CC BY 4.0