【C++笔记】数据结构之——栈

数据结构

数据元素是数据的基本单位，数据结构右逻辑结构和物理结构两个概念

逻辑结构

  • 集合
  • 线性结构
  • 树形结构
  • 图状结构或网络结构

物理结构

  • 数据结构的物理结构有两种：顺序存储和链式存储
  • 顺序储存结构：用数据元素在储存器中的相对位置来辨识数据元素之间的逻辑关系
  • 链式存储结构：每一个数据元素中增加一个存放地址的指针，用指针来表示数据元素之间的逻辑关系

基本数据结构——线性表

如栈和队列

存在唯一一个被称作“第一个”的元素；

存在唯一一个被称为“最后一个”的元素

除了第一个元素，集合中每一个元素都有一个“前驱”；

除了最后一个元素每个元素都有一个“后继”

栈

栈(stack)是一种特殊的线性数据结构，栈中的元素是按照入栈顺序线性排列

栈的特点是：后进先出(LIFO，Last In First Out)

栈的应用

例如递归函数。我们调用函数时相当于把函数压到了一个栈里。每次调用栈顶的函数 。一个函数的结束相当于从栈顶被弹出，继续执行栈顶的函数。

C++用数组模拟栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

const int MAX_SIZE=1145;
int Stack[MAX_SIZE];
int top;

bool empty(){
    return top==0;
}

void pushu(int x){
    top++;
    Stack[top]=x;
}

void pop(){
    top--;
}

C++ STL库 栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<stack>
using namespace std;

stack st;

st.empty();//返回栈是否为空
st.top();//返回栈顶的元素
st.push(x);//把x压入栈
st.pop();//把栈顶元素弹出
st.size();//返回元素个数
                
            
例——判断回文字符串
                
#include<iostream>
#include<stack>
using namespace std;
int main(){
    stack stk;
    string str;
    int length=0;
    cin>>str;
    length=str.size();
    for(int i=0;i<length;i++){
        stk.push(str[i]);
    }
    for(int i=0;i<length;i++){
        if(str[i]!=stk.top()){
            cout<<"no";
            return 0;
        }
        stk.pop();
    }
    cout<<"yes";
    return 0;
}