栈的简介
栈是所有数据结构中最常用的之一，栈是一个行动受限的线性表。
它具有后进先出的特点，这一点区别于队列的先进先出。他仅允许插入栈首和弹出栈首的操作，不被允许任意的插入和清除。
基本的API
- push
- pop
- size
写栈结构的简单思路
已知栈是一个线性表，我们所能想到的第一个就是用链表来实现它。
链表是采用不连续的内存地址来存储数据，各个地址间用指针来相连。
链表节点基本的结构 ：
// 定义 Node 结构体
typedef struct Node {
int val;
struct Node* next;
} Node;
完整代码
#include <stdio.h>
#include <stdlib.h>
/*
* 用链表写出栈结构
* 栈结构具有的API：push, pop, size, sort(用来给链表根据数据重新排序),
*/
/*
* 基本流程：
* 一、写出链表
* 1. Node结构体；
* 2. linkedList 作为 Node 结构体的指针；
* 二、写出栈
* 1.主要API函数的编写；还需要写一个生成栈的函数；
* 2.测试
*/
// 定义 Node 结构体
typedef struct Node {
int val;
struct Node* next;
} Node;
// 定义linkedList 作为指向 Node 结构的指针
typedef Node* linkedList;
// 测试 Node 结构以及 linkedList 是否成功定义的函数
void testNode() {
Node node = {1, NULL};
// 输出结果 ： 1
printf("%d\n", node.val);
linkedList pointer = &node;
pointer->val = 2;
// 输出结果 ： 2
printf("%d\n", node.val);
}
// 生成一个栈的函数，返回一个 Node 类型的指针
linkedList gen_stack() {
// 生成一个头部，作为栈的入口
linkedList head = (linkedList) malloc(sizeof(Node));
// 头部无 val ，next指向 NULL；
head->next = NULL;
return head;
}
// 测试 gen_stack 的函数
void test_gen_stack() {
linkedList stack = gen_stack();
stack->val = 1;
// 输出 ： 1
printf("%d", stack->val);
}
// 打印 queue 的函数
void print_stack(const linkedList stack) {
// 从头部的下一个开始打印 val
linkedList current = stack->next;
while (current != NULL) {
printf("%d -> ", current->val);
// 指针指向下一个
current = current->next;
}
printf("%s", "NULL");
printf("\n");
}
// 生成一个节点的函数
linkedList gen_Node(int val) {
linkedList node = (linkedList) malloc(sizeof(Node));
node->val = val;
node->next = NULL;
return node;
}
// API : push 放到栈首
void push(linkedList stack, int val) {
// 生成一个节点
linkedList node = gen_Node(val);
// 栈首就是链接到头部的 next
// 储存原来头部的 next
linkedList tmp = stack->next;
// 将 node 连接
stack->next = node;
// node 的 next 接 tmp
node -> next = tmp;
}
// 测试 push 的函数
void test_push() {
linkedList stack = gen_stack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
// 打印 : 3 -> 2 -> 1 -> NULL
print_stack(stack);
}
// API : pop 弹出栈首的 Node 的 val
int pop(linkedList stack) {
linkedList origin = stack->next;
int val = origin->val;
stack->next = stack->next->next;
// 释放掉弹出的元素空间
free(origin);
return val;
}
// 测试 pop
void test_pop() {
linkedList stack = gen_stack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
int val = pop(stack);
// 打印 ：2 -> 1 -> NULL
print_stack(stack);
// 打印 ：3
printf("%d\n", val);
}
// API ：size 返回栈中元素的个数
int size(linkedList stack) {
int ret = 0;
linkedList current = stack->next;
while (current != NULL) {
ret++;
current = current->next;
}
return ret;
}
// 测试 size 函数
void test_size() {
linkedList stack = gen_stack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
// 输出 : 3
printf("%d\n", size(stack));
pop(stack);
// 输出 : 2
printf("%d\n", size(stack));
}
// API : sort 根据 val 从小到大排序 一般 stack 并不具备这个功能，写着玩的
void sort(linkedList stack) {
// 采用冒泡排序
int size_of_stack = size(stack);
int i;
for (i = size_of_stack - 1; i > 0; i--) {
linkedList current = stack->next;
while (current->next != NULL) {
// 需要交换的情况
if (current->val > current->next->val) {
int tmp = current->val;
current->val = current->next->val;
current->next->val = tmp;
}
current = current->next;
}
}
}
// 测试 sort 的函数
void test_sort() {
linkedList stack = gen_stack();
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);
sort(stack);
// 打印 : 1 -> 2 -> 3 -> 4 -> NULL
print_stack(stack);
}
// 测试汇总
void test() {
// testNode(); 测试通过
// test_gen_stack(); 测试通过
// test_push(); 测试通过
// test_pop(); 测试通过
// test_size(); 测试通过
// test_sort(); 测试通过
}
// 主函数
int main() {
test();
return 0;
}
代码需要注意的点
- 尽管该代码很简单，也应该尽量每写完一个函数就测试，确保每一个模块的正确性。
- 生成每一个节点都需要申请内存空间，栈弹出之后，一定记得将pop掉的节点的内存空间释放掉，否则会造成内存泄漏。
- 当你想在函数中改变某个参数的值时，就要将该参数的地址作为参数传入函数。
写代码遇到的问题
C语言没有对象，写出的“栈”无法像面向对象语言那样方便地使用。当然这很可能是我的见识不够的问题。
网友评论