堆栈的实现及应用

1．栈是先入后出的数据结构，它的实现可以用数组或者栈顶指针表示，用数组时，可以为栈预分配一定的大小，栈为空时，下标值为top为-1，每增加一个元素，下标值加1，出栈时，弹出一个元素，下标值减1，判断栈是否为空可以用下标值top是否为-1。

# include <stdio.h>
# include <stdlib.h>
int stack[100]={};
int top=-1;
int size=100;
int main()
{
	
	void push(int a[],int);
	int pop(int a[]);
	int isempty(int a[]);
	push(stack,1);
	push(stack,2);
	push(stack,3);
	printf("%d\n",isempty(stack));
	printf("%d\n",pop(stack));
	printf("%d\n",pop(stack));
system("pause");
return 0;
}

void push(int a[],int x)
{
if(top>=size)
	printf("out of range");
else
	top++;
    stack[top]=x;
}

int pop(int a[])
{
if (top==-1){
	printf("stack is empty");
	exit(-1);
	}
return a[top--];  
}
int isempty(int a[])
{
return top==-1;
}

2.栈也可以用指针来实现，定义结构体表示一个节点，每个节点包含两个元素，一个是节点的数据值，另外一个是前驱指针。栈的入栈操作示意图为

# include <stdio.h>
# include <stdlib.h>
struct node
{
int num;
struct node *next;
};
typedef struct node *link;

int main()
{
	link stack=NULL;
link push(link,int);
int pop(link);
int isempty(link);

link s=push(stack,1);
s=push(s,2);
s=push(s,3);
printf("%d\n",pop(s));
printf("%d\n",isempty(s));
system("pause");
return 0;
}

link push(link stack,int x)
{
link newele=(link)malloc(sizeof(node));
if(!newele)
	exit(-1);
newele->next=stack;
newele->num=x;
stack=newele;
return stack;
}

int pop(link stack)
{
if(!stack)
	return -1;
int t;
link temp=stack;
stack=stack->next;
t=temp->num;
free(temp);
return t;
}

int isempty(link stack)
{
return stack==NULL;
}

3栈的应用

栈可以用于把十进制数转换为其它进制，如将十进制转换为8进制，N=(N/8)*8+N%8,将N除以8取商，最后将商值反过来写，即得到对应的八进制数，这刚好和栈的性质类似，下面用数组实现一个栈，并用此栈实现进制数转换。

# include <stdio.h>
# include <stdlib.h>
int stack[100]={};
int top=-1;
int size=100;
int main()
{   int t;
	void push(int a[],int);
	int pop(int a[]);
	int isempty(int a[]);
	printf("input the decimal number\n");
    scanf("%d",&t);
	if(t>0){
	while(t)
	{
	push(stack,t%8);
	t=t/8;
	}
	
	while(!isempty(stack))
	{
	printf("%d",pop(stack));
	}
	}
	else
	{
	t=-t;
	while(t)
	{
	push(stack,t%8);
	t=t/8;
	}
	printf("-");
	while(!isempty(stack))
	{
	printf("%d",pop(stack));
	}
	}
	printf("\n");
system("pause");
return 0;
}

void push(int a[],int x)
{
if(top>=size)
	printf("out of range");
else
	top++;
    stack[top]=x;
}

int pop(int a[])
{
if (top==-1){
	printf("stack is empty");
	exit(-1);
	}
return a[top--];  
}
int isempty(int a[])
{
return top==-1;
}

堆栈的实现及应用

原文：http://blog.csdn.net/u011608357/article/details/18980659