C语言数据结构——栈

继续发水文,今天说说“栈”(stack)这一数据结构。

栈应该算是数据结构中比较简单的一种,其原理一句话就可以解释清楚,即元素是“先进后出”的。如果把栈想成一摞书,就很好理解了。每次放书都只能放到最上面,而每次取书也只能取最上面那一本。当然书架的空间是有限制的,当你需要放书的时候你需要判断这摞书是否到顶了,如果到顶了你就没有办法再往上面放了;而取书的时候,如果这摞书已经空了,就不能取书了。栈同样有自己的限制。为了更加方便地去判断这摞书还能不能放或者取,我们需要记录书的数目。同样,我们在栈里也需要一个记录栈中元素数目的变量,我们称之为栈顶(top)。

stack-1

这样,我们就有了构建一个栈所需的必备的结构,接下来,我们需要明确的是对栈的操作。栈的两个基本操作分别是——压入(Push)和弹出(Pop),即元素进栈和元素出栈。每进入一个元素,栈顶+1,每弹出一个元素栈顶-1,当然这其中还需要增加对栈空与栈满的判断,这实际上已经很容易做到了。

stack-push
压入元素

 

stack-pop
弹出元素

接下来就是代码,用C语言实现,在Dev-C++ 5.7.1 + Windows 8.1 x64下面编译通过。

#include <stdio.h>
#define STACKLEN 50		//Define the length of the stack

/* Define the structure */

typedef struct _stack
{
	int array[STACKLEN];
	int top; 
} list;


/***********************************************************
	Function Name: init_stack
	Function Description: Initialize a stack.
	Inputs: Pointer of variable of structure _stack. Eg. init_stack(&example);
	Outputs: None.
	Notes: None.
************************************************************/ 


void init_stack(list *seqstack){
	int i=0;
	for (; i < STACKLEN; ++i)
	{
		seqstack->array[i]=0;
	}
	seqstack->top=0;
}

/***********************************************************
	Function Name: check_stack_empty
	Function Description: Check a stack if it is empty.
	Inputs: Pointer of variable of structure _stack. Eg. check_stack_empty(&example);
	Outputs: 1 means empty; 0 means not empty.
	Notes: None.
************************************************************/ 

int check_stack_empty(list *seqstack){
	if (seqstack->top==0){
		return 1;
	}else {
		return 0;
	}

}

/***********************************************************
	Function Name: check_stack_full
	Function Description: Check a stack if it is full.
	Inputs: Pointer of variable of structure _stack. Eg. check_stack_full(&example);
	Outputs: 1 means full; 0 means not full.
	Notes: None.
************************************************************/ 

int check_stack_full(list *seqstack){
	if (seqstack->top==STACKLEN-1){
		return 1;
	}else {
		return 0;
	}

}

/***********************************************************
	Function Name: push
	Function Description: Push an element into a stack.
	Inputs: Pointer of variable of structure _stack and value to input. 
			Eg. push(&example,value);
	Outputs: 1 means full and exit ; 0 means not full and success.
	Notes: Use Function check_stack_full.
************************************************************/ 

int push(list *seqstack,int x){
	if(check_stack_full(seqstack)){
		return 1;
	}else{
		
		seqstack->array[seqstack->top]=x;
		seqstack->top+=1;
		return 0;
	}
	
}

/***********************************************************
	Function Name: pop
	Function Description: Pop an element from a stack.
	Inputs: Pointer of variable of structure _stack. 
			Eg. pop(&example);
	Outputs: 1 means empty and exit ; 0 means not empty and success.
	Notes: Use Function check_stack_empty.
************************************************************/ 

int pop(list *seqstack){
	if (check_stack_empty(seqstack))
	{
		return 1;
	} else{
		seqstack->array[seqstack->top]=0;
		seqstack->top-=1;
		return 0;
	}
}

/***********************************************************
	Function Name: print_stack
	Function Description: Print all elements of a stack.
	Inputs: Pointer of variable of structure _stack and the length to print. 
			Eg. print_stack(&example,length);
	Outputs: None.
	Notes: Use Function check_stack_empty.
************************************************************/ 

void print_stack(list *seqstack,int l){
	int i=l-1;
	 if (check_stack_empty(seqstack)){
	 	printf("========STACK========\n");
	 	printf("The stack is empty.\n");
	 	printf("=====================\n");
	 }else{
	 	printf("========STACK========\n");
		for (; i>=0; i--)
			{
				printf("%d\n",seqstack->array[i]);
			}
			if (check_stack_full(seqstack)){
				printf("The stack is full.\n");
			}
		printf("=====================\n");
	 }
}



int main(int argc, char const *argv[])
{
	int i=0;
	int cnt;
	list seqstack;
	int input=0;
	init_stack(&seqstack);
	int choice=0;
	printf("Now initializing the stack.(The stack length is 50.)\n");
	printf("Please input length of the stack:");
	scanf("%d",&cnt);
	do{
		printf("=========MENU========\n");
		printf("1:Push a element into the stack.\n");
		printf("2:Pop a element of the stack.\n");
		printf("3:Print all the element of the stack.\n");
		printf("0:Do nothing.\n");
		printf("Please select the option:");
		scanf("%d",&choice);
		switch(choice){
			case 1:{
				printf("Please input a number:");
				scanf("%d",&input);
				if (push(&seqstack,input))
				{
					printf("The stack is FULL!\n");
				}else {
					printf("Push success!\n");
				}
			};
			break;
			case 2:{
				if (pop(&seqstack))
				{
					printf("The stack is EMPTY!\n");
				}else {
					printf("Pop success!\n");
				}
			};
			break;
			case 3:{
				print_stack(&seqstack,cnt);
			};
			break;

		}
	}while (choice!=0);
	return 0;
}

 

 

代码中我把判断栈空或者栈满分别用一个函数来实现,压入弹出也写成了一个函数,可以方便未来的调用。当然这个例子也仅仅是实现一个栈的基本功能,仅仅是数字的输入输出,但是还是能够帮忙理解栈的原理。栈多应用于四则运算表达式的解析,当然还是这里留个坑。

发布者

《C语言数据结构——栈》上有3条评论

  1. 您好,您的程序在判满时明显有问题,您实现的应该是空递增栈(姑且这么认为吧),简单的入栈出栈就出错了。

    Google Chrome 40.0.2214.111 Google Chrome 40.0.2214.111 Mac OS X  10.9.5 Mac OS X 10.9.5
    1. 您说的问题应该是指判断栈满的代码有问题(调试了一下确实如此),总之感谢大神指导,我当初写的时候加上写完调试的时候没有注意到这一点,感谢指出。

      Google Chrome 42.0.2305.3 Google Chrome 42.0.2305.3 Windows 8.1 x64 Edition Windows 8.1 x64 Edition

发表评论

电子邮件地址不会被公开。 必填项已用*标注