清华962数据结构 --- Ch3 栈和队列
一、栈
1、定义
栈是限定仅在表尾进行插入或删除操作的线性表 栈顶:允许插入和删除的一端,对应元素被称为栈顶元素 栈底:不允许插入和删除的一端,对应元素被称为栈底元素
栈是一种 后进先出
的结构
2、基本操作
- InitStack (&S):初始化栈
- DestroyStack (&S):销毁栈
- ClearStack (&S):清空栈
- StackEmpty (S):判断一个栈 S 是否为空
- StackLength (S):返回 S 的元素个数
- GetTop (S, &e):读栈顶元素。若栈 S 非空,则用 e 返回栈顶元素
- Push (&S, e):进栈,若栈 S 未满,则将 e 加入使之成为新栈顶
- Pop (&S,&e):出栈,若栈 S 非空,则弹出栈顶元素,并用 x 返回
注: 不同出栈顺序的数量 n 个元素进栈,出栈元素不同排列的的个数为 (卡特兰数) 可以用数学归纳法进行证明(证明过程)
3、顺序栈
(1)结构定义
#define MaxSize 10
typedef struct SqStack
{
DataType arr[MaxSize];
int top;//栈顶指针
}SqStack;
其中,base 可以成为栈底指针,top 为栈顶指针。若 base 值不存在,则表明栈结构不存在;若 top = base,则表明栈空。
在严书上,对于栈结构的定义与王道中有出入,王道中采用对 top 指针的值进行判别,此处利用双指针。
(2)获取栈顶元素
bool GetTop(SqStack &S, DataType &e)
{
if(S.top==-1)
return false;//栈空
e=S.data[S.top];
return true;
}
(3)入栈
bool Push(SqStack &S, DataType e)
{
if (S.top == MaxSize - 1)
return false; //栈满
S.top += 1;
S.data[S.top] = e;
return true;
}
(4)出栈
bool Pop(SqStack &S, DataType &e)
{
if (S.top == -1)
return false; //栈空
e = S.data[S.top];
S.top -= 1;
return true;
}
(5)共享栈
顺序栈的缺点在于,我们需要在一开始就设定好空间大小,否则扩容起来相当麻烦,有一种解决办法是引入 共享栈
有两个相同类型的栈,如果一个栈空间满了,就可以借助另一个栈的空间。 即可以让一个栈的栈底为“栈”始端,即数组下标 0 处,另一个栈的栈底为“栈”末端,即数组下标 n-1 处,增加元素时,两端点相向而行
判空:top 0 -1 且 top 1 n 判满:top 0 + 1 == top 1
4、链栈
5、栈的应用
(1)括号匹配
遇到左括号就进栈;如果遇到右括号需要进行以下判断:
- 栈空:匹配失败,说明没有与之对应的左括号
- 栈不空,取栈顶元素不匹配:匹配失败,说明左右括号不配对
- 栈不空,取栈顶元素匹配:这一对匹配成功,继续进行下一对
(2)表达式求值
表达式由操作数、运算符和界限符组成 表达式分为三种类型:
- 前缀表达式(波兰式)
- 中缀表达式(平时我们写的)
- 后缀表达式(逆波兰式)
中缀转后缀: OPTR:寄存运算符 OPND:寄存操作数或运算结果
从左往右扫描,遇到操作数就直接入栈 OPND,如果扫描到左括号,直接入栈 OPTR。如果扫描到右括号,则将左右括号之间的所有元素入栈 OPND,同时右括号不入栈、丢弃左括号。 如果扫描到的运算符优先级小于等于 OPTR 在栈顶的优先级,则 OPTR 出栈、入 OPND,再与新的栈顶元素比较,小于等于则重复,大于则入栈 OPTR
void convert(string& express, stack<char> &OPND, stack<char> &OPTR)
{
int i = 0;
while (express[i] != '\0') //扫描中缀表达式
{
if ('0' <= express[i] && express[i] >= '9')//如果扫描到了操作数,直接入 s1
{
OPND.push(express[i++]);
}
else if (express[i] == '(')//如果扫描到了左括号,直接入 s2
{
OPTR.push(express[i++]);
}
else if (express[i] == '+' || express[i] == '-' || express[i] == '*' || express[i] == '/')//扫描到运算符进行优先级判断
{
if (OPTR.empty() || OPTR.top() == '(' || getpriority(express[i]) > getpriority(OPTR.top()))//如果此时 S2 为空或者栈顶元素为左括号,或者扫描到的运算符优先级大于栈顶运算符优先级,则 S2
{
OPTR.push(express[i++]);
}
else//反之优先级如果是小于等于的话,那么就要把运算符出栈然后入 S1
{
char temp = OPTR.top();
OPTR.pop();
OPTR.push(temp);
}
}
else if (express[i] == ')')//最后一种情况就是扫描到了右括号,那么就把 S2 从栈顶到左括号的元素依次出栈入栈
{
while (OPTR.top() != '(')
{
char temp = OPTR.top();
OPTR.pop();
OPTR.push(temp);
}
//注意最后停止循环的时候 S2 的栈顶元素是左括号,但是不要把左括号入栈,所以直接丢掉左括号
OPTR.pop();
i++;//不要忘记后移
}
}
while (!(OPTR.empty()))//如果 S2 没有空,那么依次出 S2,入 S1
{
char temp = OPTR.top();
OPTR.pop();
OPTR.push(temp);
}
}
中缀转前缀: 操作方法基本一致,不同点如下:
- 从右往左进行扫描
- 遇到右括号入栈,左括号出栈
- 扫描到的运算符优先级如果大于等于栈顶运算符优先级,直接入栈
void convert2(string& express, stack<char>& s1, stack<char>& s2)//中缀转前缀
{
int i = express.size()-1;
while (i>=0)//扫描中缀表达式
{
if ('a' <= express[i] && express[i] <= 'z')//如果扫描到了操作数,直接入 s1
{
s1.push(express[i--]);
}
else if (express[i] == ')')//如果扫描到了右括号,直接入 s2
{
s2.push(express[i--]);
}
else if (express[i] == '+' || express[i] == '-' || express[i] == '*' || express[i] == '/')//扫描到运算符进行优先级判断
{
if (s2.empty() || s2.top() == ')' || getpriority(express[i]) >= getpriority(s2.top()))//如果此时 S2 为空或者栈顶元素为左括号,或者扫描到的运算符优先级大于等于栈顶运算符优先级,则入 S2
{
s2.push(express[i--]);
}
else//反之优先级如果是大于等于的话,那么就要把运算符出栈然后入 S1
{
char temp = s2.top();
s2.pop();
s1.push(temp);
}
}
else if (express[i] == '(')//最后一种情况就是扫描到了左括号,那么就把 S2 从栈顶到右括号的元素依次出栈入栈
{
while (s2.top() != ')')
{
char temp = s2.top();
s2.pop();
s1.push(temp);
}
//注意最后停止循环的时候 S2 的栈顶元素是右括号,但是不要把右括号入栈,所以直接丢掉右括号
s2.pop();
i--;//不要忘记后移
}
}
while (!(s2.empty()))//如果 S2 没有空,那么依次出 S2,入 S1
{
char temp = s2.top();
s2.pop();
s1.push(temp);
}
}
二、队列
1、定义
队列是限定仅在一端插入,在另一端删除的线性表 队尾:允许插入的一端,对应元素被称为队尾元素 队头:允许删除的一端,对应元素被称为队头元素
队列是一种 先进先出
的结构
2、基本操作
InitQueue(&Q)
:初始化队列DestoryQueue(&Q)
:销毁队列ClearQueue
:清空队列QueueEmpty(Q)
:队列判空QueueLength(Q)
:返回队列长度GetHead(Q,&e)
:读队头元素EnQueue(&Q,e)
:入队DeQueue(&Q,&e)
:出队
3、双端队列
可以在两端插入、删除的线性表。其中把允许一端插入、两端删除的称为输入受限的双端队列,把允许两端插入、一端删除的称为输出受限的双端队列
双端队列:只允许从两端插入、两端删除的线性表 输入受限的双端队列:只允许从一端插入、两端删除的线性表 输出受限的双端队列:只允许从两端插入、一端删除的线性表
4、链队
通过两个指针唯一确定一个链队列,front
指针指向头结点,rear
指针指向队尾结点
(1)结构定义
typedef struct QNode//结点
{
DateType data;
struct QNode* next;
}QNode;
typedef struct LinkQueue//链式栈
{
QNode* rear;//队尾指针
QNode& front;//队头指针
}LinkQueue;
(2)入队
bool EnQueue(LinkQueue &Q,DataType e)
{
QNode* NewNode=(QNode*)malloc(sizeof(QNode));
if(NewNode==NULL)
return false;
NewNode->data=e;
NewNode->next=NULL;
Q->rear->next=NewNode;
Q->rear=NewNode;//新节点作为队尾结点
}
(3)出队
bool DeQueue(LinkQueue &Q,DataType &e)
{
Node* p;//用于释放
if(Q.front==Q.rear)
return false;
p=Q.front->next;
*e=p->data;
Q.front->next=p->next;
if(p==Q.rear)//注意如果队头就是队尾,那么删除是空队列
Q.rear=Q.front;
free(p);
return true;
}
5、顺序队列
(1)单纯的顺序队列
与顺序栈类似,我们同样通过两个指针 front
和 rear
指向队头元素和队尾元素
在创建空队列的时候,我们令 front=rear=0,当插入新元素时,队尾指针 +1;删除队头元素时,队头指针 +1。使得头指针始终指向队头元素,尾指针始终指向队尾元素的下一个。
但在该种形式下,当队尾指针到达最后预先分配好的最后一个位置时,无法再插入新的元素,但此时内存的前部仍有许多空的位置尚未使用,形成一种假溢出。
(2)循环队列
为了解决上述的问题,我们提出了循环队列的办法,将顺序队列臆造成一个环状空间。 由于环状空间只是假象的逻辑结构,并不是真实存在的结构,所以我们需要通过出、入队时下标的变换,达到这样的效果:
rear
移动时:rear=(rear+1)%Maxsize)
front
移动时:front=(front+1)%Maxsize)
通过对 Maxsize 其取余,将两个指针的取值范围限定在 0~Maxsize - 1 中结构定义
c typedef struct { DataType data[MaxSize]; int front;//头指针 int rear;//尾指针。若队列不空,指向队尾元素的下一个位置 }SqQueue;
入队 ```c bool EnQueue(SqQueue& Q,DataType e) { if(Q.front==(Q.rear+1)%MaxSize) return false;//队满 Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize;
return true; } ```
出队
c bool DeQueue(SqQueue& Q,DataType& e) { if(Q.front==Q.rear) return false;//队空 *e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; }
判空、判满的条件
- 方案 1:
- 牺牲一个存储空间
- 初始化时
rear=front=0
- 队列元素个数:
(rear+MaxSize-front)%MaxSize
- 队列已满的条件:队尾指针的再下一个位置是队头,即
(Q.rear+1)%MaxSize==Q.front
- 队空条件:
Q.rear==Q.front
- 方案 2:
- 不牺牲一个存储空间,在结构体中多建立一个变量
size
- 初始化时
rear=front=0;size = 0
- 队列元素个数 = size
- 插入成功
size++
,删除成功size--
- 队满条件:
size==MaxSize
- 队空条件:
size == 0
- 不牺牲一个存储空间,在结构体中多建立一个变量
- 方案 3:
- 不牺牲一个存储空间,在结构体中多建立一个变量
tag
- 初始化时
rear=front=0
,tag = 0
- 因为只有删除操作,才可能导致队空,只有插入操作,才可能导致队满
- 每次删除操作成功时,都令
tag=0
- 每次插入操作成功时,都令
tag=1
- 队满条件:
front==rear && tag == 1
- 队空条件:
front==rear && tag == 0
- 队列元素个数:
(rear+MaxSize-front)%MaxSize
- 不牺牲一个存储空间,在结构体中多建立一个变量