数据结构与算法教程，数据结构C语言版教程！（第三部分、栈(Stack)和队列(Queue)详解）二

?第三部分、栈(Stack)和队列(Queue)详解

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 "一对一" 的数据，但由于它们比较特殊，因此将其单独作为一章，做重点讲解。

使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使用队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。

既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。

三、链栈及基本操作（包含入栈和出栈）详解

链栈，即用链表实现栈存储结构。

链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底，如图 1 所示：

图 1 链栈示意图

将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着：

• 在实现数据"入栈"操作时，需要将数据从链表的头部插入；
• 在实现数据"出栈"操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。

1、链栈元素入栈

例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中，每个数据元素的添加过程如图 2 所示：

图 2 链栈元素依次入栈过程示意图

C语言实现代码为：

//链表中的节点结构

typedef struct lineStack{

????????int data;

????????struct lineStack * next;

}lineStack;

//stack为当前的链栈，a表示入栈元素

lineStack* push(lineStack * stack,int a){

????????//创建存储新元素的节点

????????lineStack * line=(lineStack*)malloc(sizeof(lineStack));

????????line->data=a;

????????//新节点与头节点建立逻辑关系

????????line->next=stack;

????????//更新头指针的指向

????????stack=line;

????????return stack;

}

2、链栈元素出栈

例如，图 2e) 所示的链栈中，若要将元素 3 出栈，根据"先进后出"的原则，要先将元素 4 出栈，也就是从链表中摘除，然后元素 3 才能出栈，整个操作过程如图 3 所示：

图 3 链栈元素出栈示意图

因此，实现栈顶元素出链栈的 C 语言实现代码为：

//栈顶元素出链栈的实现函数

lineStack * pop(lineStack * stack){

????????if (stack) {

????????????????//声明一个新指针指向栈顶节点

????????????????lineStack * p=stack;

????????????????//更新头指针

???????????????? stack=stack->next;

????????????????printf("出栈元素：%d ",p->data);

????????????????if (stack) {

????????????????????????printf("新栈顶元素：%d\n",stack->data);

????????????????}else{

????????????????????????printf("栈已空\n");

????????????????}

????????????????free(p);

????????}else{

????????????????printf("栈内没有元素");

????????????????return stack;

????????}

????????return stack;

}

代码中通过使用 if 判断语句，避免了用户执行"栈已空却还要数据出栈"错误操作。

3、总结

本节，通过采用头插法操作数据的单链表实现了链栈结构，这里给出链栈及基本操作的C语言完整代码：

#include <stdio.h>

#include <stdlib.h>

typedef struct lineStack{

????????int data;

????????struct lineStack * next;

}lineStack;

lineStack* push(lineStack * stack,int a){

????????lineStack * line=(lineStack*)malloc(sizeof(lineStack));

????????line->data=a;

????????line->next=stack;

????????stack=line;

????????return stack;

}

lineStack * pop(lineStack * stack){

????????if (stack) {

????????????????lineStack * p=stack;

????????????????stack=stack->next;

????????????????printf("弹栈元素：%d ",p->data);

????????????????if (stack) {

????????????????????????printf("栈顶元素：%d\n",stack->data);

????????????????}else{

????????????????????????printf("栈已空\n");

????????????????}

????????????????free(p);

????????}else{

????????????????printf("栈内没有元素");

????????????????return stack;

????????}

????????return stack;

}

int main() {

????????lineStack * stack=NULL;

????????stack=push(stack, 1);

????????stack=push(stack, 2);

????????stack=push(stack, 3);

????????stack=push(stack, 4);

????????stack=pop(stack);

????????stack=pop(stack);

????????stack=pop(stack);

????????stack=pop(stack);

????????stack=pop(stack);

????????return 0;

}

程序运行结果为：

弹栈元素：4 栈顶元素：3
弹栈元素：3 栈顶元素：2
弹栈元素：2 栈顶元素：1
弹栈元素：1 栈已空
栈内没有元素

---

?四、[数据结构实践项目]进制转换器

进制转换器项目要求：用户提供需要转换的数据和该数据的进制，以及要转换的进制，进制转换器提供给用户最终的正确转换的结果。

1、转换器实例

例如，用户提供了一个十进制数：10，要求将此数据以二进制形式转换，则通过进制转换器转换的最终结果应该：1010。

提示：此进制转换器可以在 2-36 进制之间对数据进行任意转换。各进制中对应的数字如下表：

2、设计思路

当用户给定 2 - 36 进制中的任意一进制数时，最简单的方法是使用顺序存储结构进行存储，即使用字符串数组存储。

转化时，最直接的思路就是先将该数转化为十进制数据，然后再由十进制转化成要求的进制数，最终的结果用栈结构存储（先进后出），这样最终显示给用户的是正常的数据。

3、实现代码

#include <stdio.h>

#include <string.h>

#include <math.h>

int top=-1;//top变量时刻表示栈顶元素所在位置

void push(char * a,char elem){

????????a[++top]=elem;

}

void pop(char * a){

????????if (top==-1) {

????????????????return ;

????????}

????????//输出时要按照正确的格式显示给用户

????????if (a[top]>=10) {

????????????????printf("%c",a[top]+55);

????????}else{

????????????????printf("%d",a[top]);

????????}

????????top--;

}

//将各进制数转换成十进制数

int scaleFun(char * data,int system){

????????int k=(int)strlen(data)-1;

????????int system_10_data=0;

????????int i;

????????for (i=k; i>=0; i--) {

????????????????int temp;

????????????????if (data[i]>=48 && data[i]<=57) {

????????????????????????temp=data[i]-48;

????????????????}else{

????????????????????????temp=data[i]-55;

????????????????}

????????????????system_10_data+=temp*pow(system, k-i);

????????}

????????return system_10_data;

}

int main() {

????????char data[100];

????????printf("进制转换器，请输入原数据的进制（2-36）:");

????????int system;

????????scanf("%d",&system);

????????getchar();

????????printf("请输入要转换的数据：");

????????scanf("%s",data);

????????getchar();

????????int system_10_data=scaleFun(data, system);

????????printf("请输入转换后的数据的进制：");

????????int newSystem;

????????scanf("%d",&newSystem);

????????getchar();

????????while (system_10_data/newSystem) {

????????????????push(data,system_10_data%newSystem );

????????????????system_10_data/=newSystem;

????????}

????????push(data,system_10_data%newSystem);

????????printf("转换后的结果为：\n");

????????while (top!=-1) {

????????????????pop(data);

????????}

}

运行结果：

进制转换器，请输入原数据的进制（2-36）:10
请输入要转换的数据：100
请输入转换后的数据的进制：16
转换后的结果为：
64