栈概念及 顺序栈操作

一、概念

栈是线性表的一种，但是只能在一端进行插入和删除操作，操作的那一端称为栈顶，另一端称为栈底。如图：

特点：先进后出FILO（first?in?last?out）

逻辑结构：线性结构

储存结构：顺序存储、链式存储

• 二、顺序栈

  1. 特性

逻辑结构：线性结构

存储结构：顺序存储

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

创建空栈：

#include?<stdio.h>
#include?<stdlib.h>

typedef int?datatype;
typedef struct seqstack
{
????datatype?*data; //指向栈的存储位置
    int?maxlen;     //保存栈的最大长度
    int?top;        //称为栈针，用的时候可以当作顺序表中的last来使用，始终代表栈内最后一个有效元素下标。
} seqstack_t;

seqstack_t *createEmptySeqStack(int?len)
{
    //1.申请一块栈结构体大小的空间
    seqstack_t *p?= (seqstack_t *)malloc(sizeof(seqstack_t));
    if (NULL ==?p)
    {
        perror("createEmptySeqStack?p?malloc?err");
        return NULL;
    }
    //2.初始化
????p->maxlen?=?len; //设置栈的最大长度，通过传参拿到最大长度len赋值给结构体空间中的maxlen。
????p->top?= -1;     //栈为空，暂时将最后一个有效元素下标设为-1,类似于创空顺序表。
????p->data?= (datatype?*)malloc(sizeof(datatype) *?len);
    if (NULL ==?p->data)
    {
        perror("createEmptySeqStack?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.容错判断
    if (isFullSeqStack(p))
    {
        printf("pushStack:?isFullSeqStack\n");
        return -1;
    }
    //2.往上移动栈针
????p->top++;

    //3.将数据入栈
????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:isEmptySeqStack?\n");
        return -1;
    }
    //2.让?p->top减一，相当于向下移动一个单位
????p->top--;
    //3.将之前栈顶的数据返回
    return?p->data[p->top?+ 1];
}

//清空栈
void clearSeqStack(seqstack_t *p)
{
????p->top?= -1; //相当于清空
}

//获取栈顶数据(注意不是出栈操作，如果出栈，相当于删除了栈顶数据，只是将栈顶的数据获取到，不需要移动栈针)
int getTopSeqStack(seqstack_t *p)
{
    //1.容错判断
    if (!isEmptySeqStack(p))
        return?p->data[p->top];
    return -1;
}

//求栈的长度
int lengthSeqStack(seqstack_t *p)
{
    return?p->top?+ 1;
}

int main(int?argc, char const *argv[])
{
    seqstack_t *p?= createEmptySeqStack(5);
    for (int?i?= 1;?i?<= 6;?i++)
    {
        pushStack(p,?i);
    }
    printf("栈顶是%d\n", getTopSeqStack(p));
#if?1
    //只要栈不为空就出栈
    printf("出栈：");
    while (!isEmptySeqStack(p)) //出栈的顺序是?5?4?3?2?1?，因为栈的思想先进后出
    {
        printf("%d?", popSeqStack(p));
    }
    printf("\n");
#endif

    return 0;
}

练习：

软通动力校园招聘笔试题

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

?A.??1,4,3,2????

?B.??2,3,4,1????

1. ?3,1,4,2
2. 3,4,2,1

1. 下列叙述正确的是(??)

A.?线性表是线性结构

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

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

1. 二叉树是线性结构

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

????A.在栈中只能插入数据

????B.在栈中只能删除数据

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

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

#include?<stdio.h>
#include?<stdlib.h>
void get_memory(int *q) //q=NULL，相当于值传递。
{
????q?= (int *)malloc(sizeof(int));  //开辟空间大小不够
}

int main()
{
????int?i;
????int *p?= NULL;
????get_memory(p); 
????for(i?= 0;?i?< 10;?i++)  //p=NULL
????{
????????p[i] =?i;
????}
????for(i?= 0;?i?< 10;?i++)
????{
????????printf("%d\n",?p[i]);
????}???
????return 0;
}

错误：相当于值传递，并且开辟的空间的大小不够。

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

#include?<stdio.h>
#include?<stdlib.h>
void get_mem(int **q)        //q=&p
{
    *q?= (int *)malloc(sizeof(int) * 10); //*q=p
}
int main(int?argc, char const *argv[])
{
    int?i;
    int *p?= NULL;
    get_mem(&p);
    for (i?= 0;?i?< 10;?i++)
????????p[i] =?i;
    for (i?= 0;?i?< 10;?i++)
        printf("%d\n",?p[i]);
    free(p);
????p=NULL;
    return 0;
}