chapter 3 Stacks and Queues(数据结构栈和队列)

else
{
s.top++;
s.stack[s.top]=x;
}
}
******上课时请保持课堂的安静，谢谢大家！！！
30.10.2020
× 第11页
数据结构 电子教案 — [ 湖北汽车工业学院 软件教研室 马春江 特别制作 ] 首页 尾页 上页 下页 范例 讨论 考题 帮助 关于 结束
（３）退栈
void pop(seqstack &s)
30.10.2020
× 第9页
数据结构 电子教案 — [ 湖北汽车工业学院 软件教研室 马春江 特别制作 ] 首页 尾页 上页 下页 范例 讨论 考题 帮助 关于 结束
2、栈的五种运算
（1）初始化栈
void inistack(seqstack &s)
{
s.top=0;}源自******上课时请保持课堂的安静，谢谢大家！！！
×
首页 尾页 上页 下页 范例 讨论 考题 帮助 关于 结束
主要内容 栈
队列
这两种结构都是特殊的线性表
******上课时请保持课堂的安静，谢谢大家！！！
30.10.2020
第2页
数据结构 电子教案 — [ 湖北汽车工业学院 软件教研室 马春江 特别制作 ]
×
首页 尾页 上页 下页 范例 讨论 考题 帮助 关于 结束
Operation：
Void inistack(&s) //将栈S置为一个空栈(不含任何元素)
Void Push(&s,x) //将元素X插入到栈S中，也称为 “入栈”、 “插 入”、 “压入”
Void Pop(&s) //删除栈S中的栈顶元素，也称为”退栈”、 “删 除”、 “弹出”

<< " The numbers will be printed in reverse order." << endl; cin >> n; for (int i = 0; i < n; i++) {
cin >> item; numbers.push(item);
} cout << endl << endl; while (!numbers.empty()) {
栈和队列是两种常用的数据类型
Subsection 1 Stack
SPECIFICATION
A stack is a special list in which all insertions and deletions of entries (数据 元素) are executed at one end, called the top of the stack(栈顶). The last entry pushed into a stack is the first one that will be removed（so-called LIFO）.
Error_code outcome = success; if (count == 0) outcome = underflow; else --count; return outcome; }
Example：Reversing(倒转) a list
#include "sq_stack.h " void main() /* Pre: The user supplies an integer n and n decimal numbers.
Section 3 Stack & Queue （栈和队列）

~AStack() { delete [] elements; } // Destructor
void clear() { top = 0; }
注意：这里top在第I个位置
2020/12/12
8
一些重要的条件
栈满：top==maxSize-1； 栈空：top==-1
2020/12/12
9
链式栈
{
private:
int MaxSize;
// 栈中最大元素个数
int top;
// 栈中实际元素个数
T *elements; // 存储栈元素的数组
public:
AStack(int sz =DefaultListSize) // Constructor
{ size = sz; top = 0; elements = new T[sz]; }
virtual void MakeEmpty() = 0; virtual int isEmpty（） virtual int isFull（）=0
};
2020/12/12
5
顺序栈
由于栈是运算受限的线性表，因此 线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈， 它是运算受限的线性表。因此，可用 数组来实现顺序栈。因为栈底位置是 固定不变的，所以可以将栈底位置设 置在数组的两端的任何一个端点；栈 顶位置是随着进栈和退栈操作而变化 的，故需用一个整型变量top
时间上：顺序栈为O(1),链式栈为O(1) 空间上：顺序栈要一个固定的长度，当栈不够
满时，空间浪费；链式栈长度可变，但对于每 个元素需要一个链接域，产生结构性开销。 何时使用顺序栈？ 当要实现多个栈时，可用一个数组存储两个栈， 且最好是一个栈增长时另一个栈缩短。

第三章 栈和队列
（Chapter 3. பைடு நூலகம்tack and Queue)
栈的概念、存储结构及其基本操作
栈的应用举例 队列的概念、存储结构及其基本操作
§3.1 栈
3.1.1 栈的定义及基本运算
• 定义：只能在表尾（栈顶）进行插入和删除操 作进行的线性表。 • 特点: 后进先出(LIFO—Last In First Out )
top 栈顶
an an-1
. . .
a1 ∧
栈底
空栈： top == NULL
16

入栈
LinkStack Push_LS (LinkStack top，datatype x) { StackNode *p ; top p = (StackNode *) malloc (sizeof( StackNode)); p->data = x; top p->next = top; top = p; return top; }
23
2
括号匹配的检验：
问题：两种括号，可以嵌套使用，但不能重叠 解决：使用栈。 ｛（［ ］［ ］）｝ 左括号进栈， 右括号就从栈顶出栈一个左括号， 检查是否能够匹配。 算法开始和结束时，栈都应该是空的。
匹配一个字符串中的左、右括号。如
[ a * ( b + c ) + d ]
( 出栈
( )匹配
[ 出栈
3.1.2 栈的存储及运算实现

顺序栈 -- 栈的顺序存储表示 链栈 -- 栈的链式存储表示

4
1 顺序栈
顺序栈类型的定义 – 本质 顺序表的简化，唯一需要确定的是栈顶、栈底。 – 通常 栈底：下标为0的一端 栈顶：由top指示，空栈时top=-1