PPT精品文档---栈与队列.ppt

文档介绍：栈与队列
西安交通大学计教中心
.
1
栈的定义
栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶,另一端称为栈底。
如果多个元素依次进栈,则后进栈的元素必然先出栈,所以堆栈又称为后进先出(LIFO)表。堆栈设有一个栈顶指针标志栈顶位置。
栈示意图
a1
a3
a2
进栈
出栈
top
2
堆栈的主要操作有:
•创建空栈。
•进栈(push)操作: 在栈顶插入元素。
•出栈(pop)操作: 在栈顶删除元素。
•读栈顶元素: 只是读出栈顶元素,并不改变栈内元素。
3
顺序栈
#define STACKSIZE 100 //堆栈最大可分配空间数量
class SqStack{
public:
ElemType data[STACKSIZE]; //存储元素的数组
int top; //栈顶指针,存储栈顶元素的下标
SqStack() { top=-1; } //构造函数
void Push(ElemType x); //入栈操作
void Pop(ElemType &result); //出栈操作
void GetTop(ElemType &result); //取栈顶元素
};
一般将数组的0下标单元作为栈底,将栈顶元素的下标存储在栈顶指针top中,它随着元素进栈出栈而变化。top为-1表示空栈,top等于stacksize-1则表示栈满。
4
(1)进栈操作
若栈不满,则在栈顶插入元素x作为新的栈顶。
void SqStack::Push(ElemType x)
{
if( top < stacksize-1)
{
top++;
data[top]=x;
}
else cout<<”栈满”;
}
5
(2)出栈操作
若栈不空,则删除栈顶元素,用result返回其值。
void SqStack::Pop(ElemType &result)
{
if(top > -1)
{
result= data[top];
top--;
}
else cout<<"栈空";
}
6
(3)取栈顶元素
若栈不空,则用result返回栈顶元素。
void SqStack::GetTop(ElemType &result )
{
if(top > -1) {
result= data[top];
}
else cout<<"栈空";
}
7
链式栈
栈的链式存储结构实质上就是一个无头结点、只能在头部插入、删除元素的单链表。
typedef struct node{
ElemType data; //数据域
struct node *next; // 指针域
}SNode;
class LinkStack{
public:
SNode* top; //栈顶指针
LinkStack() { top=NULL; } //构造函数
void Push(ElemType x); //入栈操作
void Pop(ElemType &result); //出栈操作
};
8
(1)进栈操作
若栈不满,则在栈顶插入元素x作为新的栈顶。
void LinkStack::Push(ElemType x)
{
SNode *p=new SNode;
if(p!=NULL) {
p->data=x;
p->next=top;
top=p;
}
}
9
(2)出栈操作
若栈不空,则删除栈顶元素,用result返回其值。
void LinkStack::Pop(ElemType &result);
{
SNode *p;
if(top!=NULL){
result = top->data;
p=top;
top=top->next;
delete p;
}
}
10