栈(顺序栈)

简介: 栈(顺序栈)

栈作为一个最简单的数据结构,实现起来也非常容易,想想现在有一摞盘子,每次只能取走或放一个盘子且只能最上面进行操作;

那么我们如果有一个索引TOP时刻指向最上面的那个盘子,栈不就实现了么?

栈的理论

  • 栈是一个先进后出的结构,类似于堆盘子,先放到地上的盘子最后被取走(默认只能取走一个盘子)
  • 栈其实就是操作受限的线性表,只有一个口,每一次操作时,这个口可以当出口也可以当入口.
  • 例如:水桶,注入水时,水桶的头当做入口,倒水时,水桶的头当做出口


什么是栈

栈是限制插入和删除只能在一个位置上进行的线性表。其中,允许插入和删除的一端位于表的末端,叫做栈顶(top),不允许插入和删除的另一端叫做栈底(bottom)。对栈的基本操作有 PUSH(压栈)和 POP (出栈),前者相当于表的插入操作(向栈顶插入一个元素),后者则是删除操作(删除一个栈顶元素)。栈是一种后进先出(LIFO)的数据结构,最先被删除的是最近压栈的元素。栈就像是一个箱子,往里面放入一个小盒子就相当于压栈操作,往里面取出一个小盒子就是出栈操作,取盒子的时候,最后放进去的盒子会最先被取出来,最先放进去的盒子会最后被取出来,这即是后入先出。下面是一个栈的示意图:

d83f07d8b9926527e07ad2a8531136d5.png

注意:栈顶和栈底不是上下决定,而是有入栈方向决定.


栈的实现

顺序栈(顺序结构)

用一段连续的存储空间来存储栈中的数据元素,比较常见的是用数组来实现顺序栈。

  • 元素所占的存储空间必须连续(这里的连续是指的逻辑连续,而不是物理连续)
  • 元素在存储空间的位置是按逻辑顺序存放的

a5719b90dd99159753904c4428d14791.png

c62f50421d554d757f25f2522f81b976.png

顺序栈的实现一般包括如下部分

#define OK   1
#define ERROR   0
#define TRUE  1
#define FALSE  0
#define OVERFLOW   -2
typedef  int  ElemType;
typedef  int  Status;
//----- 栈的顺序存储表示 -----
#define STACK_INIT_SIZE 10 // 存储空间的初始分配量
#define STACKINCREMENT 5// 存储空间的分配增量
typedef struct{
    ElemType *base;       //存储空间的基址
    int  top;             //栈顶元素的下一个元素,简称栈顶位标
    int  size;            //当前分配的存储容量,作用看入栈操作就可以知道
    int  increment;       //扩容时,增加的存储容量,作用看入栈操作就可以知道
} SqStack;                //顺序栈类型


构造一个空栈(初始化)

Status InitStack(SqStack &S) {
    S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!S.base) exit(OVERFLOW);
    S.top = 0;
    S.size = STACK_INIT_SIZE;
    S.increment = STACKINCREMENT;
    return OK;
}


判栈 S 是否为空栈

Status StackEmpty(SqStack S){
 if(S.top == 0)
  return TRUE;
 else 
  return FALSE;
}


入栈函数

Status Push(SqStack &S, ElemType e) {
    //定义中间变量
 ElemType *newbase;          
    //S.top如果指向最后一个不存储元素的地址时,即S.top大于
    if (S.top>= S.size) {       
     //等于S.size时,就表示栈满了  //通过realloc动态扩容
  newbase = (ElemType*)realloc(S.base,
  (S.size + S.increment) * sizeof(ElemType));
  //判断扩容是否成功  
     if (NULL == newbase) return OVERFLOW;     
     //扩容成功后才将中间变量的值指向S.elem,防止扩容失败时,
  S.base = newbase;
  //S.elem指向一个不是原来的位置         
     S.size += S.increment;       
    }
    //将e元素入栈; 使S.top加1,表示指向的是栈顶位标
    S.base[S.top++] = e;
 //上面操作正常后返回1     
    return  OK;             
}


出栈函数

栈顶元素出栈,赋给元素e

Status Pop(SqStack &S, ElemType &e) {  
 //请在此填写代码,将该算法补充完整,参见课本和课件相关章节
    if ( 0  == S.top)  return  ERROR;    
    //e出栈,并将S.top减1
    e = S.base[--S.top];     
    return  OK;
}


输出顺序栈函数

void OutStack(SqStack S) {  
    ElemType  e;
    if(TRUE == StackEmpty(S)) {
        printf("这是一个空栈!");
    } else 
        while(FALSE == StackEmpty(S)){
   Pop(S, e);
   printf("%6d", e);
   }
    printf("\n");
}


主函数(展示)

int main() {  
    SqStack s;
    int cord; ElemType a;
    printf("第一次使用必须初始化!\n");
    do {
        printf("\n 主菜单 \n");
        printf(" 1 初始化顺序栈 ");
        printf(" 2 插入一个元素 ");
        printf(" 3 删除栈顶元素 ");
        printf(" 4 结束程序运行 ");
        printf("\n-------------------------------------------------------------------\n");
        printf("请输入您的选择( 1, 2, 3, 4)");
        scanf("%d", &cord);
        printf("\n");
        switch(cord) {  
            case 1:
                InitStack(s);
                OutStack(s);
                break;
            case 2:
                printf("请输入要插入的数据元素:a=");
                scanf("%d", &a);
                Push(s, a);
                printf("%d 进栈之后的栈:", a);
                OutStack(s);
                break;
            case 3:
                Pop(s, a);
                printf("栈顶元素 %d 出栈之后的栈:", a);
                OutStack(s);
                break;
            case 4:
                exit(0);
        }
    } while (cord <= 4);
    return 0;
}
目录
相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
134 9
|
24天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
11天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
29 5
|
27天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
50 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
38 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
22 1