栈和队列

栈

• 只在一端插入和删除的线性表（栈顶）
• 后进先出（LIFO）

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

template <class T>
void Stack<T>::overflowProcess( ) {
    //私有函数：当栈满则执行扩充栈存储空间处理
    T *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 T>
void Stack<T>::Push(T x) {
    //若栈不满, 则将元素x插入该栈栈顶, 否则溢出处理
    if (IsFull() == true) overflowProcess;
    //栈满
    elements[++top] = x;
}

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

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

• GetTop()
• Push()
• Pop()

时间复杂度：$O(1)$

双栈共享一个栈空间

• 初始：t[0] = b[0] = -1 t[1] = b[1] = maxSize
• 栈满：t[0] + 1 = t[1]
• 栈空：t[0] = b[0] t[1] = b[1]

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

链式栈

• 链式栈的栈顶在链头
• 插入删除在栈顶执行
• 无满栈问题，空间可扩充
• 适合多栈操作

template <class T> class Stack;
template <class T> 
class StackNode {
friend class Stack<T>;
private:
    Type data; //结点数据
    StackNode<T> *link; //结点链指针
public:
    StackNode (T d = 0, StackNode<T> * next = NULL) : data(d), link(next) { }
};

template <class T>
class LinkedStack : public Stack<T> { //链式栈类定义
private:
    StackNode<T> *top; //栈顶指针
    void output(ostream& os, StackNode <E> *ptr, int& i);
    //递归输出栈的所有元素
public:
    LinkedStack() : top(NULL) {} //构造函数
    ～LinkedStack() { makeEmpty(); } //析构函数
    void Push(E x); //进栈
    bool Pop(E& x); //退栈
    bool getTop(E& x) const; //取栈顶
    bool IsEmpty() const { return top == NULL; }
    void makeEmpty(); //清空栈的内容
    int k = 1;
    friend ostream& operator << (ostream& os, LinkedStack<E>& s){output(os, s.top, k);}
    //输出栈元素的重载操作 <<
};

应用

括号匹配

• 左括号对应index入栈
• 碰到右括号将index出栈

#include <iostream.h>
#include <string.h>
#include <stdio.h>
#include “stack.h”

const int maxLength = 100;
void PrintMatchedPairs(char * expression) {
    stack<int> s(maxLength);
    int j, length = strlen(expression);
    for (int i = 1;i<=length; i++) {
        if ( expression[i-1] == '(' ){
            s.Push(i); //左括号, 位置进栈
        } 
        else if ( expression[i-1] == ')' ) { //右括号
            if (s.Pop(j) == true){ //栈不空,退栈成功
                cout << j << "与" << i << "匹配" << endl;
            }
        }
        else{
            cout << "没有" << i << "位置上的右括号匹配的左括号!" << endl;
        }
    }
    while (s.IsEmpty( ) == false) {
        s.Pop(j);
        cout << "没有与第" << j << "个左括号相匹配的右括号!" << endl;
    }
}

表达式计算

• 后缀表达式计算
• 中缀转后缀

栈和递归

• 定义是递归的（阶乘）
• 数据结构是递归的（单链表）
• 问题的解法是递归的（汉诺塔）

队列

• 允许删除的一端是队头（front），允许插入的一端是队尾（rear）
• 先进先出（FIFO）
• 初始化：front = rear + 1
• 进队：rear = rear + 1 新元素插入rear
• 出队：front = front + 1
• 队满：rear = maxSize - 1 （会有假溢出）
• 队空：front = rear

循环队列

• 队头、队尾指针加1进到maxSize - 1 后，再前进一个位置就自动到0，用模运算实现
  • 队头指针进1：front = (front + 1) % maxSize;
  • 队尾指针进1：rear = (rear + 1) % maxSize;
• 初始化：front = rear = 0;
• 队空：front == rear;
• 队满：(rear + 1) % maxSize == front;

int DeQueue (Type& x){	 	//退队
    if (IsEmpty ( )) return 0;
    front = (front+1) % maxSize;
    x = elements[front]; return 1;
}

int GetFront (Type& x){		//取队头元素
    if ( IsEmpty ( ) ) return 0;
    x = elements[( front+1) % maxSize];
    return 1;
}

void MakeEmpty ( ) { front = rear = 0; }

int IsEmpty ( ) const{ 
    return front == rear; 
}

int IsFull ( ) const{ 
    return (rear+1) % maxSize == front; 
}

int Length ( ) const{
    return (rear - front + maxSize) % maxSize;
}

• 时间复杂度
  • 入队：$O(1)$
  • 出队：$O(1)$