C语言栈的基本实现

• • 1.栈的定义和特点
  • 2.顺序栈（数组型）的实现
  • 3.顺序栈（线性表型）的实现
  • 4.链式栈的实现
  • 5.总结

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈（push）、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈(pop)，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

首先我们定义一个全局的整型数组，基于此数组来进行栈的相关操作。直接上清晰简单的代码。
预处理：

#include
int A[MAX_SIZE];//创建一个全局的整型数组 
#define MAX_SIZE 101//宏定义数组的大小 101 
int top=-1;//空栈，虚构索引-1 

push操作：

void Push(int x){
	if(top==MAX_SIZE -1){
		printf("Error:stack overflown");
		return ;
	}
	// top ++;
	//A[top]=x; 
	A[++top]=x;//自增发生在赋值之前 
}

pop操作：

void Pop(){
	if (top==-1){
		printf("Error:No element to popn");
		return;
	}
	top--;
}
int Top(){
	return A[top];//直接返回top索引处的值。 
}

最后我们写一个print函数和主函数来测试一下。

void Print(){
	int i;
	printf("Stack: ");
	for(i=0;i<=top;i++){
		printf("%d ",A[i]);
	}
	printf("n");
}
int main(){
	Push(2);Print();
	Push(5);Print();
	Push(10);Print();
	Pop();Print();
	Push(12);Print();
	
}

测试结果如下：

不同于整型数组，定义了结构体是一种更加理想化的实现。代码：

#include 
#include 
typedef int Status;
typedef char SElemType;
#define stack_INIT_SIZE     100  //定义栈空间大小
#define stackINCREMENT  10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 typedef struct {
       SElemType  *base;   //栈底指针
       SElemType  *top;     //栈顶指针
       int stacksize;       //栈空间
}Sqstack;

Status iniStack(Sqstack &S) //初始化栈
{//构造一个空栈S
	S.base=(SElemType*)malloc(stack_INIT_SIZE * sizeof(SElemType));
	if(!S.base)return(ERROR);
	S.top=S.base;  //栈顶指针指向栈底指针表示栈为空
	S.stacksize=stack_INIT_SIZE;
	return OK;
  }//InitStack

Status push(Sqstack &S,SElemType x)  //入栈
{
	//栈不满的情况下进行入栈操作
	if(S.top-S.base>=S.stacksize){
		S.base=(SElemType * )realloc(S.base,
			(S.stacksize+stackINCREMENT)*sizeof(SElemType));
		if(!S.base)return(ERROR);
		S.top=S.base+S.stacksize;  //设置栈顶指针位置
		S.stacksize+=stackINCREMENT;  //累积入栈元素空间
  	}
	*S.top++=x;  //先入栈，指针再加1
	return OK;
}

Status pop(Sqstack &S,SElemType &e)  //出栈
{
	//栈不空时进行出栈操作
    if(S.top==S.base)return ERROR;
		e=*--S.top;  //指针先减1，再出栈
	return OK;
}

int main()
{
	Sqstack S;
	SElemType k;
	iniStack(S);  //栈初始化
	if(push(S,'A')==ERROR)  //入栈
        printf("入栈失败！n");
	if(push(S,'B')==ERROR)  //入栈
        printf("入栈失败！n");
    if(push(S,'C')==ERROR)  //入栈
        printf("入栈失败！n");
	if(pop(S,k)==ERROR)  //出栈
         printf("出栈失败！n");
    else
        printf("出栈元素为：%cn",k);
    if(pop(S,k)==ERROR)  //出栈
         printf("出栈失败！n");
    else
        printf("出栈元素为：%cn",k);
    return 0;
}

测试结果：

链式栈的实现，就用到链表。关于链表的操作，比如创建、插入等，此处不再做赘述。我们直接来看链表中push和pop操作的实现。
push操作：

void Push(int x){
	struct Node*temp=(struct Node*)malloc(sizeof(struct Node*));
	temp->data=x;
	temp->link=top;
	top=temp;
}

pop操作：

void Pop(){
	struct Node* temp;
	if(top==NULL) return ;//空栈不能执行操作
	temp=top;
	top=top->link;
	free(temp);
}

(1)顺序栈的实现（尤其是采用数组）比较简单，而且存储密度高。但是当栈需要动态变化（元素出入）时，我们如果设置的空间较大，则会造成浪费；如果设置的过小，就容易导致栈溢出，不得不开辟另外一块空间同时要拷贝原来栈的元素到新的空间去，这是比较麻烦的一件事。
（2）对于链式栈来说，它是运算受限的单链表，其插入和删除操作只能在表头进行。存储密度比顺序栈低。但是在空间上，链表是动态分配的，并且不会产生碎片化的空间，提高了空间的利用率。在程序设计时如何选择要看具体的需求。