数据结构（三）-栈和队列

1. 栈

• 栈是限定仅在表尾进行插入或删除的线性表
• 表尾称为栈顶，表头称为栈底
• 后进先出
• 栈既然是一种线性结构，就能够以数组或链表（单向链表、双向链表或循环链表）作为底层数据结构
• 操作
  • 压栈：栈的插入操作，叫做进栈，也称压栈、入栈，通常命名为push
  • 弹栈：栈的删除操作，也叫做出栈，通常命名为pop
  • 求栈的大小
  • 判断栈是否为空
  • 获取栈顶元素的值

2. 栈的数组实现

• 以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向
• 代码
  • Stack.h

template<typename T>
class ArrayStack
{
public:
    ArrayStack(int s = 10);    //默认的栈容量为10
    ~ArrayStack();
 
public:
    T top();            //获取栈顶元素
    void push(T t);        //压栈操作
    T pop();            //弹栈操作
    bool isEmpty();        //判空操作
    int size();            //求栈的大小
 
private:
    int count;            //栈的元素数量
    int capacity;        //栈的容量
    T * array;            //底层为数组
};

• Stack.cpp

/*栈的判空操作*/
template <typename T>
bool ArrayStack<T>::isEmpty()
{
     return count == 0; //栈元素为0时为栈空
};
 
/*返回栈的大小*/
 template <typename  T>
int ArrayStack<T>::size()
{
     return count;
};
 
/*插入元素*/
template <typename T>
void ArrayStack<T>::push(T t)
{
     if (count != capacity)    //先判断是否栈满
     {
         array[count++] = t;   
     }
};
 
/*弹栈*/
template <typename T>
T ArrayStack<T>::pop()
{
     if (count != 0)    //先判断是否是空栈
     {
         return array[--count];
     }
};
 
/*获取栈顶元素*/
template <typename T>
T ArrayStack<T>::top()
{
     if (count != 0)
     {
         return array[count - 1];
     }
};

3. 栈的单链表实现

• 以链表为底层的数据结构时，以链表头为作为栈顶较为合适，这样方便节点的插入与删除
• 压栈产生的新节点将一直出现在链表的头部
• 代码实现
  • Stack.h

/*链表节点结构*/
template <typename T>
struct Node
{
    Node(T t) :value(t), next(nullptr){};
    Node() :next(nullptr){};
 
public:
    T value;
    Node<T>* next;
};

/*栈的抽象数据结构*/
template <typename T>
class LinkStack
{
public:
     LinkStack();
     ~LinkStack();
public:
 
     bool isEmpty();
     int size();
     void push(T t);
     T pop();
     T top();
 
private:
 
     Node<T>* phead;
     int count;
};

• Stack.cpp

/*返回栈的大小*/
template <typename T>
int LinkStack<T>::size()
{
     return count;
};
/*栈的判空操作*/
template <typename T>
bool LinkStack<T>::isEmpty()
{
     return count == 0;
};
/*插入元素*/
template<typename T>
void LinkStack<T>::push(T t)
{
     Node <T> *pnode = new  Node<T>(t);
     pnode->next = phead->next;
     phead->next = pnode;
     count++;
};
/*弹栈*/
template <typename T>
T LinkStack<T>::pop()
{
     if (phead->next != nullptr) //栈空判断
     {
         Node<T>* pdel = phead->next;
         phead->next = phead->next->next;
         T value = pdel->value;
         delete pdel;
         count--;
         return value;
     }
};
/*获取栈顶元素*/
template <typename T>
T LinkStack<T>::top()
{
    if (phead->next!=nullptr)
        return phead->next->value;
};

4. 栈的代码题

4.1 数制转换

• 10进制转换为其他进制的数采用取余法，即每次将整数部分除以8，余数为该位权上的数，而商继续除以8，余数又为上一个位权上的数，这个步骤一直持续下去，直到商为0为止，最后读数时候，从最后一个余数起，一直到最前面的一个余数
• 代码

void Conversion(int n) {
    stack<int> stack;
    while (n) {
        stack.push(n % 8);
        n = n / 8;
    }
    while (!stack.empty()) {
        cout << stack.top() << " ";
        stack.pop();
    }
}

4.2 括号匹配的检验

• 代码

void GetCharacter() {
    char a[1024];
    stack<char> character;
    char *s = a;
    character.empty();
    while (*s != '\0') {
        if (*s == '[' || *s == '(') {
            character.push(*s);
        } else {
            if (*s == ']') {
                if (character.top() == '[') {
                    character.pop();
                } else {
                    character.push(*s);
                }
            } else if (*s == ')') {
                if (character.top() == '(') {
                    character.pop();
                } else {
                    character.push(*s);
                }
            }
        }
    }
    if (character.empty()) {
        printf("Character is valid\n");
    } else {
        printf("Character is invalid\n");
    }
}

4.3 汉诺塔问题

• 非递归算法
  • 根据圆盘的数量确定柱子的排放顺序：
    • 若n为偶数，按顺时针方向依次摆放 A B C
    • 若n为奇数，按顺时针方向依次摆放 A C B
  • 然后进行如下操作
    • 按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A
    • 接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
    • 反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。

#include<bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;

struct Hanoi
{
    int n;
    struct Tower
    {
        char Name;
        stack<int> Disks;
    }Tow[3];
    void init(int num)
    {
        n=num;
        for(int i=0;i<3;i++)
        {
            Tow[i].Name='A'+i;
            while(!Tow[i].Disks.empty()) Tow[i].Disks.pop();
        }
        for(int i=n;i>=1;i--) Tow[0].Disks.push(i);
    }
    void solve()
    {
        LL cnt=0,cnt_max=(1<<n)-1;
        while(cnt<cnt_max)
        {
            cnt++;

            int flag1,flag2;
            if(cnt%2)//第奇数次的移动
            {
                for(int i=0;i<3;i++) if(!Tow[i].Disks.empty() && Tow[i].Disks.top()==1) flag1=i;
                if(n%2)//n为奇数
                    flag2=((flag1-1)+3)%3;
                else
                    flag2=(flag1+1)%3;
            }
            else//第偶数次的移动
            {
                flag1=flag2=-1;
                for(int i=0;i<3;i++)
                {
                    if(!Tow[i].Disks.empty() && Tow[i].Disks.top()==1) continue;

                    if(flag1==-1) flag1=i;
                    else if(flag2==-1) flag2=i;
                }

                if(!Tow[flag1].Disks.empty() && !Tow[flag2].Disks.empty())
                {
                    if(Tow[flag1].Disks.top()>Tow[flag2].Disks.top()) swap(flag1,flag2);
                }
                else
                {
                    if(Tow[flag1].Disks.empty()) swap(flag1,flag2);
                }
            }

            cout<<cnt<<": "<<"Move disk "<<Tow[flag1].Disks.top()<<" from "<<Tow[flag1].Name<<" to "<<Tow[flag2].Name<<endl;
            Tow[flag2].Disks.push(Tow[flag1].Disks.top());
            Tow[flag1].Disks.pop();
        }
    }
}hanoi;
int main()
{
    int n;
    cout<<"输入圆盘个数:"; cin>>n;
    hanoi.init(n);
    hanoi.solve();
}

• 递归算法
  • 设Hanoi(n,a,c,b)表示n个圆盘在a柱上，通过服从汉诺塔规则的若干步骤移动，在b柱的辅助下，全部按原顺序移动到了c柱上

#include<bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;

LL cnt;

void Hanoi(int n,char a,char c,char b)
{
    if(n==1)
    {
        cout<<++cnt<<": "<<"Move disk "<<n<<" from "<<a<<" to "<<c<<endl;
        return;
    }

    Hanoi(n-1,a,b,c);
    cout<<++cnt<<": "<<"Move disk "<<n<<" from "<<a<<" to "<<c<<endl;
    Hanoi(n-1,b,c,a);
    return;
}

int main()
{
    int n;
    cout<<"输入圆盘个数:";
    cin>>n;
    cnt=0;
    Hanoi(n,'A','C','B');
}

5. 队列

• 先进先出
• 允许插入的一端叫队尾，允许删除的一端叫队头

6. 队列题

6.1 用两个栈实现队列

• 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作

• in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序

  • push 元素时，始终是进入栈，pop 和 peek 元素时始终是走出栈
  • pop 和 peek 操作，如果出栈为空，则需要从入栈将所有元素移到出栈，也就是调换顺序，比如开始push的顺序是 3-2-1，1 是最先进入的元素，则到出栈的顺序是 1-2-3，那 pop 操作拿到的就是 1，满足了先进先出的特点
  • pop 和 peek 操作，如果出栈不为空，则不需要从入栈中移到数据到出栈

• 代码

void StackAsQueue(std::vector<int> data) {
    if (data.size() < 1) {
        return;
    }
    stack<int> inStack;
    stack<int> outStack;
    inStack.empty();
    outStack.empty();
    for (std::vector<int>::iterator iter = data.begin(); iter != data.end(); iter ++) {
        inStack.push((*iter));
    }
    while (!inStack.empty()) {
        outStack.push(inStack.top());
        inStack.pop();
    }
}