C语言数据结构 - 栈

        类似很多软件都有撤销的 *** 作，这其实就是用栈这种方法来实现的，当然不同的软件具体实现代码会有差异，不过原理大多都是一样的。

        栈(stack)是限定仅在表尾进行插入和删除 *** 作的线性表。

        我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈低(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进后出(Last In First Out)的线性表，简称LIFO结构。

         它是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针top(相对指针)完成各种 *** 作。

         我们定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，如下图所示，它可以来回移动，意味着栈顶的top可以变大变小，但是无论如何游标都不能超出尺的长度。同理，若存储栈的长度为SIZE，则栈顶位置top必须小于SIZE。当栈存在一个元素时，top等于0，因此通常把为空栈的判定条件定为top等于-1；

代码示例：分为SeqStack.c、SeqStack.h、main.c

#include 
#include  
#include 
#include "SeqStack.h"

SqStack* CreatStack()						//初始化 *** 作，建立一个空栈
{
	SqStack* stack = (SqStack* )malloc(sizeof(SqStack));
	
	if(stack == NULL)
	{
		return NULL;
	}
	stack->top = -1;
	memset(stack->data,0,sizeof(stack->data));
	
	return stack;
} 
int Stack_is_Empty(SqStack *s)				//判断栈空 
{
	if(s == NULL)
	{
		return -1;
	} 
	return (s->top == -1);
} 
int Stack_is_Full(SqStack *s)				//判断栈满 
{
	if(s == NULL)
	{
		return -1;
	}
	return ( s->top == (MAXSIZE - 1) );
} 
int StackGetLength(SqStack *s)				//返回栈S的元素个数
{
	if(s == NULL)
	{
		return -1;
	}
	
	return (s->top+1);
} 
int Push(SqStack *s, data_t data)			//压栈，插入新元素data到栈S 
{
	if(Stack_is_Full(s) || s == NULL)
	{
		return -1;
	}
	s->data[s->top+1] = data;
	s->top++;
	
	return 0;
} 
data_t Pop(SqStack *s)						//出栈  从顺序栈中提取数据
{
	data_t data;
	
	if(s == NULL || Stack_is_Empty(s))
	{
		return -1;
	}
	
	data = s->data[s->top];
	s->top--;
	
	return data;
} 
int ClearStack(SqStack *s) 				    //将栈清空
{
	s->top = -1;
} 
int DestroyStack(SqStack *s)				//若栈存在，则销毁它
{
	s->top = -1;
	free(s);
} 
int PrintStack(SqStack *s)				    //打印顺序栈中的数据 
{
	int m = s->top;
	
	if(s == NULL)
	{
		return -1;
	}	
	for(;m >= 0; m--)
	{
		printf("%dn",s->data[m]);	
	}
	
	return 0;
} 

#ifndef __SEQSTACK_H__
#define __SEQSTACK_H__

#define MAXSIZE 10

typedef int data_t;              //定义栈中数据元素的数据类型 
typedef struct {
	data_t data[MAXSIZE];  
	int top;					 //栈顶指针  表示指向栈顶元素 
}SqStack;



SqStack* CreatStack();						//初始化 *** 作，建立一个空栈
int Stack_is_Empty(SqStack *s);				//判断栈空 
int Stack_is_Full(SqStack *s);				//判断栈满 
int StackGetLength(SqStack *s);				//返回栈S的元素个数
int Push(SqStack *s, data_t data);			//压栈，插入新元素data到栈S 
data_t Pop(SqStack *s);						//出栈  从顺序栈中提取数据 
int ClearStack(SqStack *s); 				//将栈清空
int DestroyStack(SqStack *s);				//若栈存在，则销毁它
int PrintStack(SqStack *s);				    //打印顺序栈中的数据 

 
#endif

#include 
#include "SeqStack.h"

int main(int argc, char *argv[])
{
	printf("顺序栈测试代码rn");
	
	SqStack *seq;
	int i;
	
	seq = CreatStack();

	for(i=0;i 
栈的链式存储结构及实现 
        上面介绍了栈的顺序存储结构，下面我们来看看栈的链式存储结构，简称链栈。
 
        链式栈的插入和删除 *** 作均在链表头部进行(如下图所示)，链表尾部就是栈底，栈顶指针就是头指针。
 
 
        对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机 *** 作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。
 
 
        对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top等于NULL的时候。
 
代码示例：分为linkstack.c、linkstack.h、main.c
 
#include "linkstack.h"
#include 
#include 

lstack * CreateLstack()             //创建链式栈
{
	lstack *top = (lstack *)malloc(sizeof(lstack));
	if(top == NULL)
	{
		return NULL;
	}	
	top->data = -1;
	top->next = NULL;
	
	return top;
}
int Lstack_is_Empty(lstack *top)     // 判断是否为空
{
	if(top == NULL)
	{
		return -1;
	} 
	
	return (top->next == NULL);
}
int LstackgetLength(lstack *top)    //求链式栈当中有效结点数 不包含头结点
{
	int num;
	lstack *p;
	
	if(top == NULL)
	{
		return -1;
	}
	
	p = top->next;
	while(p != NULL)
	{
		p = p->next;
		num++;
	}
	
	return num;
}
int PushLstack(lstack *top,data_t data)//入栈
{
	if(top == NULL)
	{
		return -1;
	}
	
	lstack *new_d = (lstack *)malloc(sizeof(lstack));
	if(new_d == NULL)
	{
		return -1;
	}
	
	new_d->data = data;
	new_d->next = NULL;
	
	new_d->next = top->next;
	top->next = new_d;
	
	return 0; 
}
data_t PoPLstack(lstack *top)         // 出栈
{
	if(top == NULL)
	{
		return -1;
	}
	
	lstack *p = top->next;
	top->next = p->next;
	
	data_t m = p->data;
	free(p);
	p = NULL;
	
	return 0; 
}

int DestoryStack(lstack **top)    //销毁链栈 
{
  if(top == NULL)
    {
        return -1;
    }
    lstack* to_delete = *top;
    while(to_delete != NULL)
    {
        lstack* node = to_delete->next;
        free(to_delete);
        to_delete = node;
    }
    *top = NULL;
    
    return 0;
}

int PrintLstack(lstack *top)     //打印链式栈
{
	if(top == NULL)
	{
		return -1;
	}
	
	lstack *p = top->next;
	while(p != NULL)
	{
		printf("%drn",p->data);
		p = p->next;	
	}
	
	return 0;
}
 
#ifndef __linkSTACK_H__
#define __linkSTACK_H__

typedef int data_t;                      //定义栈中元素数据类型

typedef struct node{
	data_t data;                         //数据域
	struct node *next;                   //链栈指针域
}lstack;                                 //链栈类型定义

lstack * CreateLstack();                  //创建链式栈
int Lstack_is_Empty(lstack *top);         // 判断是否为空
int LstackgetLength(lstack *top);         //求链式栈当中有效结点数 不包含头结点
int PushLstack(lstack *top,data_t data);  //入栈
data_t PoPLstack(lstack *top);            // 出栈
int PrintLstack(lstack *top);             // 打印链式栈
int DestoryStack(lstack **top);           //摧毁链栈 

#endif
 
#include 
#include "linkstack.h"

int main(int argc, char *argv[])
{
	int i;
	lstack *p = CreateLstack();
	
	for(i = 0; i < 10; i++)
	{
		PushLstack(p,i);
	}
	PrintLstack(p);
	//摧毁链栈 
	printf("摧毁链栈Srn");
	DestoryStack(&p);
	printf("摧毁链栈Ern");
	PrintLstack(p);
	 
	return 0;
}

 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5579430.html