头条超市

2.线性结构（下）——栈和队列

2024-07-29 13:15 由 renYwen 发表于 #其他

线性结构（下）：栈和队列

1.栈

  • 只允许在一端插入和删除的线性表

  • 允许插入和删除的一端称为栈顶 (top)，另一端称为栈底(bottom)

  • 特点：后进先出，LIFO（Last In First Out）

    栈的基本抽象数据类型实现：

    template <class E> 
class Stack 
{	
public:
     Stack ( int = 10 );		             //构造函数
     virtual void Push(const E& item) = 0;    //进栈
     virtual E Pop(E& x) = 0;                 //出栈
     virtual E GetTop(E& x) = 0;              //取栈顶元素
     virtual void MakeEmpty() = 0;           //置空栈
     virtual int IsEmpty() const = 0;        //判栈空否
     virtual int IsFull() const = 0;         //判栈满否
};

1.顺序栈

栈的数组表示 :

顺序栈类实现：

template <class E> 
class SeqStack : public Stack<E> 
{
private:
    int top;	             //栈顶指针
    E *elements;	         //栈元素数组
    int maxSize;	         //栈最大容量
    void OverflowProcess();	 //栈的溢出处理
public:
    SeqStack (int sz = 10) { elements = new E[sz];}   
    ~SeqStack ( ) { delete[] elements; }
    void Push (const E& x);             //进栈    
    bool Pop (E& x);              //出栈
    bool GetTop (E& x);           //取栈顶
    void MakeEmpty ( ) { top = -1; }   //置空栈
    int IsEmpty ( ) const { return top == -1; } 
    int IsFull ( ) const { return top == maxSize-1; }	
};


template <class E>
void SeqStack<E>::OverflowProcess() 
{
//私有函数,当栈满则执行扩充栈存储空间处理
     E *newArray = new E[2*maxSize]; //创建更大的存储数组
	 for (int i = 0; i <= top; i++) 
          newArray[i] = elements[i];
	 maxSize += maxSize;  
     delete [ ]elements;  
     elements = newArray;  	         //改变elements指针
}; 

template <class E>
void SeqStack<E>::Push(const E& x) 
{   
//若栈不满,则将元素x插入该栈栈顶,否则溢出处理
	  if (IsFull()) overflowProcess();	      //栈满
	  elements[++top] = x;	                  //栈顶指针先加1, 再进栈
}; 

template <class E>
bool SeqStack<E>::Pop(E& x) 
{
//函数退出栈顶元素并返回栈顶元素的值
	  if (IsEmpty()) return false;
	  x = elements[top--];	 //栈顶指针退1
      return true;		     //退栈成功
};	 

template <class E>
bool Seqstack<E>::GetTop(E& x) 
{
//若栈不空则函数返回该栈栈顶元素的地址
	 if (IsEmpty()) return false;
	 x = elements[top];
     return true;
};

如何合理进行栈空间分配，以避免栈溢出或空间的浪费？

2.双栈

双栈共享一个栈空间（多栈共享栈空间）

  • 两个栈共享一个数组空间V[maxSize]
  • 设立栈顶指针数组 t[2] 和栈底指针数组 b[2] ，存储元素为整型，t[i]和b[i]分别指示第 i 个栈的栈顶与栈底
  • 初始 t[0] = b[0] = -1, t[1] = b[1] = maxSize
  • 栈满条件：t[0]+1 == t[1] （栈顶指针相遇）
  • 栈空条件：t[0] = b[0]或t[1] = b[1] （栈顶指针退到栈底）

双栈部分函数实现：

//DualStack为双栈结构类，i作为操控的指针数组下标
bool Push(DualStack& DS,const E& x, int i) 
{
     if (DS.t[0]+1 == DS.t[1]) return false;
     if (i == 0) DS.t[0]++; 
     else DS.t[1]--;
     DS.V[DS.t[i]] = x;   
     return true;
}

bool Pop(DualStack& DS, E & x, int i) 
{
     if (DS.t[i] == DS.b[i]) return false;
     x = DS.V[DS.t[i]]; 
     if (i == 0) DS.t[0]--; 
     else DS.t[1]++;
     return true;
}

3.链式栈

  • 链式栈无栈满问题，空间可扩充
  • 插入与删除仅在栈顶处执行
  • 链式栈的栈顶在链头

链式栈类实现：

//栈结点类定义
template <class E>
struct StackNode 
{                                  
    E data;			              //栈结点数据
    StackNode<E> *link;            //结点链指针
    StackNode(const E& d = 0, StackNode<E> *next = NULL)
         : data(d), link(next) { }
};  

//链式栈类定义 
template <class E>
class LinkedStack : public Stack<E> 
{   
private:
	 StackNode<E> *top;		        //栈顶指针
public:
     LinkedStack() : top(NULL) {}	   
	 ～LinkedStack() { MakeEmpty(); }   
	 void Push(const E& x);		    //进栈
	 bool Pop(E& x);			   //退栈
     bool GetTop(E& x) const;		//取栈顶  	
     bool IsEmpty() const { return top == NULL; }
     void MakeEmpty();			    //清空栈的内容
     friend ostream& operator << (ostream& os,LinkedStack<E>& s);   
     //输出栈元素的重载操作 <<
};

template <class E>
void LinkedStack<E>::MakeEmpty() 
{	//逐次删去链式栈中的元素直至栈顶指针为空
    StackNode<E> *current;
	while (top != NULL) { current = top;  top = top->link;  delete current; }
};

template <class E>
void LinkedStack<E>::Push(const E& x) 
{   //将元素值x插入到链式栈的栈顶,即链头
    StackNode<E> *p = top;		     //暂存栈顶元素
    top = new StackNode<E> (x, top);  //创建新结点
    assert (top != NULL);		     //创建失败退出
    top->link = p; 
};

template <class E>
bool LinkedStack<E>::Pop(E& x) 
{
     //删除栈顶结点, 返回被删栈顶元素的值
     if (IsEmpty()) return false;   //栈空返回
  	 StackNode<E> *p = top;		 //暂存栈顶元素
	 top = top->link;			//退栈顶指针
	 x = p->data;   
     delete p;		//释放结点
     return true;	
};

template <class E>
bool LinkedStack<E>::GetTop(E& x) const 
{	
	 if (IsEmpty()) return false;   //栈空返回
	 x = top->data;                         //返回栈顶元素的值
     return true;
};

template <class E>
ostream& operator << (ostream& os,LinkedStack<E>& s) 
{
     StackNode<E> * p = s.top;
     while (p != NULL) { os << p->data << endl;  p = p-> link; }
     return os;
};

拓展：卡特兰数在计算出栈序列的应用

例题1：当进栈元素的编号为1, 2, …, n时，可能的出栈序列有多少种？

卡特兰数列通项公式H(n)有：

$$
H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}})
$$

公式的推导较为复杂，感兴趣可以自己尝试

4.栈的应用——表达式的计算

算术表达式有三种表示：

  • 中缀(infix)表达式 <操作数> <操作符> <操作数>，如 A+B；
  • 前缀(prefix)表达式 （又称波兰式） <操作符> <操作数> <操作数>，如 +AB；
  • 后缀(postfix)表达式（又称逆波兰式） <操作数> <操作数> <操作符>，如 AB+；

示例：A + B * (C - D) - E / F

  • 中缀表达式：A + B * (C - D) - E / F

    表达式中相邻两个操作符的计算次序为：优先级高的先计算，优先级相同的自左向右计算

  • 后缀表达式：A B C D - * + E F / -

    在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。

应用后缀表示计算表达式的值

idea：

  1. 从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果
  2. 扫描中遇操作数则压栈
  3. 遇操作符则从栈中退出两个操作数，计算后将结果压入栈最后计算结果在栈顶

例：计算后缀表达式 A B C D - * + E F ^ G / -

第n步 输入 类型 动作 栈内容（结果）
1 置空栈 空
2 A 操作数 进栈 A
3 B 操作数 进栈 A B
4 C 操作数 进栈 A B C
5 D 操作数 进栈 A B C D
6 - 操作符 D、C退栈，计算C-D，结果r1进栈 A B r1
7 * 操作符 r1、B退栈，计算B*r1，结果r2进栈 A r2
8 + 操作符 r2、A退栈，计算A*r2，结果r3进栈 r3
9 E 操作数 进栈 r3 E
10 F 操作数 进栈 r3 E F
11 ^ 操作符 F、E退栈，计算E^F，结果r4进栈 r3 r4
12 G 操作数 进栈 r3 r4 G
13 / 操作符 G、r4退栈，计算r4/G，结果r5进栈 r3 r5
14 - 操作符 r5、r3退栈，计算r3-r5，结果r6进栈 r6

计算后缀表达式实现：

class Calculator
{
    LinkedStack<double>S;
public:
    void Run();
    void DoOperator(char op);
    bool Get2Operands(double& left, double& right);
};

void Calculator::Run()
{
    char ch;
    double newoperand;
    while (std::cin >> ch, ch != ';')
    {
        switch (ch) 
        {
        case '+': case '-': case '*': case '/': case '^':  DoOperator(ch);  break;
        default:  
            if (!isdigit(ch)) { std::cerr << "非法输入!" << std::endl; return; }           
            std::cin.putback(ch);  //将字符放回输入流(放回一个字符)
            std::cin >> newoperand;  //读操作数
            S.Push(newoperand);
        }
    }
    double result;
    S.GetTop(result);
    std::cout << result;
}

void Calculator::DoOperator(char op)
{
    //从栈S中取两个操作数，形成运算指令并计算进栈
    double left, right;  
    if(!Get2Operands(left, right))return; //退出两个操作数
    switch (op) 
    {
    case '+': S.Push(left + right);  break;     //加
    case '-': S.Push(left - right);  break;     //减
    case '*': S.Push(left * right);  break;      //乘
    case '/': 
        if (right != 0.0) { S.Push(left / right); break; }
        else { std::cout << "除数为0!\n";  exit(1); } //除
    case '^': S.Push(std::pow(left, right)); //乘幂
    }
}

bool Calculator::Get2Operands(double& left,double& right) 
{
    //从栈S中取两个操作数
    if (S.IsEmpty())
    {
        std::cerr << "缺少右操作数!" << std::endl; return false;
    }
    S.Pop(right);//先出栈为右操作数
    if (S.IsEmpty())
    {
        std::cerr << "缺少左操作数!" << std::endl; return false;
    }
    S.Pop(left);//后出栈为左操作数
    return true;
}

中缀表达式转化为后缀表达式

resolution:

  1. 先对中缀表达式按运算优先次序加上括号
  2. 再把操作符后移到右括号的后面并以就近移动为原则
  3. 最后将所有括号消去

(也可以利用二叉树中序遍历转化为后序遍历，本节将不涉及)

如中缀表达式：(A+B)D-E/(F+AD)+C

后缀表示： A B + D * E F A D * + / - C +

idea:

  • 使用栈可将表达式的中缀表示转换成它的后缀表示。
  • 为了实现这种转换，需要考虑各操作符的优先级。

规定算术操作符“优先级”如下：

操作符ch ; ( * / % + - )
isp（栈内） 0 1 5 3 6
icp（栈外） 0 6 4 2 1

tips:

  • isp叫做栈内(in stack priority)优先级，icp叫做栈外(in coming priority)优先级
  • 操作符优先级相等的情况只出现在括号配对或栈底的“;”号与输入流最后的“;”号配对时

算法描述（具体实现请自行尝试）：

  1. 操作符栈初始化，将结束符‘;’进栈。然后读入中缀表达式字符流的首字符ch
  2. 重复执行以下步骤，直到ch = ‘;’，同时栈顶的操作符也是‘;’，停止循环
    • 若ch是操作数直接输出，读入下一个字符ch
    • 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：
      • 若 icp(ch) > isp(op)，令ch进栈，读入下一个字符ch。
      • 若 icp(ch) < isp(op)，退栈并输出。（仍需继续比较）
      • 若 icp(ch) == isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。

算法结束，输出序列即为所需的后缀表达式

例：将A + B * (C - D) - E / F转化为后缀表达式

第n步 输入 栈内容（右为栈顶） 优先级比较 输出 行为
1 ; 栈初始化
2 A ; A 操作数A输出，读字符
3 + ; + 大于 ; 操作符+进栈，读字符
4 B ;+ B 操作数B输出，读字符
5 * ;+ * 大于 + 操作符*进栈，读字符
6 ( ;+* ( 大于 * 操作符(进栈，读字符
7 C ;+*( C 操作数C输出，读字符
8 - ;+*( - 大于 ( 操作符-进栈，读字符
9 D ;+*(- D 操作数D输出，读字符
10 ) ;+*(- ) 小于 - - 操作符-退栈并输出
11 ;+*( ) 等于 ( (退栈，消括号，读字符
12 - ;+* - 小于 * * 操作符*退栈并输出
13 ;+ - 小于 + + 操作符+退栈并输出
14 - ; - 大于 ; 操作符-进栈，读字符
15 E ;- E 操作数E输出，读字符
16 / ;- / 大于 - 操作符/进栈，读字符
17 F ;-/ F 操作数F输出，读字符
18 ; ;-/ ; 小于 / / 操作符/退栈并输出
19 ;- ; 小于 - - 操作符-退栈并输出
20 ; ; 等于 ; ;配对，转换结束

2.队列

  • 定义队列是只允许在一端删除，在另一端插入的线性表

  • 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)

  • 特性：先进先出，FIFO（ First In First Out）

队列的基本抽象数据类型实现：

template <class E>
class Queue 
{
public:
     Queue() = default;	      
     ~Queue() = default;	      
     virtual bool EnQueue(const E& x) = 0;           //进队列
     virtual bool DeQueue(E& x) = 0;	      //出队列
     virtual bool GetFront(E& x) = 0;	      //取队头  
     virtual bool IsEmpty() const = 0;	      //判队列空
     virtual bool IsFull() const = 0;	      //判队列满
};

1.顺序队列

队列的数组表示：

  • 进队:新元素在rear处加入，rear = rear + 1
  • 出队:取出下标为 front 的元素，front = front + 1
  • 队空时 rear == front
  • 队满时 rear == maxSize （假溢出）
  • 解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列

顺序队列类实现：

template <class E>
class SeqQueue : public Queue<E>
{	 //队列类定义
protected:
    int rear, front;		   //队尾与队头指针
    E* elements;		       //队列存放数组
    int maxSize;		       //队列最大容量
public:
    SeqQueue(int sz = 10)
        : front(0), rear(0), maxSize(sz) { elements = new E[sz]; }
    ~SeqQueue() { delete[] elements; }
    bool EnQueue(const E& x);     //新元素进队列
    bool DeQueue(E& x);           //退出队头元素
    bool GetFront(E& x);	      //取队头元素值
    void MakeEmpty() { front = rear = 0; }
    bool IsEmpty() const { return front == rear; }
    bool IsFull() const { return rear == maxSize; }
    int GetSize() const { return rear - front; }
};

template<class E>
inline bool SeqQueue<E>::EnQueue(const E& x)
{
    if (IsFull())return false;
    elements[rear++] = x;
    return true;
}

template<class E>
inline bool SeqQueue<E>::DeQueue(E& x)
{
    if (IsEmpty())return false;
    x = elements[front++];
    return true;
}

template<class E>
inline bool SeqQueue<E>::GetFront(E& x)
{
    if (IsEmpty())return false;
    x = elements[front];
    return true;
}

2.循环队列

  • 队列存放数组被当作首尾相连的表处理

  • 队头、队尾指针在maxSize-1位置时候，加1直接进到0,可用取模运算实现

  • 队头指针进1: front = (front+1) % maxSize

  • 队尾指针进1: rear = (rear+1) % maxSize

  • 队列初始化：front = rear = 0

  • 队空条件：front == rear

  • 队满条件：(rear+1) % maxSize == front

    在SeqQueue类部分函数中稍作修改即可，请自行尝试

3.链式队列

队列的链接表示：

  • 队头在链头，队尾在链尾
  • 链式队列在进队时无队满问题，但有队空问题
  • 队空条件为 front == NULL

template<class E>
struct QueueNode
{   //队列结点类定义	
    E data;			             //队列结点数据
    QueueNode<E>* link;           //结点链指针
    QueueNode(const E& x = 0, QueueNode<E>* next = NULL) : data(x), link(next) {}
};

//链式队列
template <class E>
class LinkedQueue 
{
private:
    QueueNode<E>* front, * rear;   //队头、队尾指针
public:
    LinkedQueue() : rear(NULL), front(NULL) { }
    ~LinkedQueue() { MakeEmpty(); }
    bool EnQueue(const E& x);
    bool DeQueue(E& x);
    bool GetFront(E& x);
    void MakeEmpty();            
    bool IsEmpty() const { return front == NULL; }
};

template<class E>
inline bool LinkedQueue<E>::EnQueue(const E& x)
{
    //将新元素x插入到队列的队尾
    if (front == NULL) {  //创建第一个结点
        front = rear = new QueueNode<E>(x);
        if (front == NULL) return false;//分配失败
    }	 
    else {  //队列不空, 插入
        rear->link = new QueueNode<E>(x);
        if (rear->link == NULL) return false;
        rear = rear->link;
    }
    return true;
}

template<class E>
inline bool LinkedQueue<E>::DeQueue(E& x)
{
    //如果队列不空，将队头结点从链式队列中删去
    if (IsEmpty()) return false;  //判队空
    QueueNode<E>* p = front;
    x = front->data;  front = front->link;
    delete p;   
    return true;
}

template<class E>
inline bool LinkedQueue<E>::GetFront(E& x)
{
    //若队列不空，则函数返回队头元素的值 
    if (IsEmpty()) return false;  //判队空
    x = front->data; 
    return true;
}

template<class E>
inline void LinkedQueue<E>::MakeEmpty()
{
    QueueNode<E>* p;
    while (front != NULL) 
    {   //逐个结点释放
        p = front;  front = front->link;  delete p;
    }
}

4.队列的应用——逐行打印二项展开式 (a + b)^i 的系数：

杨辉三角形 (Pascal’s triangle):

分析第 i 行元素与第 i+1行元素的关系: 从前一行的数据可以计算下一行的数据

思路：从队首取元素t，与元素s相加结果压入队尾，再更新s的值为t

例题2：利用队列实现打印二项展开式系数的算法。

//二项式n次方展开系数
void YANGHUI(int n)
{
    if (n == 1) { std::cout << 1 << ' ' << 1; return; }
    LinkedQueue<int>q;                      //队列初始化
    q.EnQueue(1); q.EnQueue(1);
    int s = 0, t;
    for (int i = 1; i < n; i++) {            //逐行计算
        q.EnQueue(0);
        for (int j = 1; j <= i + 2; j++) {     //下一行
            q.DeQueue(t);    //出队并更新t
            q.EnQueue((s + t));
            if (i == n - 1) std::cout << s + t << ' ';
            s = t;           //更新s
        }
    }
}

3.优先级队列（最小堆）

假定数字越小，优先权越高

任务编号 1 2 3 4 5
优先权 20 0 40 30 10
执行顺序 3 1 5 4 2

  • 优先级队列： 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权(优先级)的元素

  • 出现相同的优先权的元素时，按FIFO的方式处理

优先级队列实现（简要但低效的实现，O(n)复杂度）：

//优先级队列
template <class E>
class PrioQueue
{
private:
    E* elements;	       //存放数组
    int count;	           //队列元素计数
    int maxSize;           //最大元素个数
    void Adjust();         //调整
public:
    PrioQueue(int sz = 10):maxSize(sz),count(0)
    {
        elements = new E[maxPQSize];assert(elements != NULL);
    };
    ~PrioQueue() { delete[] elements; }
    bool Insert(const E& x);
    bool RemoveMin(E& x);
    bool GetFront(E& x);
    void MakeEmpty() { count = 0; }
    bool IsEmpty() const { return count == 0; }
    bool IsFull() const {return count == maxSize;}
    int Length() const { return count; }
};


template<class E>
inline void PrioQueue<E>::Adjust()
{
    E temp = elements[count - 1];
    //将最后元素暂存再从后向前找插入位置
    int j = 0;
    for (j = count - 2; j >= 0; j--) {
        if (elements[j] <= temp) break;
        else elements[j + 1] = elements[j];
    }
    elements[j + 1] = temp;
}

template<class E>
inline bool PrioQueue<E>::Insert(const E& x)
{
    if (IsFull()) return false;   
    elements[count++] = x; Adjust();   
    return true;
}

template<class E>
inline bool PrioQueue<E>::RemoveMin(E& x)
{
    if (IsEmpty()) return false;
    x = elements[0];       //取出0号元素
    for (int i = 1; i < count; i++)
        elements[i - 1] = elements[i];
    //从后向前逐个移动元素填补空位
    count--;
    return true;
}

template<class E>
inline bool PrioQueue<E>::GetFront(E& x)
{
    if (IsEmpty()) return false;
    x = elements[0];       
    return true;
}

课后作业

1.请使用两个栈来模拟一个队列。

2.给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。（选做）

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

热门相关：锦绣田园：医女嫁贤夫   幻想世界大穿越   隐婚365天：江少，高调宠！   至尊凰妃   伏天剑尊