数据结构与算法 栈

数据结构与算法 栈

一、简述

      栈是一种只能在一端进行插入或删除操作的线性表。进行插入、删除的一端称为栈顶，栈顶的当前位置是动态的，由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。栈中没有数据元素时，称为空栈。栈的插入操作通常称为压栈或入栈，栈的删除操作通常称为退栈或出栈。

      栈的主要特点是“后进先出”，即后进栈的元素先弹出，栈也称为 后进先出表。每次进栈的数据元素都放在栈顶元素之上成为新的栈顶元素，每次出栈的元素数据都是当前的栈顶元素。

      栈的实现：可以使用顺序存储结构(数据元素存放位置相邻)，也可以使用链式存储结构(数据元素存放位置一般不相邻，随机的)

二、栈的顺序存储结构

        例子：输入正数--〉入栈，输入负数--〉出栈，输入0--〉退出

        代码结构:

         

        测试代码：

#include <stdio.h>
#include <stdlib.h>//memset()

#define SIZE	5

typedef struct s_stack
{
	int data[SIZE];
	int top;
}Stack;


/*函数声明*/
void init_stack(Stack *stack);
int is_empty(Stack *stack);
int is_full(Stack *stack);
int push_stack(Stack *stack, int input);
int pop_stack(Stack *stack, int *output);
void display_stack(Stack *stack); 

int main(int argc, char *argv[])
{
	Stack stack;
	init_stack(&stack);//初始化栈
	
	int input, ret, output;
	
	while(1)
	{
		scanf("%d", &input);
		if( input > 0 )//入栈
		{
			ret = push_stack(&stack, input);
			if( ret == 0)
			{
				display_stack( &stack );//打印栈的所有元素
			}
			else
			{
				printf("push data to stack is failed\n");
			}
			
		}
		else if( input < 0 )//出栈
		{
			ret = pop_stack(&stack, &output);
			if( ret == 0)
			{
				printf("出栈的元素是[%d]\n", output);
				display_stack( &stack );
			}
			else
			{
				printf("pop data from stack is failed\n");
			}
		}
		else if(input == 0)//退出 
		{
			break;
		}
	}
	return 0;
}

void init_stack(Stack *stack)//初始化栈 
{
	memset(stack->data, 0, sizeof(Stack));
	stack->top = -1;
}

int is_empty(Stack *stack)//判断栈是否为空 
{
	return stack->top == -1;
}

int is_full(Stack *stack)//判断栈是否满了 
{
	return stack->top == (SIZE-1);
}

int push_stack(Stack *stack, int input)//元素入栈 
{
	if( is_full(stack) == 1 )
	{
		return -1;
	}
	
	stack->data[++stack->top] = input;
	
	return 0;
}

int pop_stack(Stack *stack, int *output)//元素出栈,出栈的元素存放到output 
{
	if( is_empty(stack) == 1 )
	{
		return -1;
	}
	
	*output = stack->data[stack->top--];
	
	return 0;
}

void display_stack(Stack *stack)//打印栈所有元素 
{
	if( is_empty(stack) == 1)
	{
		printf("the stack is empty\n");
		return ;
	}
	
	printf("栈底 ");
	int i;
	for(i=0; i <= stack->top; ++i )
	{
		printf("[%d] ", stack->data[i]);
		
	}
	printf("栈顶\n");
	
}

        运行结果：

                         

   测试代码2：效果与测试代码1一样，不同点在于数据元素存放在堆之中。

   

#include <stdio.h>
#include <stdlib.h>//calloc() 

#define SIZE	5

typedef struct s_stack
{
	int *data;
	int top;
}Stack;


/*函数声明*/
void init_stack(Stack *stack);
int is_empty(Stack *stack);
int is_full(Stack *stack);
int push_stack(Stack *stack, int input);
int pop_stack(Stack *stack, int *output);
void display_stack(Stack *stack); 

int main(int argc, char *argv[])
{
	Stack stack;
	init_stack(&stack);//初始化栈
	
	int input, ret, output;
	
	while(1)
	{
		scanf("%d", &input);
		if( input > 0 )//入栈
		{
			ret = push_stack(&stack, input);
			if( ret == 0)
			{
				display_stack( &stack );//打印栈的所有元素
			}
			else
			{
				printf("push data to stack is failed\n");
			}
			
		}
		else if( input < 0 )//出栈
		{
			ret = pop_stack(&stack, &output);
			if( ret == 0)
			{
				printf("出栈的元素是[%d]\n", output);
				display_stack( &stack );
			}
			else
			{
				printf("pop data from stack is failed\n");
			}
		}
		else if(input == 0)//退出 
		{
			break;
		}
	}
	
	free(stack.data);
	return 0;	
}

void init_stack(Stack *stack)//初始化栈 
{
	stack->data = (int*) calloc(SIZE, sizeof(int));
	stack->top = -1;
}

int is_empty(Stack *stack)//判断栈是否为空 
{
	return stack->top == -1;
}

int is_full(Stack *stack)//判断栈是否满了 
{
	return stack->top == (SIZE-1);
}

int push_stack(Stack *stack, int input)//元素入栈 
{
	if( is_full(stack) == 1 )
	{
		return -1;
	}
	
	stack->data[++stack->top] = input;
	
	return 0;
}

int pop_stack(Stack *stack, int *output)//元素出栈,出栈的元素存放到output 
{
	if( is_empty(stack) == 1 )
	{
		return -1;
	}
	
	*output = stack->data[stack->top--];
	
	return 0;
}

void display_stack(Stack *stack)//打印栈所有元素 
{
	if( is_empty(stack) == 1)
	{
		printf("the stack is empty\n");
		return ;
	}
	
	printf("栈底 ");
	int i;
	for(i=0; i <= stack->top; ++i )
	{
		printf("[%d] ", stack->data[i]);
		
	}
	printf("栈顶\n");
	
}

三、栈的链式存储结构

        链式栈动态申请空间来存放那个数据，一般没有栈满的情况。

        例子：输入正数--〉入栈，输入负数--〉出栈，输入0--〉退出

        代码结构:

        测试代码：

#include <stdio.h>
#include <stdlib.h>//calloc() 

#define SIZE	5

typedef struct s_stack
{
	int data;
	struct s_stack *next;
}Stack;

/*函数声明*/
void init_stack(Stack *stack);
int is_empty(Stack *stack);
int is_full(Stack *stack);
int push_stack(Stack *stack, int input);
int pop_stack(Stack *stack, int *output);
void display_stack(Stack *stack); 
void free_stack(Stack *stack);

int main(int argc, char *argv[])
{
	Stack stack;
	init_stack(&stack);//初始化栈
	
	int input, ret, output;
	
	while(1)
	{
		scanf("%d", &input);
		if( input > 0 )//入栈
		{
			ret = push_stack(&stack, input);
			if( ret == 0)
			{
				display_stack( &stack );//打印栈的所有元素
			}
			else
			{
				printf("push data to stack is failed\n");
			}
			
		}
		else if( input < 0 )//出栈
		{
			ret = pop_stack(&stack, &output);
			if( ret == 0)
			{
				printf("出栈的元素是[%d]\n", output);
				display_stack( &stack );
			}
			else
			{
				printf("pop data from stack is failed\n");
			}
		}
		else if(input == 0)//退出 
		{
			break;
		}
	}
	
	free_stack(&stack);
	return 0;	
}

void init_stack(Stack *stack)//初始化栈 
{
	stack->next = NULL;
}

int is_empty(Stack *stack)//判断栈是否为空 
{
	return stack->next == NULL;
}

int push_stack(Stack *stack, int input)//元素入栈 
{
	Stack *new_node;
	new_node = (Stack*) calloc(1, sizeof(Stack));
	new_node->next = stack->next;
	new_node->data = input;
	stack->next = new_node;
	
	return 0;
}

int pop_stack(Stack *stack, int *output)//元素出栈,出栈的元素存放到output 
{
	if( is_empty(stack) == 1 )
	{
		return -1;
	}
	
	*output = stack->next->data;
	stack->next = stack->next->next;
	
	return 0;
}

void display_stack(Stack *stack)//打印栈所有元素 
{
	if( is_empty(stack) == 1)
	{
		printf("the stack is empty\n");
		return ;
	}
	
	printf("栈顶 ");
	Stack *tmp;
	for(tmp=stack->next; tmp != NULL; tmp=tmp->next )
	{
		printf("[%d] ", tmp->data);
		
	}
	printf("栈底\n");
	
}

void free_stack(Stack *stack)//释放链栈 
{
	Stack *tmp;
	for(tmp=stack->next; tmp != NULL; tmp=stack->next )
	{
		stack->next = stack->next->next;
		printf("free: [%d] \n", tmp->data);
		free(tmp);
	}
}

        运行结果：