数据结构（Java）--栈和队列

一.栈

1.基础概念

- 栈是指插入和删除运算被限制在表的一端进行的线性表
- 允许操作的一端称为栈顶
- 不允许操作的一端称为栈底
- 在栈顶插入元素的操作称为入栈
- 删除栈顶元素的操作称为出栈
- 没有元素的栈称为空栈

后进先出 LIFO（last in first out）

栈接口

public interface Stack<T>

{

public abstract boolean isEmpty(); //判空

public abstract void push(T x);// x入栈

public abstract peek(); // 返回栈顶元素，未出栈

public abstract pop(); //出栈，返回栈顶元素

}

2 顺序栈

- 采用顺序存储结构的栈称为顺序栈
- 1. 顺序栈操作的效率分析
    - O(1)

isEmpty()

Push()

Pop()

peek()

- 1. - O（n）

toString()

链式栈
- 采用链式存储结构的栈
- - 链式栈出栈、入栈操作
- 链式栈操作的效率分析
- - O（1）
  - - isEmpty()
    - Push()
    - Pop()
    - peek()
  - O(n)
  - - toString()
栈的应用
1. 栈是嵌套调用机制的实现基础
2. 使用栈以非递归方式实现递归算法

二.队列

基础概念
- 队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行
- 向队列中插入元素的过程称为入队
- 删除元素的过程称为出队
- 允许出队的一端称为对头
- 允许入队的一端称为队尾
- 没有元素的队列称为空队列

先进先出 FIFO（First In First Out）

队列接口

public interface Queue<T>

{

public abstract boolean isEmpty(); //判空

public abstract boolean add(T x ); //x入队

public abstract T peek(); //返回对头，没有删除

public abstract T poll(); //出队，返回对头

}

3.顺序队列

- 采用顺序存储结构的队列称为顺序队列
- 造成假溢出

4.顺序循环队列

、

（1）对头、队尾元素下标按照循环规律变化

front=（front+1）%length；

real=（real+1）%length；

（2）约定rear含义及队列空条件

约定rear是下一个入队元素位置

队列空条件是：rear==front

（3）约定队列满条件

约定队列满条件是队列中仍有一个空位置。

fr ont==（rear+1）%length；

5.顺序循环队列类（Sequence.java）

操作的效率分析：

- - - 时间复杂度O（1）
    - - isEmpty();
      - add();
      - poll();
      - peek();
    - 时间复杂度O（n）
    - - toString();

6.链式队列表

操作的效率分析：

- - - 时间复杂度O（1）
    - - isEmpty();
      - add();
      - poll();
      - peek();
    - 时间复杂度O（n）
    - - toString（）；

数据结构（Java）--栈和队列

相关推荐