一，栈的定义与操作基础
栈是一种尽可以在一端进行插入和删除运算的限定线性表，栈中能被插入的一端为栈顶，最底部的一端为栈底，如图：
由图可知，栈其实就像一个管道，只能从后往前依次插入或取出，不能从其它位置进行操作，是一种具有限制操作的线性表。
栈既然属于线性表，那么它也有属于自已的基础操作，而栈的基础操作如下：
（1）向栈顶插入数据
（2）从栈顶取出数据
（3）删除栈顶元素
（4）判断栈是否为空
只要是属于栈结构，无论是什么栈类型，基本都需要这几种操作，而复杂的问题基本是以这几种基础算法为操作进行的。下面我会详细的跟大家介绍。
二，栈的顺序栈
顺序栈跟顺序表的结构差不多，是以数组为形式构成的一种结构，也是栈的基本结构之一，
顺序栈的基本形式如下：
typedef int Datatype;
struct stack
{
Datatype a[100];
int top;//top作为栈顶指针，用来指向数据的位置
};
其中，用结构体中的a数组来存放数据，整个框架就是一个顺序栈，由此课看出，顺序栈与顺序表几乎一样，只是顺序栈被限制了数据元素的位置。
下面是顺序栈的基本操作算法，在以后的运用栈中可根据以下作为基础。
#include<stdio.h>
#include<stdlib.h>
#define max 100
typedef int type;
typedef struct set//顺序栈的结构式
{
type a[max];
int top;//栈顶指针
}stack;
stack* add(stack* s, type n)//顺序栈的入栈算法
{
if (s->top == max)
{
puts("栈已满，不能添加");
return 0;
}
else
s->a[s->top++] = n;
return s;
}
stack* spill(stack* s, type m)//顺序栈的溢出算法
{
if (s->top == 0)
{
puts("顺序栈内无任何数据元素");
return 0;
}
else
s->top--;
return s;
}
type take(stack* s)//取栈顶元素算法
{
type n;
if (s->top == 0)
{
puts("顺序栈无任何元素");
return 0;
}
else
n = s->a[s->top - 1];
return n;
}
void determine(stack* s)//判断算法
{
if (s->top == 0)
puts("顺序栈为空栈");
else
puts("顺序栈不为空栈");
}
int main()
{
stack* s;
s = (stack*)malloc(sizeof(stack));//建立顺序栈s
if (!s)
puts("空间不足，建立失败");
else
s->top = 0;
//入栈操作
type n;
scanf("%d", &n);
s = add(s, n);
//出栈操作
type m;
scanf("%d", &m);
s = spill(s, m);
//取栈顶元素操作
type x;
x = take(s);
//判别是否空栈
determine(s);
return 0;
}
三，栈的链式栈
栈的链式栈与链式表的关系跟栈的顺序栈与顺序表的关系相同，除了在元素位置上被限制外没有其它的异处，在这里就不做过多说明，而链式栈的基本结构如下：
typedef int Datatype;
struct stack
{
Datatype a;
struct stack* next;
};
而链式栈的基本操作流程如下：
stack* push(stack* s, type x)//入栈算法
{
stack* p;
p = (stack*)malloc(sizeof(stack));
p->data = x;
p->next = s;
s = p;
return s;
}
stack* deletdata(stack* s)//出栈算法
{
stack* p;
p = (stack*)malloc(sizeof(stack));
p = s;
s = s->next;
free(p);
return s;
}
Datatype Gettopdata(stack* pa)//得到栈顶元素算法
{
Datatype a;
a = pa->data;
//不能pa = pa->next进行查找;因为只是在子程序内部进行，出了子程序就销毁
return a;
}
要说明的是，链式栈不必设置头结点，因为链式栈在算法中操作是用地址进行的，在链式栈中很容易造成程序上的链接错误，并且栈顶的操作还比较频繁。
·由以上可知，链式栈的操作虽然比顺序栈稍微复杂一点，但链式栈中的元素变化数量较大，并链式栈一般也不会出现栈满情况，因此，在栈的结构中，链式栈是首选的存储方式。
四，栈的综合运用
讲解完栈的基础之后，接下来我们要考虑的这东西学完之后怎么用，在什么情况下运用。从以上对栈的认识上看，不难发现，凡问题求解具有后进先出的天然特性，其求解过程中必然需要利用栈。下面我来跟大家讲解几道例题，让大家学会如何更好的利用栈。
（1）链式栈的十进制的转换问题
#include<stdio.h>
#include<stdlib.h>
typedef struct set//建立链式栈
{
int data;
struct set* next;
}stack;
stack* reverse(stack* head)//逆序算法，将其全部逆序排列
{
stack* p, * pa, * pp;
pa = head;
p = head->next;
head->next = 0;
while (p->next)
{
pp = p->next;
p->next = pa;
pa = p;
p = pp;
}
return pa;
}
stack* change(int n, int m)
{
int x = 0;
stack* head = 0, * p = 0, * pa = 0;
head = p = (stack*)malloc(sizeof(stack));
do
{
x = n % m;
p->data = x;
pa = (stack*)malloc(sizeof(stack));
p->next = pa;
p = pa;
n /= m;
} while (n);
p->next = 0;
return reverse(head);
}
int main()
{
int n, m;
stack* p;
scanf("%d%d", &n, &m);//n代表数，m代表转换的进制
for (p = change(n, m);; p = p->next)
{
if (!p->next)
{
printf("%d", p->data);
break;
}
else
printf("%d->", p->data);
}
return 0;
}
（2）括号匹配问题
#include<stdio.h>
#include<stdlib.h>
typedef char type;
typedef struct note stack;
struct note
{
type data;
struct note* next;
};
stack* push(stack* s, type x)//入栈算法
{
stack* p;
p = (stack*)malloc(sizeof(stack));
p->data = x;
p->next = s;
s = p;
return s;
}
stack* deletdata(stack* s)//出栈算法
{
stack* p;
p = (stack*)malloc(sizeof(stack));
p = s;
s = s->next;
free(p);
return s;
}
int main()
{
stack* s;
type a[100];
int i = 0;
s = (stack*)malloc(sizeof(stack));//建立链式栈
s->data = 0;
fgets(a, 100, stdin);
while (a[i])//下面程序反复调用算法
{
switch (a[i])
{
case '(':
case '[':
case '{':
s = push(s, a[i]);
break;
case ')':
if (s->data == '(')
s = deletdata(s);
else
{
puts("匹配失败");
return 0;
}
break;
case ']':
if (s->data == '[')
s = deletdata(s);
else
{
puts("匹配失败");
return 0;
}
break;
case '}':
if (s->data == '{')
s = deletdata(s);
else
{
puts("匹配失败");
return 0;
}
break;
}
i++;
}
puts("匹配成功");
return 0;
}
（3）用顺序栈来实现逆置单向链表
#include<stdio.h>
#include<stdlib.h>
#define max 100
typedef int Datatype;
typedef struct note//定义单向链式表
{
Datatype a;
struct note* next;
}link;
typedef struct set//定义顺序栈
{
Datatype a[max];
int Topdata;
}stack;
link* creat()//创建单链表
{
link* p, * head, * pa;
p = (link*)malloc(sizeof(link));
head = pa = (link*)malloc(sizeof(link));
pa->next = p;
fscanf(stdin, "%d", &p->a);
while (p->a)
{
pa = p;
p = (link*)malloc(sizeof(link));
fscanf(stdin, "%d", &p->a);
pa->next = p;
}
pa->next = 0;
return head;
}
void linkprint(link* head)//输出单向链表
{
link* p;
for (p = head->next; p; p = p->next)
{
if (!p->next)
fprintf(stdout, "%d\n", p->a);
else
fprintf(stdout, "%d->", p->a);
}
}
void push(stack* pa, Datatype a)
{
pa->Topdata++;
pa->a[pa->Topdata - 1] = a;
}
Datatype Gettopdata(stack* pa)
{
return pa->a[--pa->Topdata];
}
void stackprint(stack* pa)
{
int i;
for (i = pa->Topdata; i; i--)
{
if (i == 1)
fprintf(stdout, "%d\n", pa->a[i - 1]);
else
fprintf(stdout, "%d->", pa->a[i - 1]);
}
}
int main()
{
link* p, * s;
s = creat();
fprintf(stdout, "单向链表的数据域: ");
linkprint(s);
stack* pa;
pa = (stack*)malloc(sizeof(stack));
pa->Topdata = 0;
//然后用栈实现逆置，首先将数据放入顺序栈中
for (p = s->next; p; p = p->next)
push(pa, p->a);
fprintf(stdout, "此时栈中的元素: ");
stackprint(pa);//输出栈中的元素，检查是否将单链表中的数据元素放到了栈中
//然后出栈从前到后的顺序放入链表中，即实现逆置运算
for (p = s->next; p; p = p->next)
p->a = Gettopdata(pa);
fprintf(stdout, "用栈逆置后的链表: ");
linkprint(s);
return 0;
}
（4）用链式栈来实现逆置单向链表
#include<stdio.h>
#include<stdlib.h>
#define max 100
typedef int Datatype;
typedef struct note//定义单向链式表{
Datatype a;
struct note* next;
}link;
typedef struct set//定义顺序栈{
Datatype data;
struct set* next;
}stack;
link* creat()//创建单链表{
link* p, * head, * pa;
p = (link*)malloc(sizeof(link));
head = pa = (link*)malloc(sizeof(link));
pa->next = p;
fscanf(stdin, "%d", &p->a);
while (p->a)
{
pa = p;
p = (link*)malloc(sizeof(link));
fscanf(stdin, "%d", &p->a);
pa->next = p;
}
pa->next = 0;
return head;
}
void linkprint(link* head)//输出单向链表{
link* p;
for (p = head->next; p; p = p->next)
{
if (!p->next)
fprintf(stdout, "%d\n", p->a);
else
fprintf(stdout, "%d->", p->a);
}
}
stack* push(stack* pa, Datatype a)
{
stack* p;
p = (stack*)malloc(sizeof(stack));
p->data = a;
p->next = pa;
return p;
}
void stackprint(stack* pa)
{
stack* p;
for (p = pa; p->next; p = p->next)
{
if (!p->next->next)
printf("%d\n", p->data);
else
printf("%d->", p->data);
}
}
Datatype Gettopdata(stack* pa)
{
//不能pa = pa->next进行查找;因为只是在子程序内部进行，出了子程序就销毁return pa->data;
}
int main()
{
link* p, * s;
s = creat();
fprintf(stdout, "单向链表的数据域: ");
linkprint(s);
stack* pa;
pa = (stack*)malloc(sizeof(stack));//建立链式栈pa->next = 0;
for (p = s->next; p; p = p->next)//将数据放入链式栈中pa = push(pa, p->a);
fprintf(stdout, "此时栈中的元素: ");
stackprint(pa);for (p = s->next; p; p = p->next)
{
p->a = Gettopdata(pa);
pa = pa->next;
}
fprintf(stdout, "用栈逆置后的链表: ");
linkprint(s);
return 0;
}
由以上栈的综合运用我们不难发现，无论是多么复杂的栈问题，基本都需要反复运用栈的基本算法，因此，无论是顺序栈还是链式栈，这些基本的运算都必须完全掌握，笔者建议学者们在下多次练习这些基础操作。
