栈和队列

后台 C++

作者: admin 2019-12-05 23:45:29 阅读(48) 评论(0)

二. 栈和队列

1. 栈

(1) 概念

栈只能在一端进行插入或者删除操作，插入元素称为入栈，删除元素称为出栈。

在存储结构上分为顺序栈和链栈。主要特点是先进后出（FILO）。

n个元素入栈（满足先进后出原则），所获得的元素排列数目 N 为：

$ N = \frac{1}{n+1}C_{2n}^{n} $

(2) 数据结构

/*顺序栈*/
//top == -1表示栈空，top == maxSize - 1 表示栈满。
typedef struct {
    int data[maxSize]; // 栈中元素
    int top;  // 栈顶指针
}SqStack; // 类型定义

//考试中定义顺序栈并初始化一般这样写
int stack[maxSize];
int top = -1;

//考试中写元素 x 入栈
/*注意 ++top 和 top++ 的区别，两者都能实现自增的效果，但 ++top 的值为自增后的值，而 top++ 的值仍等于自增前的值。--top 和 top--类似。*/
stack[++top] = x;

//考试中写出栈
x = stack[top--];

/*链栈*/
//链栈默认情况下不存在栈满情况，栈空即为栈顶指针的 next 指针域为 NULL
//链栈的入栈相当于单链表头插法，出栈相当于删除单链表元素 
typedef struct LNode {
    int data; // 数据域
    struct LNode *next; // 指针域
}LNode; // 类型定义

2. 队列

(1) 概念

队列只允许在一端（队尾 rear）插入数据（入队），另一端（队头 front）删除数据（出队）。特点是先进先出，类似于隧道。可分为顺序队和链队。

(2) 数据结构

顺序队：

/*顺序队列*/
typedef struct {
    int data[maxSize];
    int front;
    int rear;
}SqQueue;

链队：

/*队结点*/
typedef struct QNode {
    int data; 
    struct QNode *next;
}QNode;

/*链队*/
typedef struct {
    QNode *front;
    QNode *rear;
}LiQueue;

栈和队列

二. 栈和队列

1. 栈

(1) 概念

(2) 数据结构

2. 队列

(1) 概念

(2) 数据结构

Heading 1

Heading 2

Heading 3

Heading 4

Heading 5

Heading 6