第二章 数据结构

//用数组去模拟链表 栈与队列
struct Node{
    int val;
    Node *next;
};//第一种方式是不讲的 这种方式在面试题中比较多
//但是在笔试题中用的不是很多
//因为这种方式在每次新建一个链表的时候都要调用一下new函数

new Node();
//new 一个新的节点这个操作是非常慢的
//一般在笔试题里数据大小一般在10w 100w这个级别
//如果new 10w 100w 就会超时
//如果改进下是可以的 比如new n个节点 但是这样就和数组差不多了




//因为用指针 结构体去做链表的话效率慢

//单链表主要用邻接表 其实是n个链表 主要用来存储图和树
//双链表主要用来优化某些问题


//链表用数组表示
//空节点下标用-1来表示


#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int stk[N], tt;

//插入
stk[++tt] = x;

//弹出
tt--;

//判断栈是否为空
if(tt > 0) not empty
else empty

//栈顶
stk[tt];

// ************************ 队列

// 在队尾插入元素，在队头弹出元素
int q[N], hh, tt = -1;

//插入
q[++tt] = x;

//弹出
hh++;

// 判断队列是否为空
if (hh <= tt) not empty
else empty

// 取出队头元素
q[hh]
// 取出队尾元素
q[tt]