当前位置：首页 > news >正文

关于栈（顺序栈）的知识讲解

news 来源：原创 2024/9/19 12:34:06

1.1 什么是栈

栈是只能在一端进行插入和删除操作的线性表(又称为堆栈)，进行插入和删除操作的一端称为栈顶，另一端称为栈底。

特点：栈是先进后出FILO(First In Last Out)

(LIFO(Last In First Out))

1.2 顺序栈

1.2.1 特性

逻辑结构：线性结构

存储结构：顺序结构

操作：创建、入栈、出栈、判空和判满

创空：

入栈：

出栈：

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct seqstack
{int maxlen;     //表示数组元素总个数
    datatype *data; //指向存放数据的数组的指针int top;        //栈顶有可以称栈针，本质还是最后一个有效元素下标等同于之前学的顺序表的last
} seqstack_t;//创建空顺序栈, len代表创建栈时的最大长度
seqstack_t *createEmptySeqStack(int len)
{//1. 开辟顺序栈结构体大小空间seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (NULL == p){perror("p malloc err");return NULL;}//2. 初始化结构体空间
    p->top = -1;                                          //如同之前的last初始化为-1，因为元素个数是0，下标是0-1=-1
    p->maxlen = len;                                      //保存数组长度可以通过传参获取
    p->data = (datatype *)malloc(sizeof(datatype) * len); //开辟数组大小空间，单个元素大小乘以元素个数if (NULL == p->data){perror("p->data malloc err");return NULL;}return p;
}//判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p)
{return p->top + 1 == p->maxlen;
}//入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{//  1. 判满： p->top + 1 == p->maxlenif (isFullSeqStack(p)){printf("pushStack err\n");return -1;}// 让top栈顶加一
    p->top++;// 将数据入栈
    p->data[p->top] = data;return 0;
}//判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{return p->top == -1;
}//出栈
int popSeqStack(seqstack_t *p)
{//1.容错判断if (isEmptySeqStack(p)){printf("popSeqStack\n");return -1;}//printf("%d\n", p->data[p->top]);  //或者加打印也可以//2. 将栈针top减一
    p->top--;//3. 返回要出栈数据return p->data[p->top + 1];
}int main(int argc, char const *argv[])
{seqstack_t *p = createEmptySeqStack(6);for (int i = 0; i < 7; i++)pushStack(p, i); //最后报一个pushStack err，因为栈满了while (!isEmptySeqStack(p))printf("%d\n", popSeqStack(p));  //5 4 3 2 1 0 后进先出return 0;
}

练习：

软通动力校园招聘笔试题

1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )

A. 1,4,3,2 //入1出1入234出4出3出2

B. 2,3,4,1 //入12 出2 入3 出3 入4出4 出1

C. 3,1,4,2

D. 3,4,2,1 //入123出3入4出4出2 出1

下列叙述正确的是( )

A. 线性表是线性结构

B. 栈与队列是非线性结构

C. 线性链表是非线性结构

二叉树是线性结构

3. 下列关于栈叙述正确的是( )

A.在栈中只能插入数据

B.在栈中只能删除数据

C.栈是先进先出的线性表

D.栈是先进后出的线性表

请问下面的程序有问题吗？如果有问题在哪儿？

#include <stdio.h>
#include <stdlib.h>void get_mem(int *q) //q=NULL
{
    q = (int *)malloc(sizeof(int)); //改变q不会影响到函数外的p， 开辟空间也不够
}int main(int argc, char const *argv[])
{int i;int *p = NULL;get_mem(p); //函数调用完成后p还是等于NULLfor (i = 0; i < 10; i++)
        p[i] = i;for (i = 0; i < 10; i++)printf("%d\n", p[i]);free(p);return 0;
}

错误：相当于值传递，改变函数内的q不会影响到主函数的p，函数调用后p还是等于NULL。再一个开辟空间大小不够，只开辟了4字节。

修改：可以通过传递二级指针，或者返回值

#include <stdio.h>
#include <stdlib.h>void get_mem(int **q) //q=&p
{*q = (int *)malloc(sizeof(int) * 10); //*q = *&p =p ,也就是操作*q就等同操作函数外的p
}int main(int argc, char const *argv[])
{int i;int *p = NULL;get_mem(&p); //函数调用结束后p真的指向了堆区for (i = 0; i < 10; i++)
        p[i] = i;for (i = 0; i < 10; i++)printf("%d\n", p[i]);free(p);return 0;
}