【数据结构】C语言顺序栈和链式栈的使用

1、栈的基本概念

栈是一种逻辑结构，是特殊的线性表。特殊在：

• 只能在固定的一端操作

只要满足上述条件，那么这种特殊的线性表就会呈现一种“后进先出”的逻辑，这种逻辑就被称为栈。
由于约定了只能在线性表固定的一端进行操作，于是给栈这种特殊的线性表的“插入”、“删除”，另起了下面这些特定的名称：

• 栈顶：可以进行插入删除的一端
• 栈底：栈顶的对端
• 入栈：将节点插入栈顶之上，也称为压栈，函数名通常为push()
• 出栈：将节点从栈顶剔除，也称为弹栈(出栈)，函数名通常为pop()
• 取栈顶：取得栈顶元素，但不出栈，函数名通常为top()

2、栈的存储形式

栈只是一种数据逻辑，如何将数据存储于内存则是另一回事。一般而言，可以采用顺序存储形成顺序栈，或采用链式存储形成链式栈。

3、示例代码：

(1) 顺序栈：

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

#define STACK_SIZE  10

typedef struct stack
{
    // 真实存放数据的数组
    int data[STACK_SIZE];
    // 记录目前栈顶位置
    int top;
}sq_stack_t;

// 初始化顺序栈
sq_stack_t *sq_stack_init(void)
{
    sq_stack_t *my_sqstack = malloc(sizeof(sq_stack_t));
    // 给top赋初值
    my_sqstack->top = -1;
    return my_sqstack;
}

// 入栈
int push(int new_data, sq_stack_t *sq_stack)
{
    // 判断栈是否已满-栈未满
    if (sq_stack->top < STACK_SIZE - 1)
    {
        /* 更新top */
        sq_stack->top++;
        sq_stack->data[sq_stack->top] = new_data;
        return 0;
    }
    // 栈满了
    else
    {
        printf("栈已满!\n");
        return -1;
    }
}

// 出栈
int pop(sq_stack_t *sq_stack)
{
    // 判断栈是否空了
    if (sq_stack->top >= 0)
    {
        // 先保存栈顶元素
        int temp = sq_stack->data[sq_stack->top];
        // 清除原栈顶元素值
        sq_stack->data[sq_stack->top] = 0;
        // 更新栈顶 
        sq_stack->top--;
        return temp;
    }
    else
    {
        printf("栈已空！\n");
        return -1;
    }
}

int main(int argc, char const *argv[])
{
    /* 初始化顺序栈 */
    sq_stack_t *my_sqstack = sq_stack_init();
    // 入栈
    push(1, my_sqstack);
    push(2, my_sqstack);
    push(3, my_sqstack);
    push(4, my_sqstack);
    push(5, my_sqstack);

    // 出栈
    int size = my_sqstack->top;
    for(int i = 0; i <= size; i++)
    {
        printf("出栈的数据：%d\n", pop(my_sqstack));
    }
    return 0;
}

/*
执行结果：
    出栈的数据：5
    出栈的数据：4
    出栈的数据：3
    出栈的数据：2
    出栈的数据：1

*/ 

(2) 顺序栈的应用：【十进制转二进制】

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

#define STACK_SIZE  10

typedef struct stack
{
    // 真实存放数据的数组
    int data[STACK_SIZE];
    // 记录目前栈顶位置
    int top;
}sq_stack_t;

// 初始化顺序栈
sq_stack_t *sq_stack_init(void)
{
    sq_stack_t *my_sqstack = malloc(sizeof(sq_stack_t));
    // 给top赋初值
    my_sqstack->top = -1;
    return my_sqstack;
}

// 入栈
int push(int new_data, sq_stack_t *sq_stack)
{
    // 判断栈是否已满-栈未满
    if (sq_stack->top < STACK_SIZE - 1)
    {
        /* 更新top */
        sq_stack->top++;
        sq_stack->data[sq_stack->top] = new_data;
        return 0;
    }
    // 栈满了
    else
    {
        printf("栈已满!\n");
        return -1;
    }
}

// 出栈
int pop(sq_stack_t *sq_stack)
{
    // 判断栈是否空了
    if (sq_stack->top >= 0)
    {
        // 先保存栈顶元素
        int temp = sq_stack->data[sq_stack->top];
        // 清除原栈顶元素值
        sq_stack->data[sq_stack->top] = 0;
        // 更新栈顶 
        sq_stack->top--;
        return temp;
    }
    else
    {
        printf("栈已空！\n");
        return -1;
    }
}

/*
    实现将键盘输入的任意整数转换成2进制保存到栈里面，然后打印出来
*/
int main(int argc, char const *argv[])
{
    int num = 0;
    /* 初始化顺序栈 */
    sq_stack_t *my_sqstack = sq_stack_init();
    // 入栈
    printf("请输入任一整数：");
    scanf("%d", &num);
    while (num != 0)
    {
        push(num % 2, my_sqstack);
        num /= 2;
    }


    // 出栈
    int size = my_sqstack->top;
    for(int i = 0; i <= size; i++)
    {
        printf("出栈的数据：%d\n", pop(my_sqstack));
    }

    return 0;
}

/*
执行结果：
    请输入任一整数：15
    出栈的数据：1
    出栈的数据：1
    出栈的数据：1
    出栈的数据：1

*/ 

(3) 链式栈

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

typedef struct list_stack
{
    // 数据域
    int data;
    // 指针域
    struct list_stack *next;
    // 记录当前栈顶位置
    struct list_stack *top;

}list_stack_t;

// 初始化链式栈
list_stack_t *list_stack_init(void)
{
    // 申请堆空间
    list_stack_t *list_stack = malloc(sizeof(list_stack_t));
    
    list_stack->next = NULL;
    list_stack->top = NULL;

    return list_stack;
}
// 入栈
int push(int new_data, list_stack_t *list_stack)
{
    // 给新节点申请堆空间
    list_stack_t *new_node = malloc(sizeof(list_stack_t));
    if (new_node == NULL)
    {
        return -1;
    }
    new_node->data = new_data;
    new_node->next = NULL;
    new_node->top = NULL;

    list_stack_t *p = list_stack;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = new_node;

    // 更新栈顶位置
    list_stack->top = new_node;
    
    return 0;
}

// 出栈
int pop(list_stack_t *list_stack)
{
    // 判断栈是否空了
    if (list_stack->next == NULL)
    {
        printf("栈已空\n");
        return -1;
    }
    
    // 保存栈顶元素值
    int temp = list_stack->top->data;
    // 删除栈顶节点
    list_stack_t *p = list_stack;
    while (p->next->next != NULL)
    {
        p = p->next;
    }
    p->next = NULL;
    free(list_stack->top);
    // 更新栈顶位置
    list_stack->top = p;

    return temp;
}

int main(int argc, char const *argv[])
{
    unsigned char i;
    list_stack_t * my_list_stack = list_stack_init();
    for (i = 0; i < 5; i++)
    {
        push(i, my_list_stack);
    }
    for (i = 0; i < 9; i++)
    {
        printf("出栈数据：%d\n", pop(my_list_stack));
    }

    return 0;
}

/*
执行结果：
    出栈数据：4
    出栈数据：3
    出栈数据：2
    出栈数据：1
    出栈数据：0
    栈已空
    出栈数据：-1
    栈已空
    出栈数据：-1
    栈已空
    出栈数据：-1
    栈已空
    出栈数据：-1

*/