第三部分、栈(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
