3-栈和队列

System.exit(1);
}
栈顶指针top的初始值决
top=-1;
定了后续其他方法的实现
stackArray=(T[])new Object[n];
}
【算法3-2】入栈
public void push(T obj)
{
if(top==stackArray.length-1){
T []p=(T[])new Object [top*2];
(b)元素a2入栈
an … … a2 a1
(c)元素an入栈
an-1 … a2 a1
(d)元素an出栈
a2 a1
(e)元素a3出栈
a1
(f)元素a2出栈
【例3-1】一个栈的输入序列是1、2、3、4、5，若在 入栈的过程中允许出栈，则栈的输出序列4、3、5、1、 2可能实现吗？1、2、3、4、5的输出呢？
型 正序遍历：依次访问栈中每个元素并输出
3.1.2 顺序栈
顺序栈泛型类的定义如下：
public class sequenceStack<T> {
顺序栈中一维数组 的初始长度
final int MaxSize=10;
private T[] stackArray; 存储元素的数组对象
private int top;
public void nextOrder() {
for(int i=top;i>=0;i--) System.out.println(stackArray[i]);
}
【算法3-8】清空栈操作
public void clear() {
top=-1; }
3.1.3 链栈
栈的链接存储结构称为链栈。结点类的定义，同 第二章Node类。

04 栈和队列的比较与选择
栈和队列的区别
01 02
操作方向
栈是后进先出（LIFO）的数据结构，只允许在固定的一端进行插入和删 除操作；而队列是先进先出（FIFO）的数据结构，允许在两端进行插入 和删除操作。
限制性
栈的操作是有记忆性的，只能按照后进先出的顺序进行操作，而队列没 有这种限制。
03
应用场景
链表实现栈
链表实现栈的原理
使用链表来存储栈中的元 素，通过指针来访问和操 作栈顶元素。
链表实现栈的优点
插入和删除操作效率高， 不需要移动大量元素。
链表实现栈的缺点
空间利用率较低，因为链 表中的节点通常会有一些 额外的空间开销。
栈的常见操作
push：将一个元素压入栈顶。
pop：删除栈顶元素并返回 其值。
数据流处理：在数据流处理中，使用 队列来缓冲数据，以便按顺序处理数 据。
02 栈的实现方式
数组实现栈
01
02
03
数组实现栈的原理
使用数组来存储栈中的元 素，通过索引来访问和操 作栈顶元素。
数组实现栈的优点
空间利用率高，因为数组 的大小是固定的，不会造 成空间的浪费。
数组实现栈的缺点
在某些情况下，插入和删 除操作可能需要移动大量 元素，效率较低。
02
01
03
peek/top：返回栈顶元素的 值，但不删除它。
isEmpty：判断栈是否为空。
04
05
size/length：返回栈中元素 的数量。
03 队列的实现方式
数组实现队列
总结词
数组实现队列时，队列的头部和尾部操作都能够在常数时间内完成，但队列的 长度固定，无法动态扩展。

top top 栈空 F E D C B A
栈满 top-base=stacksize
top
F
E
D C B
top top top top top top base
入栈PUSH(s,x):s[top++]=x; top 出栈 POP(s,x):x=s[--top]; top
base
4
A
3.1 栈
例1：一个栈的输入序列为1,2,3，若在入栈的过程中 允许出栈，则可能得到的出栈序列是什么？ 答： 可以通过穷举所有可能性来求解：
3.2 栈的应用举例
二、表达式求值
“算符优先法”
一个表达式由操作数、运算符和界限符组成。 # 例如：3*（7-2*3） （1）要正确求值，首先了解算术四则运算的规则 a.从左算到右 b.先乘除后加减 c.先括号内，后括号外 所以，3*（7-2*3）=3*(7-6)=3*1=3
9
3.2 栈的应用举例
InitStack(S); while (!QueueEmpty(Q))
{DeQueue(Q,d);push(S,d);}
while (!StackEmpty(S)) {pop(S,d);EnQueue(Q,d);} }
第3章 栈和队列
教学要求：
1、掌握栈和队列的定义、特性，并能正确应用它们解决实 际问题；
用一组地址连续的存储单元依次存放从队头到队尾的元素， 设指针front和rear分别指示队头元素和队尾元素的位置。
Q.rear 5 4 Q.rear 3 2 3 2 5 4 Q.rear 3 3 5 4 5 4
F E D C
C B A
Q.front
2 1 0
C B
Q.front 2 1 0

an
队头
队尾
队列示意图
入队
13
2、队列的基本运算
初始化队列 INIQUEUE(&Q)
将队列Q设置成一个空队列。
入队列
ENQUEUE(&Q,X)
将元素X插入到队尾中，也称“进队” ，“插入”。
出队列
DLQUEUE(&Q)
将队列Q的队头元素删除，也称“退队”、“删除”。
取队头元素 GETHEAD(Q)
也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。
3
2、栈的运算
初始化栈：INISTACK(&S)
将栈S置为一个空栈(不含任何元素)。
进栈：PUSH(&S,X)
将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压 入”。
出栈： POP(&S)
删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹 出”。
9
三、链栈
typedef struct Lsnode { ElemType data;
struct Lsnode *next; } Lsnode *top;
一个链表栈由ቤተ መጻሕፍቲ ባይዱ顶指针top唯一确定。
10
1、链栈的主要运算
进栈操作 void Push(Lsnode *top; ElemType x)
{ p=(Lsnode *)malloc(sizeof(Lsnode)); p->data=x; p->next=top->next; top->next=p; }/*Push*/
第3章 栈和队列
1
栈和队列是二种特殊的线性表。是操作受 限的线 性表。 一、栈