当前位置: 首页 > 后台 > C++

栈和队列

作者: admin 2019-12-05 23:45:29 阅读(224) 评论(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;
0 条评论