考研408数据结构(栈与队列)

#include <stdio.h>

// 考研标准：栈的最大容量（可根据题目修改）
#define MaxSize 50

// 顺序栈结构体定义（考研必考写法）
typedef struct {
    // 静态数组存放栈元素
    int data[MaxSize];
    // 栈顶指针：指向栈顶元素（考研最常用定义方式）
    int top;
} SqStack;

// 1. 初始化栈（核心）
void InitStack(SqStack *S) {
    // 栈顶指针置为-1，表示空栈
    S->top = -1;
}

// 2. 判断栈是否为空
int StackEmpty(SqStack S) {
    // 栈顶为-1 → 空栈，返回1；否则返回0
    return S.top == -1;
}

// 3. 判断栈是否为满
int StackFull(SqStack S) {
    // 栈顶指向最后一个元素 → 栈满，返回1
    return S.top == MaxSize - 1;
}

// 4. 入栈操作（进栈）
int Push(SqStack *S, int e) {
    // 栈满，入栈失败
    if (StackFull(*S))
        return 0;

    // 栈顶指针先+1，再赋值
    S->data[++S->top] = e;
    // 入栈成功
    return 1;
}

// 5. 出栈操作（删除栈顶元素，用e返回值）
int Pop(SqStack *S, int *e) {
    // 栈空，出栈失败
    if (StackEmpty(*S))
        return 0;

    // 先取栈顶元素，栈顶指针再-1
    *e = S->data[S->top--];
    // 出栈成功
    return 1;
}

// 6. 取栈顶元素（不删除）
int GetTop(SqStack S, int *e) {
    // 栈空，取元素失败
    if (StackEmpty(S))
        return 0;

    *e = S.data[S.top];
    // 取元素成功
    return 1;
}

// 7. 销毁栈（静态栈无需free，仅重置指针即可）
void DestroyStack(SqStack *S) {
    S->top = -1;
}

// 主函数：测试栈的所有操作（考研答题可写可不写，建议写上）
int main() {
    // 定义一个栈
    SqStack S;
    // 初始化栈
    InitStack(&S);

    // 测试入栈
    Push(&S, 10);
    Push(&S, 20);
    Push(&S, 30);
    printf("入栈元素：10,20,30\n");

    // 测试取栈顶
    int topElem;
    GetTop(S, &topElem);
    printf("当前栈顶元素：%d\n", topElem);

    // 测试出栈
    int e;
    Pop(&S, &e);
    printf("出栈元素：%d\n", e);
    GetTop(S, &topElem);
    printf("出栈后栈顶元素：%d\n", topElem);

    // 测试判空
    if (StackEmpty(S))
        printf("栈为空\n");
    else
        printf("栈不为空\n");

    // 销毁栈
    DestroyStack(&S);
    return 0;
}

共享栈

基本概念

共享栈是一种利用同一块内存空间实现两个栈的数据结构。两个栈的栈底分别位于共享内存空间的两端，栈顶向中间生长。当两个栈顶相遇时，表示栈空间已满。

核心特性

空间高效利用

共享栈通过让两个栈共享同一块内存区域，避免了单独分配两块内存可能导致的浪费。尤其当两个栈的实际使用空间动态变化时，能更灵活地利用内存。

双向生长

两个栈的栈顶分别从数组的两端向中间延伸。栈A从下标0开始向高位生长，栈B从下标n-1开始向低位生长。

溢出条件

共享栈的溢出条件为两个栈顶相遇（即top1 + 1 >= top2）。此时无论向哪个栈压入元素都会导致栈满。

代码实现

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

// 共享栈最大容量（可根据需求修改）
#define MaxSize 10

// 共享栈结构体定义（408标准写法）
typedef struct {
	// 共享存储空间
	int data[MaxSize];
	// 栈1栈顶指针
	int top1;
	// 栈2栈顶指针
	int top2;
} ShareStack;

//==================== 基本操作 ====================//

// 1. 初始化共享栈
void InitStack(ShareStack *S) {
	// 栈1空栈状态
	S->top1 = -1;
	// 栈2空栈状态
	S->top2 = MaxSize;
}

// 2. 判断共享栈是否为空
// flag=1 判栈1空；flag=2 判栈2空
int StackEmpty(ShareStack S, int flag) {
	if (flag == 1) {
		// 栈1空返回1
		return S.top1 == -1;
	} else if (flag == 2) {
		// 栈2空返回1
		return S.top2 == MaxSize;
	}
	// 非法标记
	return -1;
}

// 3. 判断共享栈是否满
int StackFull(ShareStack S) {
	// 标准判满条件
	return S.top1 + 1 == S.top2;
}

// 4. 入栈操作
// flag=1 入栈1；flag=2 入栈2
int Push(ShareStack *S, int flag, int e) {
	// 栈满，入栈失败
	if (StackFull(*S)) {
		printf("共享栈已满，入栈失败！\n");
		return 0;
	}
	if (flag == 1) {
		// 栈1：先移动指针，再入栈
		S->data[++S->top1] = e;
	} else if (flag == 2) {
		// 栈2：先移动指针，再入栈
		S->data[--S->top2] = e;
	} else {
		printf("栈编号错误！\n");
		return 0;
	}
	return 1;
}

// 5. 出栈操作
// flag=1 出栈1；flag=2 出栈2，e保存出栈元素
int Pop(ShareStack *S, int flag, int *e) {
	if (flag == 1) {
		// 栈1空
		if (S->top1 == -1) {
			printf("栈1为空，出栈失败！\n");
			return 0;
		}
		// 先出栈，再移动指针
		*e = S->data[S->top1--];
	} else if (flag == 2) {
		// 栈2空
		if (S->top2 == MaxSize) {
			printf("栈2为空，出栈失败！\n");
			return 0;
		}
		// 先出栈，再移动指针
		*e = S->data[S->top2++];
	} else {
		printf("栈编号错误！\n");
		return 0;
	}
	return 1;
}

// 6. 获取栈顶元素（不删除）
int GetTop(ShareStack S, int flag, int *e) {
	if (flag == 1) {
		if (S.top1 == -1) return 0;
		*e = S.data[S.top1];
	} else if (flag == 2) {
		if (S.top2 == MaxSize) return 0;
		*e = S.data[S.top2];
	} else return 0;
	return 1;
}

//==================== 测试主函数 ====================//
int main() {
	ShareStack S;
	// 初始化
	InitStack(&S);
	int e;

	// 栈1入栈
	Push(&S, 1, 10);
	Push(&S, 1, 20);
	Push(&S, 1, 30);

	// 栈2入栈
	Push(&S, 2, 100);
	Push(&S, 2, 200);

	// 栈1出栈
	Pop(&S, 1, &e);
	printf("栈1出栈元素：%d\n", e);

	// 栈2出栈
	Pop(&S, 2, &e);
	printf("栈2出栈元素：%d\n", e);

	// 获取栈顶
	GetTop(S, 1, &e);
	printf("栈1栈顶元素：%d\n", e);
	GetTop(S, 2, &e);
	printf("栈2栈顶元素：%d\n", e);

	return 0;
}

链栈

基本概念

链栈是一种基于链表实现的栈结构，采用动态内存分配方式存储数据。与顺序栈不同，链栈无需预先定义固定容量，通过节点间的指针链接实现元素的入栈和出栈操作。链栈的栈顶通常为链表的头节点，操作均在链表头部完成，保证时间复杂度为 O(1)。

链栈的核心特性

动态扩展性
链栈的存储空间随需求动态分配，无需担心栈满问题（除非内存耗尽）。

高效操作
入栈和出栈仅需修改头节点指针，无需移动其他元素，操作效率稳定。

内存灵活性
每个节点独立分配内存，可分散存储，但需额外空间存储指针。

实现关键

栈顶指针指向链表头节点。
空栈时，栈顶指针为 NULL。
节点结构包含数据域和指向下一节点的指针域。

代码实现

带头结点的链栈

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

// 链栈结点类型定义
typedef struct StackNode {
	int data;
	struct StackNode *next;
} StackNode, *StackPtr;

// 链栈（仅需栈顶指针，指向头结点）
typedef struct {
	StackPtr top;  // 栈顶指针，指向头结点
} LinkStack;

// 1. 初始化带头结点的链栈
int InitStack(LinkStack *S) {
	// 创建头结点
	S->top = (StackPtr)malloc(sizeof(StackNode));
	if (S->top == NULL) return 0;  // 内存分配失败

	S->top->next = NULL;  // 头结点后继为空
	return 1;
}

// 2. 判断栈空
int StackEmpty(LinkStack S) {
	// 头结点后无元素即为空
	return S.top->next == NULL;
}

// 3. 入栈（头插法）
int Push(LinkStack *S, int e) {
	StackPtr p = (StackPtr)malloc(sizeof(StackNode));
	if (p == NULL) return 0;

	p->data = e;
	p->next = S->top->next;  // 新结点指向原第一个元素
	S->top->next = p;        // 头结点指向新结点
	return 1;
}

// 4. 出栈
int Pop(LinkStack *S, int *e) {
	if (StackEmpty(*S)) return 0;  // 栈空

	StackPtr p = S->top->next;  // p指向待删除结点
	*e = p->data;

	S->top->next = p->next;  // 摘链
	free(p);
	return 1;
}

// 5. 取栈顶元素（不删除）
int GetTop(LinkStack S, int *e) {
	if (StackEmpty(S)) return 0;
	*e = S.top->next->data;
	return 1;
}

// 6. 销毁栈
int DestroyStack(LinkStack *S) {
	StackPtr p, q;
	p = S->top;
	while (p != NULL) {
		q = p->next;
		free(p);
		p = q;
	}
	S->top = NULL;
	return 1;
}

// 测试主函数
int main() {
	LinkStack S;
	int e;

	InitStack(&S);

	Push(&S, 10);
	Push(&S, 20);
	Push(&S, 30);

	GetTop(S, &e);
	printf("栈顶元素：%d\n", e);

	Pop(&S, &e);
	printf("出栈元素：%d\n", e);

	GetTop(S, &e);
	printf("新栈顶：%d\n", e);

	printf("栈是否为空：%s\n", StackEmpty(S) ? "是" : "否");

	DestroyStack(&S);
	return 0;
}

不带头结点的链栈

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

typedef struct StackNode {
	int data;
	struct StackNode *next;
} StackNode, *StackPtr;

typedef struct {
	StackPtr top;
} LinkStack;

// 初始化
void InitStack(LinkStack *S) {
	S->top = NULL;
}

// 判空
int StackEmpty(LinkStack S) {
	return S.top == NULL;
}

// 入栈
int Push(LinkStack *S, int e) {
	StackPtr p = (StackPtr)malloc(sizeof(StackNode));
	if (!p) return 0;
	p->data = e;
	p->next = S->top;
	S->top = p;
	return 1;
}

// 出栈
int Pop(LinkStack *S, int *e) {
	if (StackEmpty(*S)) return 0;
	StackPtr p = S->top;
	*e = p->data;
	S->top = p->next;
	free(p);
	return 1;
}

// 取栈顶
int GetTop(LinkStack S, int *e) {
	if (StackEmpty(S)) return 0;
	*e = S.top->data;
	return 1;
}

// 销毁栈
void DestroyStack(LinkStack *S) {
	StackPtr p, q;
	p = S->top;
	while (p != NULL) {
		q = p->next;
		free(p);
		p = q;
	}
	S->top = NULL; // 销毁后置空，避免野指针
}

// 测试
int main() {
	LinkStack S;
	int e;

	InitStack(&S);

	Push(&S, 10);
	Push(&S, 20);
	Push(&S, 30);

	GetTop(S, &e);
	printf("栈顶：%d\n", e);

	Pop(&S, &e);
	printf("出栈：%d\n", e);

	DestroyStack(&S); // 用完销毁
	return 0;
}

顺序循环队列

基本概念

顺序循环队列是一种基于数组实现的队列结构，通过模运算（取余）实现队列空间的循环利用。与普通顺序队列相比，其核心优势是避免“假溢出”（即队列未满但因数组尾部空间耗尽无法入队的问题）。

逻辑环形结构：物理上使用线性数组存储，但通过指针的循环移动模拟环形结构。
队头（Front）与队尾（Rear）指针：分别标记队列的第一个元素位置和下一个待插入位置。
空队列与满队列的判定：需通过指针位置关系区分，通常牺牲一个存储单元或使用标志位。

核心特性

空间复用

通过取模运算实现指针循环移动。当指针到达数组末尾时，通过 (rear + 1) % capacity 回到数组起始位置。

判空与判满条件

判空：front == rear
判满：
- 牺牲一个单元法：(rear + 1) % capacity == front
- 标志位法：额外维护一个布尔变量标记队列状态。

时间复杂度

入队（Enqueue）：O(1)，仅修改 rear 指针并赋值。
出队（Dequeue）：O(1)，仅修改 front 指针。

代码实现

#include <stdio.h>

// 队列最大容量（考研固定写法）
#define MAXSIZE 100

// 循环队列结构体定义（408标准格式，一字不差）
typedef struct {
	int data[MAXSIZE];  // 静态数组存放元素
	int front;          // 队头指针：指向队头元素
	int rear;           // 队尾指针：指向队尾元素的下一个位置
} SqQueue;

//==================== 基本操作（考研必考6大函数）====================
// 1. 初始化队列
void InitQueue(SqQueue *Q) {
	Q->front = Q->rear = 0;  // 初始指针均为0，队列为空
}

// 2. 判断队列是否为空
int QueueEmpty(SqQueue Q) {
	// 空返回1，非空返回0
	return Q.front == Q.rear;
}

// 3. 入队操作：队尾插入元素e，成功返回1，失败返回0
int EnQueue(SqQueue *Q, int e) {
	// 队满判断（408标准条件）
	if ((Q->rear + 1) % MAXSIZE == Q->front)
		return 0;

	Q->data[Q->rear] = e;               // 元素存入队尾位置
	Q->rear = (Q->rear + 1) % MAXSIZE;  // 队尾指针循环后移
	return 1;
}

// 4. 出队操作：删除队头元素，用e返回值，成功返回1，失败返回0
int DeQueue(SqQueue *Q, int *e) {
	// 队空判断
	if (Q->front == Q->rear)
		return 0;

	*e = Q->data[Q->front];               // 取出队头元素
	Q->front = (Q->front + 1) % MAXSIZE;  // 队头指针循环后移
	return 1;
}

// 5. 读取队头元素（不删除）
int GetHead(SqQueue Q, int *e) {
	if (Q.front == Q.rear)
		return 0;
	*e = Q.data[Q.front];
	return 1;
}

// 6. 求队列长度（元素个数）
int QueueLength(SqQueue Q) {
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

// 主函数：测试循环队列所有功能
int main() {
	SqQueue Q;
	InitQueue(&Q);  // 初始化

	// 入队测试
	EnQueue(&Q, 10);
	EnQueue(&Q, 20);
	EnQueue(&Q, 30);

	printf("队列长度：%d\n", QueueLength(Q));  // 输出 3

	// 取队头
	int head;
	GetHead(Q, &head);
	printf("队头元素：%d\n", head);  // 输出 10

	// 出队测试
	int e;
	DeQueue(&Q, &e);
	printf("出队元素：%d\n", e);  // 输出 10

	printf("队列是否为空：%d\n", QueueEmpty(Q));  // 输出 0（非空）
	return 0;
}

链式队列

基本概念

链式队列是一种基于链表实现的队列数据结构，采用动态内存分配方式存储元素。与顺序队列（数组实现）不同，链式队列无需预先分配固定大小的存储空间，通过节点间的指针链接实现元素的动态增删。

节点结构：每个节点包含数据域（存储元素）和指针域（指向下一节点）。
队首与队尾：通过两个指针（front和rear）分别指向队列的首节点和尾节点，确保入队（enqueue）和出队（dequeue）操作的高效性。

核心特性

动态扩容
链式队列的容量理论上仅受系统内存限制，插入新元素时动态创建节点，无需考虑空间不足问题（假设内存充足）。
操作时间复杂度
- 入队操作：在队尾插入节点，时间复杂度为 O(1)。
- 出队操作：在队首删除节点，时间复杂度为 O(1)。
避免假溢出
顺序队列可能因数组空间固定导致“假溢出”（实际空间未满但无法插入），链式队列通过动态分配节点彻底解决此问题。
应用场景
适用于需要频繁动态增删数据的场景，如任务调度、消息缓冲等，尤其适合无法预估队列最大长度的场景。

代码实现

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

// 链式队列结点结构
typedef struct QNode {
	int data;
	struct QNode *next;
} QNode;

// 链队列 头尾指针封装结构
typedef struct {
	QNode *front;   // 队头指针（指向头结点）
	QNode *rear;    // 队尾指针（指向最后一个数据结点）
} LinkQueue;

// 1. 初始化链队列（带头结点 标准初始化）
void InitQueue(LinkQueue *Q) {
	// 建立头结点
	QNode *head = (QNode *)malloc(sizeof(QNode));
	head->next = NULL;
	Q->front = head;
	Q->rear  = head;
}

// 2. 判断队列是否为空
int QueueEmpty(LinkQueue Q) {
	// 带头结点判空条件：front == rear
	return Q.front == Q.rear;
}

// 3. 入队操作  成功返回1，失败返回0
int EnQueue(LinkQueue *Q, int e) {
	QNode *s = (QNode *)malloc(sizeof(QNode));
	if (s == NULL)
		return 0;

	s->data = e;
	s->next = NULL;

	Q->rear->next = s;  // 尾结点指向新结点
	Q->rear = s;        // rear后移
	return 1;
}

// 4. 出队操作  成功返回1，用e带出队头元素
int DeQueue(LinkQueue *Q, int *e) {
	if (QueueEmpty(*Q))
		return 0;

	QNode *p = Q->front->next;  // p指向第一个数据结点
	*e = p->data;

	Q->front->next = p->next;

	// 特殊：如果删除的是最后一个结点，rear要回指到头结点
	if (Q->rear == p)
		Q->rear = Q->front;

	free(p);
	return 1;
}

// 5. 获取队头元素（不删除）
int GetHead(LinkQueue Q, int *e) {
	if (QueueEmpty(Q))
		return 0;
	*e = Q.front->next->data;
	return 1;
}

// 6. 销毁队列（408拓展常考）
void DestroyQueue(LinkQueue *Q) {
	QNode *p, *q;
	p = Q->front;
	while (p != NULL) {
		q = p->next;
		free(p);
		p = q;
	}
	Q->front = Q->rear = NULL;
}

// 测试主函数
int main(void) {
	LinkQueue Q;
	InitQueue(&Q);

	EnQueue(&Q, 1);
	EnQueue(&Q, 2);
	EnQueue(&Q, 3);

	int val;
	GetHead(Q, &val);
	printf("队头元素：%d\n", val);

	DeQueue(&Q, &val);
	printf("出队元素：%d\n", val);

	DestroyQueue(&Q);
	return 0;
}

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能