数据结构：栈与队列详解及实现

数据结构：栈与队列详解及实现 | 极客日志

栈顶 → D → C → B → A ← 栈底 出栈顺序：D → C → B → A

特性	数组实现	链表实现
内存使用	连续内存空间	非连续内存空间
扩容成本	较高（需重新分配）	较低（动态分配）
访问速度	O(1) 随机访问	O(n) 顺序访问
缓存友好性	高	低
实现复杂度	简单	中等

typedef int STDataType;
typedef struct Stack {
    STDataType* _a; // 动态数组
    int _top;       // 栈顶位置
    int _capacity;  // 容量
} ST;

void STInit(ST* pst) {
    assert(pst);
    pst->a = 0;
    pst->capacity = 0;
    pst->top = 0;
}

void STDestroy(ST* pst) {
    assert(pst);
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

void STPush(ST* pst, STDataType x) {
    assert(pst);
    // 扩容
    if (pst->top == pst->capacity) {
        int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        // 起始空间为 0 则申请 4 个空间 不为 0 则二倍
        STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));
        // pst->a 为 NULL 时，realloc 相当与 malloc
        if (tmp == NULL) {
            perror("realloc fail");
        }
        pst->a = tmp;
        pst->capacity = newcapcacity;
    }
    pst->a[pst->top] = x;
    pst->top++; // top 指向栈顶下一个元素
}

void STPop(ST* pst) {
    assert(pst);
    pst->top--;
}

STDataType STTop(ST* pst) {
    assert(pst);
    assert(pst->top > 0); // top 大于 0 才能取
    return pst->a[pst->top - 1]; // top 是栈顶的下一个数据 所以要 -1
}

bool STEmpty(ST* pst) {
    assert(pst);
    return pst->top == 0; // ==0 就是空
}

int STSize(ST* pst) {
    assert(pst);
    return pst->top; // 也就是获取 top 因为这里的 top 相当于 size
}

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
int main() {
    ST s;
    STInit(&s);
    STPush(&s, 1);
    STPush(&s, 2);
    STPush(&s, 3);
    STPush(&s, 4);
    while (!STEmpty(&s)) {
        printf("%d ", STTop(&s));
        STPop(&s); // 打印一删除一个
    }
    STDestroy(&s);
    return 0;
}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int STDataType;
typedef struct Stack {
    STDataType* a;
    int top;
    int capacity;
} ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);

// 获取数据个数
int STSize(ST* pst);

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"

// 初始化和销毁
void STInit(ST* pst) {
    assert(pst);
    pst->a = 0;
    pst->capacity = 0;
    pst->top = 0;
}

void STDestroy(ST* pst) {
    assert(pst);
    free(pst->a);
    pst->a = NULL;
    pst->top = pst->capacity = 0;
}

// 入栈出栈
void STPush(ST* pst, STDataType x) {
    assert(pst);
    // 扩容
    if (pst->top == pst->capacity) {
        int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        // 起始空间为 0 则申请 4 个空间 不为 0 则二倍
        STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));
        // pst->a 为 NULL 时，realloc 相当与 malloc
        if (tmp == NULL) {
            perror("realloc fail");
        }
        pst->a = tmp;
        pst->capacity = newcapcacity;
    }
    pst->a[pst->top] = x;
    pst->top++; // top 指向栈顶下一个元素
}

void STPop(ST* pst) {
    assert(pst);
    pst->top--;
}

// 取栈顶数据
STDataType STTop(ST* pst) {
    assert(pst);
    assert(pst->top > 0);
    return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst) {
    assert(pst);
    return pst->top == 0; // ==0 就是空
}

// 获取数据个数
int STSize(ST* pst) {
    assert(pst);
    return pst->top;
}

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
int main() {
    ST s;
    STInit(&s);
    STPush(&s, 1);
    STPush(&s, 2);
    STPush(&s, 3);
    STPush(&s, 4);
    while (!STEmpty(&s)) {
        printf("%d ", STTop(&s));
        STPop(&s);
    }
    STDestroy(&s);
    return 0;
}

void funcA() {
    int a = 10; // 栈帧创建
    funcB();    // 返回后栈帧销毁
}

void funcB() {
    int b = 20; // 新栈帧
}

class BrowserHistory:
    def __init__(self):
        self.back_stack = [] # 后退栈
        self.forward_stack = [] # 前进栈

    def visit(self, url):
        self.back_stack.append(url)
        self.forward_stack = [] # 清空前进栈

    def back(self):
        if len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            return self.back_stack[-1]

public class TextEditor {
    private StringBuilder text = new StringBuilder();
    private Stack<String> history = new Stack<>();

    public void type(String words) {
        history.push(text.toString()); // 保存状态
        text.append(words);
    }

    public void undo() {
        if (!history.isEmpty()) {
            text = new StringBuilder(history.pop());
        }
    }
}

队头 → A → B → C → D → E ← 队尾 出队顺序：A → B → C → D → E

typedef int QDataType;
typedef struct QueueNode {
    struct QueueNode* next;
    QDataType val;
} QNode;

// 队列结构
typedef struct Queue {
    QNode* phead; // 队头指针
    QNode* ptail; // 队尾指针
    int size;     // 用来计数
} Queue;

// 用一个结构题体来放头节点跟尾节点，这样传参就可以只传一个

void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq) {
    assert(pq);
    QNode* cur = pq->phead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x) {
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return;
    }
    newnode->next = NULL;
    newnode->val = x;
    if (pq->ptail == NULL) {
        pq->phead = pq->ptail = newnode;
    } else {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    pq->size++;
}

void QueuePop(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    if (pq->phead->next == NULL) // 一个节点
    {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    } else // 多个节点
    {
        QNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;
}

int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}

QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    return pq->phead->val;
}

QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    return pq->ptail->val;
}

bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}

int main() {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    while (!QueueEmpty(&q)) {
        printf("%d ", QueueFront(&q)); // 取队头数据
        QueuePop(&q);
    }
    printf("\n");
    return 0;
}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;
typedef struct QueueNode {
    struct QueueNode* next;
    QDataType val;
} QNode;

typedef struct Queue {
    QNode* phead;
    QNode* ptail;
    int size;
} Queue;

// 初始化
void QueueInit(Queue* pq);
// 队列的销毁
void QueueDestroy(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 统计队列中数据的个数
int QueueSize(Queue* pq);
// 取队头数据
QDataType QueueFront(Queue* pq);
// 取队尾数据
QDataType QueueBack(Queue* pq);
// 判空
bool QueueEmpty(Queue* pq);

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"

void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x) {
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return;
    }
    newnode->next = NULL;
    newnode->val = x;
    if (pq->ptail == NULL) {
        pq->phead = pq->ptail = newnode;
    } else {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    pq->size++;
}

int QueueSize(Queue* pq) {
    assert(pq);
    return pq->size;
}

void QueuePop(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    if (pq->phead->next == NULL) // 一个节点
    {
        free(pq->phead);
        pq->phead = pq->ptail = NULL;
    } else // 多个节点
    {
        QNode* next = pq->phead->next;
        free(pq->phead);
        pq->phead = next;
    }
    pq->size--;
}

QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    return pq->phead->val;
}

QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(pq->phead);
    return pq->ptail->val;
}

bool QueueEmpty(Queue* pq) {
    assert(pq);
    return pq->size == 0;
}

void QueueDestroy(Queue* pq) {
    assert(pq);
    QNode* cur = pq->phead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
int main() {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    while (!QueueEmpty(&q)) {
        printf("%d ", QueueFront(&q)); // 取队头数据
        QueuePop(&q);
    }
    printf("\n");
    return 0;
}

public class MessageQueue {
    private Queue<Message> queue = new LinkedList<>();

    public synchronized void enqueue(Message msg) {
        queue.add(msg);
        notifyAll(); // 唤醒等待的消费者
    }

    public synchronized Message dequeue() throws InterruptedException {
        while (queue.isEmpty()) {
            wait(); // 等待消息到达
        }
        return queue.remove();
    }
}

class Printer:
    def __init__(self):
        self.print_queue = deque()
        self.current_task = None

    def add_document(self, document):
        self.print_queue.append(document)
        print(f"Added document: {document}")

    def print_next(self):
        if self.print_queue:
            self.current_task = self.print_queue.popleft()
            print(f"Printing: {self.current_task}")
        else:
            print("No documents to print")

void BFS(Graph* graph, int start) {
    bool visited[MAX_VERTICES] = {false};
    Queue queue;
    QueueInit(&queue);
    visited[start] = true;
    QueuePush(&queue, start);
    while (!QueueEmpty(&queue)) {
        int current = QueueFront(&queue);
        QueuePop(&queue);
        printf("Visited %d\n", current);
        // 遍历所有邻接节点
        for (int i = 0; i < graph->vertices; i++) {
            if (graph->adjMatrix[current][i] && !visited[i]) {
                visited[i] = true;
                QueuePush(&queue, i);
            }
        }
    }
}

struct Task {
    int pid;
    int priority; // 其他任务信息
};

void scheduleTasks(Queue* highPriority, Queue* normalQueue) {
    while (!QueueEmpty(highPriority) || !QueueEmpty(normalQueue)) {
        Task* task;
        // 优先处理高优先级队列
        if (!QueueEmpty(highPriority)) {
            task = QueueFront(highPriority);
            QueuePop(highPriority);
        } else {
            task = QueueFront(normalQueue);
            QueuePop(normalQueue);
        }
        executeTask(task); // 任务未完成则重新入队
        if (!task->completed) {
            if (task->priority == HIGH) {
                QueuePush(highPriority, task);
            } else {
                QueuePush(normalQueue, task);
            }
        }
    }
}

特性	栈 (Stack)	队列 (Queue)
操作原则	LIFO (后进先出)	FIFO (先进先出)
插入位置	栈顶 (Top)	队尾 (Rear)
删除位置	栈顶 (Top)	队头 (Front)
典型操作	Push, Pop	Enqueue, Dequeue
实现方式	数组 (更优)/链表	链表 (更优)/循环数组
空间复杂度	O(n)	O(n)
时间复杂度	Push/Pop: O(1)	Enqueue/Dequeue: O(1)
应用场景	函数调用、表达式求值、回溯	消息传递、BFS、缓冲、调度
抽象层次	递归结构	管道结构

typedef struct DequeNode {
    int data;
    struct DequeNode* prev;
    struct DequeNode* next;
} DequeNode;

typedef struct {
    DequeNode* front;
    DequeNode* rear;
} Deque;

// 前端插入
void insertFront(Deque* dq, int data) {
    DequeNode* newNode = createNode(data);
    if (dq->front == NULL) {
        dq->front = dq->rear = newNode;
    } else {
        newNode->next = dq->front;
        dq->front->prev = newNode;
        dq->front = newNode;
    }
}

// 后端删除
int deleteRear(Deque* dq) {
    if (dq->rear == NULL) return -1; // 错误值
    DequeNode* temp = dq->rear;
    int data = temp->data;
    if (dq->front == dq->rear) {
        dq->front = dq->rear = NULL;
    } else {
        dq->rear = dq->rear->prev;
        dq->rear->next = NULL;
    }
    free(temp);
    return data;
}

typedef struct {
    int* heap;      // 堆数组
    int capacity;   // 最大容量
    int size;       // 当前大小
} PriorityQueue;

void enqueue(PriorityQueue* pq, int value) {
    if (pq->size == pq->capacity) {
        // 扩容逻辑
    }
    // 将新元素添加到堆尾
    int i = pq->size++;
    pq->heap[i] = value;
    // 上滤操作
    while (i != 0 && pq->heap[(i - 1) / 2] > pq->heap[i]) {
        swap(&pq->heap[i], &pq->heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

int dequeue(PriorityQueue* pq) {
    if (pq->size <= 0) return INT_MIN;
    int root = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    // 下滤操作
    int i = 0;
    while (true) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < pq->size && pq->heap[left] < pq->heap[smallest]) smallest = left;
        if (right < pq->size && pq->heap[right] < pq->heap[smallest]) smallest = right;
        if (smallest != i) {
            swap(&pq->heap[i], &pq->heap[smallest]);
            i = smallest;
        } else {
            break;
        }
    }
    return root;
}

数据结构：栈与队列详解及实现

栈与队列：数据结构中的双生花

1. 栈：后进先出的有序世界

1.1 概念及结构剖析

1.2 实现方式深度解析

数组 vs 链表实现

1.3 动态栈实现详解（附程序源码）

1. 定义一个动态栈

2. 初始化

3. 销毁

4. 入栈

5. 出栈

6. 取栈顶数据

7. 判空

8. 获取数据个数

9. 访问栈

10. 程序源码

1.4 栈的应用场景

1. 函数调用栈

2. 表达式求值

3. 浏览器历史记录

4. 撤销操作（Undo）

2. 队列：先进先出的公平之师

2.1 概念及结构剖析

2.2 实现方式

为什么链表实现更优？

2.3 队列实现详解 (附程序源码)

核心数据结构定义

1. 初始化

2. 队列的销毁

3. 队尾插入

4. 队头删除

5. 统计队列中数据个数

6. 取队头数据

7. 取队尾数据

8. 判空

9. 访问队列

10. 程序源码

2.4 队列的应用场景

1. 消息队列系统

2. 打印机任务调度

3. 广度优先搜索（BFS）

4. CPU 任务调度

3. 栈与队列的对比分析

4. 高级变体与应用

4.1 双端队列（Deque）

4.2 优先队列（Priority Queue）

5. 总结：选择合适的数据结构

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具