第三章笔记——栈和队列_栈和队列的逻辑结构及其对应操作特性的区别和联系

栈和队列

栈的逻辑结构
栈：限定仅在表尾进行插入和删除操作的线性表。
空栈：不含任何数据元素的栈。
允许插入和删除的一端称为栈顶，另一端称为栈底
（a1, a2, ……, an）
栈底 ———— 栈顶

栈的操作特性：先进后出
栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。

---

栈的抽象数据类型定义
ADT Stack
Data
栈中元素具有相同类型及后进先出特性，
相邻元素具有前驱和后继关系
Operation
InitStack
前置条件：栈不存在
输入：无
功能：栈的初始化
输出：无
后置条件：构造一个空栈
DestroyStack
前置条件：栈已存在
输入：无
功能：销毁栈
输出：无
后置条件：释放栈所占用的存储空间
Push
前置条件：栈已存在
输入：元素值x
功能：在栈顶插入一个元素x
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，栈顶增加了一个元素
Pop
前置条件：栈已存在
输入：无
功能：删除栈顶元素
输出：如果删除成功，返回被删元素值，否则，抛出异常
后置条件：如果删除成功，栈减少了一个元素
GetTop
前置条件：栈已存在
输入：无
功能：读取当前的栈顶元素
输出：若栈不空，返回当前的栈顶元素值
后置条件：栈不变
Empty
前置条件：栈已存在
输入：无
功能：判断栈是否为空
输出：如果栈为空，返回1，否则，返回0
后置条件：栈不变
endADT

---

栈的顺序存储结构及实现
顺序栈——栈的顺序存储结构
利用数组实现顺序存储
1，确定用数组那一端表示栈底
2，附设指针top指示栈顶元素在数组中的位置
进栈：top加1
栈空：top= -1
出栈：top减1
栈满：top= MAX_SIZE-1

顺序栈类的声明

const  int  MAX_SIZE=100;
template  <class T>
class  seqStack
{
    public:
        seqStack ( ) ;
        ~seqStack ( );
        void  Push ( T  x );
        T   Pop ( );
        T   GetTop ( );
        bool  Empty ( );
    private:
        T  data[MAX_SIZE];
        int  top;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

顺序栈的实现：
1，入栈
操作接口： void Push( T x );

template <class T>
void  seqStack<T>::Push ( T  x)
{
     if (top==MAX_SIZE-1)  throw  “溢出”;
     top++;
     data[top]=x;
 } 

1
2
3
4
5
6
7
8

2，判空
操作接口： bool Empty( )

template <class T>
bool  seqStack<T>::Empty ()
{
     if (top==-1)  
         return true;
     return false;
 } 

1
2
3
4
5
6
7
8

3，取栈顶
操作接口： T GetTop( );

template <class T>
T  seqStack<T>::GetTop ( )
{
     if (Empty()) throw  ”空栈” ；
     return data[top];
 } 

1
2
3
4
5
6
7

4，出栈
操作接口： T Pop( );

template  <class  T>
T  seqStack<T>:: Pop ( )
{
     if (top==-1)  throw  “溢出”; 
     x=data[top];
      top--;
     return  x;
}

1
2
3
4
5
6
7
8
9

---

双端栈
1，直接解决：为每个栈开辟一个数组空间
2，顺序栈单向延伸——使用一个数组来存储两个栈

两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。

栈1的底固定在下标为0的一端；
栈2的底固定在下标为StackSize-1的一端。
top1和top2分别为栈1和栈2的栈顶指针；
Stack_Size为整个数组空间的大小
两站共享空间类的声明：

const int Stack_Size=100;  
template <class T>
class BothStack 
{
  public:
       BothStack( );
       ~BothStack( ); 
       void Push(int i, T x);   
       T Pop(int i);          
       T GetTop(int i);       
       bool Empty(int i);     
  private:
       T data[Stack_Size];     
       int top1, top2;        
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

实现——插入
操作接口：void Push(int i, T x) ;

template <class T> 
void BothStack<T>::Push(int i, T x )
{
    if (top1==top2-1) 
  throw "上溢";
    if (i==1) 
  data[++top1]=x;
    if (i==2) 
  data[--top2]=x;
}

1
2
3
4
5
6
7
8
9
10
11

实现——删除
操作接口：T Pop(int i) ;

template <class T>
T BothStack<T>::Pop(int i){
    if (i==1) {   
        if (top1== -1)  throw "下溢";
        return data[top1--];
    }
    if (i==2) {                           
        if (top2==StackSize)   throw "下溢";
        return data[top2++]; 
   }
}

1
2
3
4
5
6
7
8
9
10
11
12

判空算法：

template <class T> 
bool BothStack<T>::Empty(int i)
{  
    if(i==1){
        if(top1==-1)  return 1;
        else  return 0;
    }
    if(i==2) {
        if(top2==StackSize) return 1;
        else  return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

取栈顶算法：

template <class T> 
T BothStack<T>::GetTop(int i)
{
    if(i==1) {
        if (top1!=-1)  return data[top1];
    }
    if(i==2) {
        if(top2!=StackSize)  return data[top2];
   } 
}

1
2
3
4
5
6
7
8
9
10
11

---

栈的链接存储结构及实现
链栈：栈的链接存储结构。
链栈的类声明：

template <class T>
class LinkStack
{    
   public:
         LinkStack( ) {top=NULL;};
         ~LinkStack( );            
         void Push(T x); 
         T Pop( ); 
         T GetTop( );
         bool Empty( );
   private:
         Node<T> *top; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

实现——入栈

template <class T>
void LinkStack<T>::Push(T x)
{
    s=new Node<T>;
    s->data=x; 
    s->next=top; 
   top=s; 
}

1
2
3
4
5
6
7
8
9

实现——出栈

template <class T>
T LinkStack<T>::Pop( )
{
    if (top==NULL)
     throw "下溢";
    x=top->data; 
    p=top; 
    top=top->next;   
    delete p;
    return x;
}
1
2
3
4
5
6
7
8
9
10
11

实现——链栈的析构

template <class T>
LinkStack<T>::~LinkStack( )
{
 while (top)
 {
  Node<T> *p;
  p=top->next;
          delete top;
  top=p;
 }
}
1
2
3
4
5
6
7
8
9
10
11

---

顺序栈和链栈的比较
1，时间性能：
相同，都是常树时间O(1)
2，空间性能：
顺序栈：有元素个数的限制和空间浪费的问题。
链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈 满 ，但是每个元素都需要一个指针域，从而产生了结构性开销。
3，结论：
当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。

---

后续表达式求值算法

从左到右对后缀表达式字符串进行处理，每次处理一个符号
1，若遇到数字，入栈
2，若遇到运算符，栈顶两个数字出栈，执行运算符所定义的运算，并将运算结果入栈
3，重复以上的工作，直到表达式结束，此时，栈中的数字代表最终的值。

中序表达式求值
表达式的组成：操作数(operand) 运算符(operator) 界限符(delimiter)
求值过程：
设置两个栈：
OVS(运算数栈)和OPTR(运算符栈)
自左向右扫描中缀表达式，
遇操作数进OVS，
遇操作符则与OPTR栈顶优先数比较：
OPTR栈顶<当前操作符, 当前操作符进OPTR栈
OPTR栈顶>=当前操作符，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T(i)，T(i)进OVS栈

中序表达式转化为后续表达式
设置一个运算符栈。从左到右依次对中缀表达式中的每个符号进行处理
如果遇到数字，直接输出
如果遇到“（”，则将其入栈
如果遇到运算符a，如果栈顶符号的优先级低于a的优先级，则入栈；否则，栈顶符号出栈，直到栈顶符号的优先级低于a的优先级，此时让a入栈
若遇到“）”，则栈顶符号出栈，直到“（”
重复以上工作，直到表达式结束，此时，将栈里符号全部出栈。

---

特殊线性表——队列
队列的逻辑结构
队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。
空队列：不含任何数据元素的队列
允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。
（a1, a2, ……, an）
队头——————队尾

队列的抽象数据类型定义
ADT Queue
Data
队列中元素具有相同类型及先进先出特性，
相邻元素具有前驱和后继关系
Operation
InitQueue
前置条件：队列不存在
输入：无
功能：初始化队列
输出：无
后置条件：创建一个空队列
DestroyQueue
前置条件：队列已存在
输入：无
功能：销毁队列
输出：无
后置条件：释放队列所占用的存储空间
EnQueue
前置条件：队列已存在
输入：元素值x
功能：在队尾插入一个元素
输出：如果插入不成功，抛出异常
后置条件：如果插入成功，队尾增加了一个元素
DeQueue
前置条件：队列已存在
输入：无
功能：删除队头元素
输出：如果删除成功，返回被删元素值
后置条件：如果删除成功，队头减少了一个元素
GetQueue
前置条件：队列已存在
输入：无
功能：读取队头元素
输出：若队列不空，返回队头元素
后置条件：队列不变
Empty
前置条件：队列已存在
输入：无
功能：判断队列是否为空
输出：如果队列为空，返回1，否则，返回0
后置条件：队列不变
endADT
队列的顺序存储结构及实现
顺序队列：队列的顺序存储结构
（改进出队的时间性能：放宽队列的所有元素必须存储在数组的前n个单元这一条件 ，只要求队列的元素存储在数组中连续的位置。
设置队头、队尾两个指针
队头指针指向队头元素的前一个位置；
队尾指针指向队中最后一个元素 ）
假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。

判断队满：
队满：frontrear
队满的条件：(rear+1) mod QueueSizefront

---

循环队列类的声明

const int QueueSize=100; 
template <class T>    
class CirQueue{ 
  public:
      CirQueue( )； 
      ~ CirQueue( )；
      void EnQueue(T x); 
     T DeQueue( );             
     T GetQueue( ); 
     bool Empty( ){
      if (rear==front) return true;
       return false;
   }；
  private:
     T data[QueueSize];   
     int front, rear;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实现——入队

template <class T>
 void CirQueue<T>::EnQueue(T x)
 {
   if ((rear+1) % QueueSize ==front) throw "上溢";
   rear=(rear+1) % QueueSize;    
   data[rear]=x;                 
 }

1
2
3
4
5
6
7
8

实现—— 出队

template <class T>
T CirQueue<T>::DeQueue( )
{
     if (rear==front) throw "下溢"; 
     front=(front+1) % QueueSize; 
     return data[front];
} 

1
2
3
4
5
6
7
8

实现——读队头元素

template <class T>
T CirQueue<T>::GetQueue( )
{
    if (rear==front) throw "下溢"; 
    i=(front+1) % QueueSize;  
    return data[i];
}

1
2
3
4
5
6
7
8

实现——队列长度

template <class T>
int CirQueue<T>::GetLength( )
{
    if (rear==front) throw "下溢"; 
    len=(rear-front+ QueueSize) % QueueSize;  
    return len;
}

1
2
3
4
5
6
7
8

---

队列的链接存储结构及实现
链队列：队列的链接存储结构
利用单链表实现队列的链接存储–队头指针即为链表的头指针

链队列类的声明：

template <class T>
class LinkQueue
{   
  public:
      LinkQueue( );     
      ~LinkQueue( ); 
      void EnQueue(T x);
      T DeQueue( );       
      T GetQueue( )；
      bool Empty( )；
  private:
      Node<T> *front, *rear;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

实现——构造函数
操作接口： LinkQueue( );

template <class T>
LinkQueue<T>::LinkQueue( )
{
     front=new Node<T>; 
     front->next=NULL;  
     rear=front;
}

1
2
3
4
5
6
7
8

实现——入队
操作接口： void EnQueue(T x);

template <class T>
void LinkQueue<T>::EnQueue(T x)
{ 
    s=new Node<T>; 
    s->data=x; 
    s->next=NULL;
    rear->next=s; 
    rear=s;
}


1
2
3
4
5
6
7
8
9
10
11

实现——出队

template <class T>
T LinkQueue<T>::DeQueue( )
{ 
     if (rear==front) throw "下溢";
     p=front->next; 
     x=p->data; 
     front->next=p->next;        
     delete p;
     if (front->next==NULL) rear=front;   
     return x;
}

1
2
3
4
5
6
7
8
9
10
11
12

---

循环队列和链队列的比较
时间性能:
循环队列和链队列的基本操作都需要常数时间O (1)
空间性能:
循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题
链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销

总结：