首页 > 其他分享 >【数据结构-栈】栈的基本操作

【数据结构-栈】栈的基本操作

时间：2022-10-25 17:58:08浏览次数：45  
标签：结点 return top 元素 栈顶 链表 基本操作 数据结构

目录

1 顺序表实现栈

两种实现方式：

  • 栈顶指针 top 指向栈顶元素
  • 栈顶指针 top 指向栈顶元素的下一位置

1.1 定义

# define NUM 50 // 栈的容量

typedef struct Stack{
    int data[NUM];
    int top;
} Stack;

1.2 初始化

  • 栈顶指针 top 指向栈顶元素：
void InitStack (Stack &S){
    S.top = -1;
}
  • 栈顶指针 top 指向栈顶元素的下一位置：
void InitStack (Stack &S){
    S.top = 0;
}

1.3 栈空判断

  • 栈顶指针 top 指向栈顶元素：
bool EmptyStack (Stack &S){
    if (S.top == -1) 
        return true;
    else 
        return false;
}
  • 栈顶指针 top 指向栈顶元素的下一位置：
bool EmptyStack (Stack &S){
    if (S.top == 0) 
        return true;
    else 
        return false;
}

1.4 栈满判断

  • 栈顶指针 top 指向栈顶元素：
bool FullStack (Stack &S){
    if (S.top == NUM-1) 
        return true;
    else 
        return false;
}
  • 栈顶指针 top 指向栈顶元素的下一位置：
bool FullStack (Stack &S){
    if (S.top == NUM) 
        return true;
    else 
        return false;
}

1.5 出栈

  • 栈顶指针 top 指向栈顶元素：
bool PopStack (Stack &S, int &x){
    if (S.top == -1) 
        return false;
    
    x = S.data[S.top];
    S.top--;
    
    return true;
}
  • 栈顶指针 top 指向栈顶元素的下一位置：
bool PopStack (Stack &S, int &x){
    if (S.top == 0) 
        return false;
    
    x = S.data[S.top];
    S.top--;
    
    return true;
}

1.6 入栈

  • 栈顶指针 top 指向栈顶元素：
bool PushStack (Stack &S, const int x){
    if (S.top == NUM-1) 
        return false;
    
    S.top++;
    x = S.data[S.top];
    
    return true;
}
  • 栈顶指针 top 指向栈顶元素的下一位置：
bool PushStack (Stack &S, const int x){
    if (S.top == NUM) 
        return false;
    
    S.top++;
    x = S.data[S.top];
    
    return true;
}

1.7 读栈顶元素

  • 栈顶指针 top 指向栈顶元素：
bool GetStackTop (Stack &S, int &x){
    if (S.top == 0) 
        return false;
    
    x = S.data[S.top];
    return true;
}
  • 栈顶指针 top 指向栈顶元素的下一位置：
bool GetStackTop (Stack &S, int &x){
    if (S.top == -1) 
        return false;
    
    x = S.data[S.top-1];
    return true;
}

2 单向链表实现栈

实现方法：

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置（相当于带头结点的链表，头结点正好可以用来记录当前栈存储元素的个数）

【注】“栈顶元素在链表表尾”较难实现，因为单向链表只有后继结点。

2.1 定义

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
#define NUM 50 // 栈的容量

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
} LinkNode, *LinkStack;
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
#define NUM 50 // 栈的容量

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
} LinkNode, *LinkStack;

int count; // 记录栈内当前元素个数

2.2 初始化

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool InitStack (LinkStack &top){
    top = NULL;
    count = 0;
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool InitStack (LinkStack &head){
    head = (LinkNode *) malloc(sizeof(LinkNode));
    if (head == NULL)
        return false;
        
    head->data = 0; // 用来记录当前栈存储元素的个数
    head->next = NULL; // 后继结点为空
    return true;
}

2.3 栈空判断

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
void EmptyStack (LinkStack &top){
    if (top == NULL)
        return true;
    return false;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
void EmptyStack (LinkStack &head){
    if (head->data == 0)
        return true;
    return false;
}

2.4 栈满判断

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：需要借助外部变量 count 实现
void FullStack (LinkStack &head){
    if (count == NUM)
        return true;
    return false;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
void FullStack (LinkStack &head){
    if (head->data == NUM)
        return true;
    return false;
}

2.5 出栈

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool PopStack (LinkStack &top, int &x){
    LinkNode *topNext; // 记录栈顶结点（表头结点）的下一个结点

    if (top == NULL)
        return false;
    
    x = top->data;
    topNext = top->next; // 记录栈顶结点（表头结点）的下一个结点
    free(top);
    
    count--; // 栈内元素个数减少
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool PopStack (LinkStack &head, int &x){
    LinkNode *top; // 记录表头结点的下一个结点（即栈顶结点）
    LinkNode *topNext; // 记录栈顶结点的下一个结点

    if (head->data == 0)
        return false;
    
    top = head->next; // 记录表头结点的下一个结点（即栈顶结点）
    topNext = top->next; // 记录栈顶结点的下一个结点
    x = top->data;
    free(top);
    
    head->data--; // 栈内元素个数减少
    head->next = topNext;
    return true;
}

2.6 入栈

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool PushStack (LinkStack &top, const int x){
    LinkNode *newTop; // 新结点

    newTop = (LinkNode *) malloc(sizeof(LinkNode));
    newTop->data = x;
    newTop->next = top; // 新结点的后继结点指向当前栈顶结点
    
    count++; // 栈内元素增加
    top = newTop; // 新结点作为新的栈顶结点
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool PushStack (LinkStack &head, const int x){
    LinkNode *top; // 记录表头结点的下一个结点（即栈顶结点）
    LinkNode *newTop; // 新结点

    if (head->data == NUM)
        return false;
    
    top = head->next; // 记录表头结点的下一个结点（即栈顶结点）
    topNext = top->next; // 记录栈顶结点的下一个结点
    
    newTop = (LinkNode *) malloc(sizeof(LinkNode));
    newTop->data = x;
    newTop->next = top; // 新结点的下一个结点为当前栈顶结点
    
    head->data++; // 栈内元素个数增加
    head->next = newTop; // 新结点作为表头结点的后继结点
    return true;
}

2.7 读栈顶元素

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool GetStackTop(LinkStack top, int &x){
    if (top == NULL)
        return false;
    
    x = top->data;
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool GetStackTop(LinkStack head, int &x){
    LinkNode *top = head->next;
    
    if (head->data == 0)
        return false;
    
    x = top->data;
    return true;
}

3 双向链表实现栈

实现方法：

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置（相当于带头结点的链表，头结点正好可以用来记录当前栈存储元素的个数）

【注】“栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素的下一位置”没有意义。

3.1 定义

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：
typedef struct LinkNode{
    int data;
    struct LinkNode *prev;
    struct LinkNode *next;
} LinkNode, *LinkStack;

int count;
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
typedef struct LinkNode{
    int data;
    struct LinkNode *prev;
    struct LinkNode *next;
} LinkNode, *LinkStack;

3.2 初始化

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool InitStack (LinkStack &top){
    top = NULL;
    count = 0;
    return true;
}
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：
bool InitStack (LinkStack &top){
    top = NULL;
    count = 0;
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool InitStack (LinkStack &head){
    head = (LinkNode *) malloc(sizeof(LinkNode));
    if (head == NULL)
        return false;
        
    head->data = 0; // 用来记录当前栈存储元素的个数
    head->prev = NULL; // 前驱结点为空
    head->next = NULL; // 后继结点为空
    return true;
}

3.3 栈空判断

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
void EmptyStack (LinkStack &top){
    if (top == NULL)
        return true;
    return false;
}
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：
void EmptyStack (LinkStack &top){
    if (top == NULL)
        return true;
    return false;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
void EmptyStack (LinkStack &head){
    if (head->data == 0)
        return true;
    return false;
}

3.4 栈满判断

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：需要借助外部变量 count 实现
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：需要借助外部变量 count 实现
void FullStack (LinkStack &head){
    if (count == NUM)
        return true;
    return false;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
void FullStack (LinkStack &head){
    if (head->data == NUM)
        return true;
    return false;
}

3.5 出栈

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool PopStack (LinkStack &top, int &x){
    LinkNode *topNext; // 记录栈顶结点（表头结点）的下一个结点

    if (top == NULL)
        return false;
    
    x = top->data;
    topNext = top->next; // 记录栈顶结点（表头结点）的下一个结点
    free(top);
    
    count--; // 栈内元素个数减少
    topNext->prev = NULL;
    top = topNext; // 旧栈顶结点（表头结点）的下一个结点成为新的栈顶结点
    return true;
}
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：
bool PopStack (LinkStack &top, int &x){
    LinkNode *topPrev; // 记录栈顶结点（表尾结点）的上一个结点

    if (top == NULL)
        return false;
    
    x = top->data;
    topPrev = top->prev; // 记录栈顶结点（表尾结点）的上一个结点
    free(top);
    
    count--; // 栈内元素个数减少
    topPrev->next = NULL;
    top = topNext; // 旧栈顶结点（表尾结点）的上一个结点成为新的栈顶结点
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool PopStack (LinkStack &head, int &x){
    LinkNode *top; // 记录表头结点的下一个结点（即栈顶结点）
    LinkNode *topNext; // 记录栈顶结点的下一个结点

    if (head->data == 0)
        return false;
    
    top = head->next; // 记录表头结点的下一个结点（即栈顶结点）
    topNext = top->next; // 记录栈顶结点的下一个结点
    x = top->data;
    free(top);
    
    head->data--; // 栈内元素个数减少
    head->next = topNext; // 旧栈顶结点（表头结点）的下一个结点成为新的栈顶结点
    topNext->prev = head; // 新栈顶结点的上一个结点为头结点
    return true;
}

3.6 入栈

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool PushStack (LinkStack &top, const int x){
    LinkNode *newTop; // 新结点

    newTop = (LinkNode *) malloc(sizeof(LinkNode));
    newTop->data = x;
    newTop->prev = NULL;
    newTop->next = top; // 新结点的后继结点指向当前栈顶结点
    
    count++; // 栈内元素个数增加
    top->prev = newTop; // 当前栈顶结点的前驱结点为新结点
    top = newTop; // 新结点作为新的栈顶结点
    return true;
}
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：
bool PushStack (LinkStack &top, const int x){
    LinkNode *newTop; // 新结点

    newTop = (LinkNode *) malloc(sizeof(LinkNode));
    newTop->data = x;
    newTop->prev = top; // 新结点的后继结点指向当前栈顶结点
    newTop->next = NULL;
    
    count++; // 栈内元素个数增加
    top->next = newTop; //当前栈顶结点的后继结点为新结点
    top = newTop; // 新结点作为新的栈顶结点
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool PushStack (LinkStack &head, const int x){
    LinkNode *top; // 记录表头结点的下一个结点（即栈顶结点）
    LinkNode *newTop; // 新结点

    if (head->data == NUM)
        return false;
    
    top = head->next; // 记录表头结点的下一个结点（即栈顶结点）
    
    newTop = (LinkNode *) malloc(sizeof(LinkNode));
    newTop->data = x;
    newTop->prev = head; // 新结点的前驱结点为头结点
    newTop->next = top; // 新结点的后继结点为当前栈顶结点
    
    head->data++; // 栈内元素个数增加
    top->prev = newTop; // 当前栈顶结点的前驱结点指向新结点
    head->next = newTop; // 新结点作为表头结点的后继结点
    return true;
}

3.7 读栈顶元素

  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素：
bool GetStackTop(LinkStack top, int &x){
    if (top == NULL)
        return false;
    
    x = top->data;
    return true;
}
  • 栈顶元素在链表表尾，且栈顶指针 top 指向栈顶元素：
bool GetStackTop(LinkStack top, int &x){
    if (top == NULL)
        return false;
    
    x = top->data;
    return true;
}
  • 栈顶元素在链表表头，且栈顶指针 top 指向栈顶元素的下一位置：
bool GetStackTop(LinkStack head, int &x){
    LinkNode *top = head->next;
    
    if (head->data == 0)
        return false;
    
    x = top->data;
    return true;
}

标签：结点,return,top,元素,栈顶,链表,基本操作,数据结构
From： https://www.cnblogs.com/Mount256/p/16825702.html

相关文章

  • Elasticsearch rest-high-level-client 基本操作
    Elasticsearchrest-high-level-client基本操作本篇主要讲解一下rest-high-level-client去操作Elasticsearch,虽然这个客户端在后续版本中会慢慢淘汰,但是目前大部......
  • 数据结构：线段树基础详解
    1.简介线段树，顾名思义，就是由线段构成的树，是一个较为优秀的数据结构，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点，通常用于解决区间类的问题，在各大......
  • 数据结构之栈
     #include<stdio.h>#include<stdlib.h>/////////////////函数结果状态代码/////////////#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#def......
  • 某高校考研数据结构背诵
    第一章      绪论1.       数据元素之间的关系在计算机中有几种表示方式？各有什么特点？a)      顺序存储方式。数据元素顺序存放，每个存储结点只含......
  • 某高校考研数据结构真题
    真题1.      试说明什么是好的散列函数？“好”的散列函数应满足的条件：①均匀分布，少冲突                                 ......
  • 某高校考研数据结构简单题
    散列表若在散列表中删除一个记录,应如何操作？为什么？答：在散列表中删除一个记录：       在拉链法情况下,可以物理地删除。       在开放定址法情况下,不......
  • Redis数据结构(一)-Redis的数据存储及String类型的实现
    1引言Redis作为基于内存的非关系型的K-V数据库。因读写响应快速、原子操作、提供了多种数据类型String、List、Hash、Set、SortedSet、在项目中有着广泛的使用，今天我们来......
  • Redis数据结构(一)-Redis的数据存储及String类型的实现
    1引言Redis作为基于内存的非关系型的K-V数据库。因读写响应快速、原子操作、提供了多种数据类型String、List、Hash、Set、SortedSet、在项目中有着广泛的使用，今天我们......
  • 数据结构中的基本结构分析
    数据结构一般将数据结构分为两大类：线性结构和非线性结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。线性表线性表的数据结......
  • 数据结构中的基本结构分析
    数据结构一般将数据结构分为两大类：线性结构和非线性结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。线性表线性表的数据结......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99