数据结构与算法栈

淡淡的烟草味﹌ 2022-05-12 05:16 196阅读 0赞

### **数据结构与算法 栈** ###

**一、简述**

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

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

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

**二、栈的顺序存储结构**

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

**        代码结构:**

**         **![70][]

**        测试代码：**

#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");
    	
    }

**        运行结果：**

![70 1][]

测试代码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--〉退出**

**        代码结构:**

![70 2][]

**        测试代码：**

#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);
    	}
    }

**        运行结果：**

![70 3][]

[70]: /images/20220512/e2b28444855642b8a310835507ff46b1.png
[70 1]: /images/20220512/104f30140578457ba6e08cbd58f7bb33.png
[70 2]: /images/20220512/1420b1f25dec4cb6a7385752f503534a.png
[70 3]: /images/20220512/4dd9e7744fbc4b608632d1b4a997c515.png