数组、链表、队列和栈----栈，C语言实现

小咪咪 2023-03-01 05:55 28阅读 0赞

栈是一种“后进先出”的数据结构。  
我们想象一下，鉴于栈的“后进先出”特征，如果我们依次把1，2，3这三个数据压入栈中，然后再弹出来，可能得到几种结果呢？  
第一种：把1，2，3一次性压入栈中，再弹出来，得到3，2，1。  
第二种：把1，2压入栈中，弹出来，再压入3，弹出来。得到2，1，3。  
第三种：把1压入栈中，弹出来，再压入2，弹出来，再压入3，弹出来。得到1，2，3。  
第四种：把1压入栈中，弹出来，再压入2，3，弹出来。得到1，3，2。  
从这个例子看，栈是不是很特别：不同的入栈出栈可以导致截然不同的结果。相比之下，队列不管是怎么进栈、出栈，结果是一样的。

## 4.1 数组实现简单栈 ##

栈也可以用数组和链表实现。这里用数组实现简单栈。

申请了10个位置的数组，用数组实现简单栈

int stack[10];  
    int capacity = 10; //栈的总容量为10 
    
    栈的范围是0 ~ top
    int top = 0; //栈顶的index为top

需要实现几个功能：

0、依次显示所有数据 (当作数组看待，其实栈不需要这个功能)
    void show() 
    {
        
    	for(int i = 0; i < top; i++)
    	{
        
    		printf("%d, ", stack[i]);  
    	}
    	printf("\r\n");  
    }
    
    1、读取栈的首元素，(不出栈)
    void peek()
    {
        
    	if(top <= 0) //栈为空
    	{
        
    		printf("栈中没有数据\r\n"); 
    		return;
    	}
    	printf("栈的首元素: %d \r\n", stack[top - 1]); //数组方式访问数据 
    }
    
    2、入栈：在栈顶插入一个数
    void push(int n) 
    {
        
    	if(top >= capacity) //栈满了
    	{
        
    		printf("栈满了，无法添加数据\r\n");
    		return;
    	}
    	//top的位置是空的，所以直接对stack[top]赋值就是在栈最后插入数据 
    	stack[top] = n; 
    	top++; //入栈之后top + 1，保持top的位置是空的 
    }
    
    3、出栈：栈顶元素离开栈 
    int pop()
    {
        
    	if(top <= 0) //栈为空
    	{
        
    		printf("栈中没有数据，无法出栈\r\n"); 
    		return -1;
    	}
    	
    	int num = stack[top - 1]; //记录栈的首元素 
    	top--; //出栈: 栈的top不再包含原先的首元素，即删除了栈首元素 
    	return num; //返回数据 
    }
    
    4、计算栈现有多少个元素 
    int getSize()
    {
        
    	return top; //栈的范围是0 ~ top，所以栈中的元素个数是top
    }

下面是完整的代码：

#include <stdio.h>
    #include <stdlib.h>
    
    //申请了10个位置的数组，用数组实现简单栈 
    int stack[10];  
    int capacity = 10; //栈的总容量为10 
    
    //栈的范围是0 ~ top
    int top = 0; //栈顶的index为top
    
    //0、依次显示所有数据 (当作数组看待，其实栈不需要这个功能)
    void show() 
    {
        
    	for(int i = 0; i < top; i++)
    	{
        
    		printf("%d, ", stack[i]);  
    	}
    	printf("\r\n");  
    }
    
    //1、读取栈的首元素，(不出栈)
    void peek()
    {
        
    	if(top <= 0) //栈为空
    	{
        
    		printf("栈中没有数据\r\n"); 
    		return;
    	}
    	printf("栈的首元素: %d \r\n", stack[top - 1]); //数组方式访问数据 
    }
    
    //2、入栈：在栈顶插入一个数
    void push(int n) 
    {
        
    	if(top >= capacity) //栈满了
    	{
        
    		printf("栈满了，无法添加数据\r\n");
    		return;
    	}
    	//top的位置是空的，所以直接对stack[top]赋值就是在栈最后插入数据 
    	stack[top] = n; 
    	top++; //入栈之后top + 1，保持top的位置是空的 
    }
    
    //3、出栈：栈顶元素离开栈 
    int pop()
    {
        
    	if(top <= 0) //栈为空
    	{
        
    		printf("栈中没有数据，无法出栈\r\n"); 
    		return -1;
    	}
    	
    	int num = stack[top - 1]; //记录栈的首元素 
    	top--; //出栈: 栈的top不再包含原先的首元素，即删除了栈首元素 
    	return num; //返回数据 
    }
    
    //4、计算栈现有多少个元素 
    int getSize()
    {
        
    	return top; //栈的范围是0 ~ top，所以栈中的元素个数是top
    }
    
    int main()
    {
        
    	printf("入栈1~15\r\n");
    	for(int i = 1; i <= 15; i++)
    	{
        
    		push(i); //入栈
    	}
    	
    	printf("显示所有数据：");
    	show(); //依次显示所有数据
    		
    	printf("出栈: %d\r\n", pop());
    	printf("出栈: %d\r\n", pop());
    	peek(); //查看当前首元素 
    	
    	push(6); //入栈
    	printf("入栈6, 显示所有数据：");
    	show(); 
    	
    	printf("一共有几个元素: %d\r\n", getSize());
    	
    	printf("显示所有数据: ");
    	show(); //依次显示所有数据
    	return 0;
    }

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
如果一次性入栈15个数据情况是怎么样呢？跟预期的一样，用数组实现的栈会发生栈满了的情况。但是跟队列不一样的是，队列满的时候，实现队列的数组可能还没有真正满；但是栈满的时候，实现栈的这个数组一定是真的满了。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]如果两个栈占用的总空间是固定的，那就可以共享一个数组的空间，具体来说就是把这两个栈分别放到数组的两头，入栈的时候，数据就往中间靠，出栈的时候数据往两边退即可。这样的栈就交给读者完成吧。

下一节，我们用链表实现栈。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/06769e6b7b8e41b0a7e126419d6d6807.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200722152707599.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc=,size_16,color_FFFFFF,t_70