知识点

1.栈和队列的定义和特点

1.1、栈的定义和特点

• 栈（stack）是限定仅在表尾进行插入或删除操作的线性表。
• 对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。
• 先进后出，后进先出

1.2、队列的定义和特点

• 队列：受约束的线性表，只允许在队尾插入，在队头删除
• 先进先出，后进后出

2.栈的表示和操作的实现

2.1　栈的类型定义

栈也有两种存储表示方法，分别称为顺序栈和链栈。

2.2　顺序栈的表示和实现

顺序栈的存储结构

//－－－－－ 顺序栈的存储结构－ －－－－
#define MAXSIZE 100 		//顺序栈存储空间的初始分配址
typedef struct{
    SElemType *base; 		//栈底指针
	SElemType *top; 		//栈顶指针
	int stacksize; 			//栈可用的最大容扯
}SqStack;

一、 顺序栈的初始化

【算法步骤】
① 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
② 栈顶指针top初始为base，表示栈为空。
③ stacksize置为栈的最大容量MAXSIZE。

二、顺序栈的入栈：

【算法步骤】
① 判断栈是否满，若满则返回ERROR。
② 将新元素压入栈顶，栈顶指针加1。

三、顺序栈的出栈：

【算法步骤】
① 判断栈是否空，若空则返回ERROR。
② 栈顶指针减1，栈顶元素出栈。

四、顺序栈取栈顶元素：

当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变。

SElemType GetTop(SqStack S)
{//返回S的栈顶元素，不修改栈顶指针
 if(S.top ！ =S.base) //栈非空
　　　return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
}

2.3、链栈的表示和实现

一、链栈的初始化

二、链栈的入栈

三、链栈的出栈

四、链栈取栈顶元素

3.栈与递归

略

4.队列的表示和操作的实现

习题

习题解析