标签： 链表

C基于链表实现栈

本篇内容中的链表是之前的文章中实现的，请参阅文章 C-单链表的实现 。

栈的特性

先进后出（First-In-Last-Out, FILO）.

像队列实现一样，有2个主要的操作：

一）push 操作将元素入栈。

二）pop 操作将元素出栈。

栈的实现

基于单链表实现，push 入栈操作就是往链表的头部添加数据元素，pop 出栈操作就是从链表的头部删除数据元素。

以下是栈的定义以及主要操作：

// 定义栈
typedef LinkedList Stack;
// 初始化栈
void initStack(Stack *stack)
{
    init_linkedlist(stack);
}
// 入栈，在链表头部添加元素
void push(Stack *stack, void *data)
{
    addHead(stack, data);
}
// 出栈，从链表头部删除元素
void* pop(Stack *stack)
{
    pNode node = stack->head;
    void* data;
    if (stack->head == NULL) {
        data = NULL;
    } else if (stack->head == stack->tail) {
        stack->head = stack->tail = NULL;
        data = node->data;
        free(node);
    } else {
        stack->head = node->next;
        data = node->data;
        free(node);
    }

    return data;
}

示例说明

    Stack stack;
    // 初始化
    initStack(&stack);
    int a = 20;
    int b = 30;
    int c = 40;
    int *ptr_1 = &a;
    int *ptr_2 = &b;
    int *ptr_3 = &c;

    push(&stack, ptr_1);
    push(&stack, ptr_2);
    push(&stack, ptr_3);

    int *ptr = NULL;
    for (int i = 0; i < 3; i++)
    {
        ptr = (int *)pop(&stack);
        printf("Popped %d\n", *ptr);
    }

运行结果：

Popped 40
Popped 30
Popped 20

以上内容如有错误，欢迎留言指出交流或者关注公众号交流。

C基于链表实现队列

本章内容是基于上一篇文章单链表的实现 C-单链表的实现 。

队列是先进先出（First in First out）的线性数据结构. 通常有2个主要的操作：enqueue 和 dequeue。

enqueue操作是将元素添加到列队中。

dequeue操作是将元素从队列中移除。

链表经常用于队列的实现。enqueue 操作是从链表的头部（head）添加元素，dequeue 操作是从链表的尾部（tail）移除元素。

队列定义

定义队列和相关操作

// 定义队列
typedef LinkedList Queue;
// 初始化队列
void initQueue(Queue *queue)
{
    init_linkedlist(queue);
}

// 添加元素
void enqueue(Queue *queue, void *data) {
    addHead(queue, data);
}

// 移除元素
void* dequeue(Queue *queue) 
{
    pNode node = queue->head;
    void* data;
    if (queue->head == NULL){
        data = NULL;
    } else if (queue->head == queue->tail) {
        queue->head = queue->tail = NULL;
        data = node->data;
        free(node);
    } else {
        // 找到倒数第二个节点，由于之前实现的链表是单链表，只能这么找
        while (node->next != queue->tail)
        {
            node = node->next;
        }
        queue->tail= node;
        node = node->next;
        queue->tail->next = NULL;

        data = node->data;
        free(node);
    }

    return data;   
}

示例说明

    Queue queue;
    // 初始化
    initQueue(&queue);
    int a = 20;
    int b = 30;
    int c = 40;
    int *ptr_1 = &a;
    int *ptr_2 = &b;
    int *ptr_3 = &c;

    enqueue(&queue, ptr_1);
    enqueue(&queue, ptr_2);
    enqueue(&queue, ptr_3);

    void *data = dequeue(&queue);
    printf("Dequeued %d\n", *((int*) data));

    data = dequeue(&queue);
    printf("Dequeued %d\n", *((int*) data));

    data = dequeue(&queue);
    printf("Dequeued %d\n", *((int*) data));

结构打印：

Dequeued 20
Dequeued 30
Dequeued 40

以上内容，如有错误，欢迎留言交流或添加公众号交流。