​ 栈和队列都是线性表，但是插入和删除位置被限定了

栈(Stack)

​ 插入和删除操作只能在表尾进行，先进后出，简称LIFO结构

  • 表尾an称为栈顶Top，表头a1称为栈底Base
  • 插入元素到栈顶的操作称为入栈PUSH，删除栈顶最后一个元素称为出栈POP
  • 有顺序栈和链栈两种方式，顺序栈更常见
  • 为方便操作，top指针一般指向栈顶上一个的元素，此时top - base = size，初始时top = base

顺序栈

结构

1
2
3
4
5
typedef struct {
    int stacksize;
    int *top;
    int *base;
}SqStack;

Init

top = base说明是空栈，top - base = stackbase说明栈满

1
2
3
4
5
void Init(SqStack &S) {
    S.stacksize = 100;  // 栈的最大长度
    S.base = new int[stacksize];
    S.top = S.base;
}

Clear

进栈时会覆盖原来的值，因此没必要删除

1
2
3
void Cleaer(SqStack & S) {
	if(S.base) S.top = S.base;
}

Destory

1
2
3
4
5
6
void Destory(SqStack &S) {
    delete S.base;
    S.stacksize = 0;
    S.base = NULL;
    S.top = NULL;
}

Push

1
2
3
4
5
6
void Push(SqStack &S, int e) {
    if (S.top - S.base != S.stacksize) {  // 判断是否栈满
        *S.top = e;  // 将元素e压入栈顶
        S.top++;  // 栈顶指针加1
    }
}

Pop

1
2
3
4
5
6
7
int Pop(SqStack &S) {
    if (S.top != S.base) {
        S.top--;
        return *S.top;
    }
    return -1;
}

链栈

  • 链栈中next指向的是前驱而不是后继，即an->next = an-1
  • 不需要头结点
  • 链表的头指针就是栈顶

结构

1
2
3
4
typedef struct StackNode {
    int data;
    StackNode *next;
}StackNode, *LinkStack;

Push

1
2
3
4
5
6
void Push(LinkStack &S, int e) {
    StackNode *p = new LinkStack;
    p->data = e;
    p->next = S;  // p称为栈顶
    S = p;  // 修改栈顶指针
}

Pop

1
2
3
4
5
6
7
int Pop(LinkStack &S) {
    LinkStack p = S;
    S = S->next;  // 栈顶指针下移一位
    int e = p->data;
    delete p;
    return e;
}

队列(Queue)

​ 插入只能插在表尾，删除只能删除表头元素，先进先出，简称FIFO结构

  • 表尾称为队尾，表头称为队头
  • 有顺序队和链队两种方式，循环顺序队列更常见
  • 初始时front = rear = 0，rear一般指向队尾后一位

顺序队列

  • 当rear = MAXQSIZE时发生溢出，当front !=0, rear = MAXQSIZE时发生假溢出，即队列中还有空间
  • 使用循环队列来解决假溢出，利用取模运算%
  • 循环队列队空和对满时均有front = rear，如何判断队列已满：设置一个标志来区别队空与队满；另设一个变量记录元素个数；少用一个元素空间，这样当front = (rear + 1) % MAXSIZE时队列已满

结构

采用少用一个空间的方法来区分队满和队空，此时队列长度为(Q.rear + MAXSIZE - Q.front) % MAXSIZE

1
2
3
4
5
6
#define MAXSIZE 100
typedef struct {
    int *base;
    int front;  // 队头指针
    int rear;  // 队尾指针
}SqQueue;

Init

1
2
3
4
5
void Init(SqQueue &Q) {
    Q.base = new int[MAXSIZE];  // 因为Q不是指针，所以不用->而用.
    Q.front = 0;
    Q.rear = 0;
}

xxxxxxxxxx myAxios({    url: ‘http://localhost:8000/‘,    method: ‘POST’,    params:{        name: ‘abc’   },    data: {        age: 18   }}).then(result => {    console.log(result)}).catch(error => {    console.log(error)})js

1
2
3
4
5
void Enter(SqQueue &Q, int e) {
    if ((Q.rear + 1) % MAXSIZE == Q.front) return;  // 判断是否队满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
}

链式队列

结构

1
2
3
4
5
6
7
8
9
10
11
// 链式队列的节点
typedef struct QNode {
    int data;
    QNode *next;
}QNode, *QueuePtr;

// 链式队列
typedef struct {
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

Init

1
2
3
4
void Init(LinkQueue &Q) {
    Q.front = new QNode();
    Q.rear = Q.front;
}

Enter

1
2
3
4
5
6
7
8
void Enter(LinkQueue &Q, int e) {
    QNode *p = new QNode();
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    Q.front->data++;
}

Delete

如果被删除的元素就是最后一个元素(即Q.rear == p)，则要将尾指针移回头指针(Q.rear = Q.front)

1
2
3
4
5
6
7
8
void Delete(LinkQueue &Q) {
    if (Q.front == Q.rear) return;
    QNode *p = Q.front->next; // 使p指向要删除的元素
    Q.front->next = p->next;  // 使front的next指向第二个元素
    if (Q.rear == p) Q.rear = Q.front;
    delete p;
    Q.front->data--;
}

Destroy

1
2
3
4
5
6
7
void Destroy(LinkQueue &Q) {
    while (Q.front) {
        QNode *p =Q.front;
        Q.front = Q.front->next;
        delete p;
    }
}