欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法 栈

程序员文章站 2022-06-03 13:33:27
...

数据结构与算法 栈

一、简述

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

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

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

二、栈的顺序存储结构

        例子:输入正数--〉入栈,输入负数--〉出栈,输入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);
	}
}

        运行结果:

                        数据结构与算法 栈