数据结构之栈与队列(一）

秒速五厘米 2023-06-16 01:56 55阅读 0赞

# 什么是栈 #

> 栈是一种用来存储，逻辑关系为“一对一”的线性存储结构，栈的存取遵循“先进后出”原则。

栈有以下两种特性：

*  栈只能从表的一端存取数据，另一端是封闭的
 *  栈中，无论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

栈顶与栈底：

*  栈的开口被称为栈顶，封口端被称为栈底。
 *  栈顶元素是距离栈顶最近的元素
 *  栈底元素是距离栈底最近的元素

进栈与出栈：

*  向栈中添加元素，被称为“进栈”（入栈或压栈）
 *  向栈中提取出指定元素，被称为“出栈”（弹栈）

栈的具体实现：

*  顺序栈：采用顺序存储的结构模拟存取数据的特点
 *  链栈：采用链式结构模拟栈

顺序栈的代码实现:

入栈：

//进栈，p为数组，top值为当前栈的栈顶位置
    int push(int* p,int top,int elem){
        ++top;
        p[top]=elem;
        return top;
    }

在最开始的时候，栈是空的，所以指针元素top = -1;然后向栈中添加元素1，以数组下标0端表示栈底，1被存储在a\[1\]处，top值+1。

出栈：

//出栈
    int pop(int * p,int top){
        if (top==-1) {
            printf("空栈");
            return -1;
        }
        printf("出栈元素：%d\n",p[top]);
        top--;
        return top;
    }

对于元素出栈的实现，top值-1即可

全部代码：

#include <stdio.h>
    //进栈
    int push(int* a,int top,int elem){
        a[++top]=elem;
        return top;
    }
    //出栈
    int pop(int * p,int top){
        if (top==-1) {
            printf("空栈");
            return -1;
        }
        printf("出栈元素：%d\n",p[top]);
        top--;
        return top;
    }
    int main() {
        int a[100];
        int top=-1;
    	int i=0;
        for(i=1;i<5;i++){
    		top=push(a, top, i);
        }
    	for(i=4;i>-1;i--){
            top=pop(a, top);
        }
        return 0;
    }

## 链栈的基本操作 ##

#### 基本思想： ####

链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底。  
![图片来源于网络][20191208162537550.jpg]

将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。但也正因为此，所以入栈时，必须将数据从链表**头部插入**，出栈时，也需要删除链表**头部**的首元素节点。  
所以可以把链栈称之为：**只能采用头插法插入或删除数据的链表**

#### 链栈入栈： ####

![图片来源于网络][20191208162911841.gif]

//链表中的节点结构
    typedef struct lineStack{
        int data;
        struct lineStack * next;
    }lineStack;
    //stack为链栈，a为入栈的元素
    lineStack* push(lineStack * stack,int a){
        //创建存储新元素的节点
        lineStack * line=(lineStack*)malloc(sizeof(lineStack));
        line->data=a;
        //新节点与头节点建立逻辑关系
        line->next=stack;
        //更新头指针的指向
        stack=line;
        return stack;
    }

#### 链栈出栈： ####

若要让栈中某元素出栈，则必须要该元素之前的所有元素都出栈，遵循“先进后出”原则。

代码如下：

lineStack * pop(lineStack * stack){
        if (stack) {
            //定义一个指针指向栈顶节点
            lineStack * p=stack;
            //更新头指针
            stack=stack->next;
            printf("出栈元素：%d ",p->data);
            if (stack) {
                printf("新栈顶元素：%d\n",stack->data);
            }else{
                printf("栈已空\n");
            }
            free(p);
        }else{
            printf("栈内没有元素");
            return stack;
        }
        return stack;
    }

[20191208162537550.jpg]: https://img-blog.csdnimg.cn/20191208162537550.jpg
[20191208162911841.gif]: https://img-blog.csdnimg.cn/20191208162911841.gif