栈和队列

#include<iostream>

using namespace std;

//栈和队列的顺序存储结构
//栈：栈顶元素位置:指向最后一个元素，指向最后一个元素的下一个位置
//队列：一般采用循环队列。
//  (a) 队头元素的位置:指向第一个元素,指向第一个元素前一个位置。
//  (b) 队尾元素的位置:指向队尾元素，指向队尾元素的下一个位置

const int N = 110;
//栈
int main(){
    //指向最后一个元素
    int stk[N],top = -1;

    //插入元素
    stk[++ top] = 1;
    stk[++ top] = 2;

    //弹出栈顶元素
    -- top;

    //返回栈顶
    stk[top];

    //判断栈是否为空
    top == -1

    //指向最后一个元素的下一个位置
    int stk[N],top = 0;

    //插入元素
    stk[top ++] = 1;
    stk[top ++] = 2;

    //弹出栈顶元素
    top --;

    //返回栈顶
    stk[top - 1];

    //判断栈是否为空
    top == 0
}

    //循环队列
    //rear指向最后一个元素的下一个位置所以真实队列里最多只能存n - 1个元素
    int q[N],front = 0,rear = 0; // front 指向第一个元素 rear指向最后一个元素的下一个位置(一共四种写法)

    //队列为空
    front == rear

    //队列满
    front = (rear + 1)%N

    //队尾插入队头弹出 出入是不考虑队头
    //由于队尾指向最后一个元素的下一个位置 在插入时 插入一个元素后在指向下一个元素
    //插入
    q[rear ++] = 1;
    rear %= N;

    //弹出
    front = (front + 1) % N;

    //返回队头
    q[front];

    //循环队列
    int q[N],front = 0,rear = -1;//rear指向最后一个元素的位置

    //判断队列为空
    front == rear + 1;

    //满
    front == (rear + 2)

    //插入
    q[++ rear] = 1;
    rear %= N;

    //弹出
    front = (front + 1) % n;

    //队头
    q[front];

#include<iostream>

using namespace std;

//栈和队列的链式存储结构

//栈用单链表 头结点为栈顶 尾结点为栈底，因为尾结点找不到上一个节点所以不能当栈顶

const int N = 110;

struct Node{
    int val;
    Node *next;
    Node(): next(NULL){}
    Node(int _val):val(_val),next(NULL){}
};
void print(Node *p){
    for(auto head = p;p;p = p->next){
        cout << p->val << " ";
    }
    cout << endl;
}
int main(){

    //从栈顶压入
    Node *top = NULL;
    auto a = new Node(1);
    a->next = top;
    top = a;

    auto b = new Node(2);
    b->next = top;
    top = b;

    auto c = new Node(3);
    c->next = top;
    top = c;

    //删除栈顶元素
    top = top->next;
    delete c;

    print(top);

    //返回栈顶元素
    cout << top->val << endl;
}

#include<iostream>

using namespace std;

//栈和队列的链式存储结构

//栈用单链表 头结点为栈顶 尾结点为栈底，因为尾结点找不到上一个节点所以不能当栈顶

const int N = 110;

struct Node{
    int val;
    Node *next;
    Node(): next(NULL){}
    Node(int _val):val(_val),next(NULL){}
};
void print(Node *p){
    for(auto head = p;p->next;p = p->next){
        cout << p->val << " ";
    }
    cout << endl;
}
int main(){

    //队列 设立一个虚拟头尾结点
    Node *front = new Node(),*rear = front;

    rear->val = 1;
    rear->next = new Node();
    rear = rear->next;

    rear->val = 2;
    rear = rear->next = new Node();

    rear->val = 3;
    rear = rear->next = new Node();
    print(front);

    //队头
    cout << front->val << endl;

    //弹出队头
    auto p = front;
    front = front->next;
    delete p;
    print(front);
}