一、栈

1.1 基本操作

1. bool empty()：返回栈是否为空。
2. bool push(): 入栈。
3. bool pop(): 出栈。
4. eleType top(): 取得栈顶。
5. void clear(): 清空。

1.2 顺序栈的存储结构

#define maxSize 50
typedef struct
{
    elemType data[maxSize];
    int topIdx;     // 存放栈顶指针
}Stack;

1.2.1 init

void init(stack& st)
{
    topIdx = -1;
}

1.2.2 empty

bool empty(stack& st)
{
    return st.topIdx == -1 ?
        true :
        false;
}

1.2.3 push

bool push(stack& st, eleType ele)
{
    if (st.topIdx < maxSize)
    {
        st.data[++st.topIdx] = ele;
        return true;
    }
    return false;
}

1.2.4 pop

bool push(stack& st)
{
    if (st.topIdx >= 0)
    {
        st.topIdx--;
        return true;
    }
    return false;
}

1.2.5 top

eleType top(stack& st)
{
    // 这里忽略了合法性检测
    return st.data[st.topIdx];
}

1.3 栈的链式存储结构

typedef struct stackNode
{
    eleType data;
    struct stackNode *next;   
} *stackList;

  所有操作在头结点执行。

二、队列

2.1 基本操作

1. bool empty(): 查看是否为空。
2. bool push(): 入队（尾部）。
3. bool pop(): 出队（头部）。
4. eleType head(): 取得队头。

2.2 队列的顺序存储结构

2.2.1 顺序队列

#define maxSize 50

typedef struct
{
    eleType data[maxSize];
    int front, back;
}

2.2.2 循环队列

2.2.2.1 基本概念

  教材（王道）提出了前面顺序队列存在“假溢出”的问题，但实际上，那是由于push/pop而没有进行拷贝导致的。

• 初始状态：front = back = 0;
• push: (back + 1) % maxSize;
• pop: (front - 1) % maxSize;
• length: (back + maxSize - front) % maxSize;

  如何区分空队列和满队列？

(1) 牺牲一个单元

• 队满：(back + 1) % maxSize == front;
• 对空：front = back;
• length: (back + maxSize - front) % maxSize

(2)增加一个queue.size元素

2.2.2.2 init

void init(stack& qst)
{
    qst.front = qst.back = 0;
}

2.2.2.3 empty

bool empty(stack& qst)
{
    return qst.back == qst.front ?
        true :
        false;
}

2.2.2.4 push

bool push(stack& qst, eleType ele)
{
    if ((back + 1) % maxSize == front)
    {
        return false;
    }
    qst.data[q.back] = x;
    q.back = (q.back + 1) % maxSize;
    return true;
}

2.2.2.5 pop

bool pop(stack& qst)
{
    if (qst.empty())
    {
        return false;
    }
    qst.front = (q.front + 1) % maxSize;
    return true;
}

2.3 链式队列

  教材上说得罗里吧嗦，这里我们直接做一个双头的链式队列。

template<typename eleType>
class deque
{
private:
    struct node
    {
        eleType data;
        node* next, prior;

        node()
        {
            next = prior = nullptr;
        }
    }

    // 成员
    node* m_front, m_back;
    int m_size;
public:
    deque()
    {
        front = back = nullptr;
        size = 0;
    }

    // 判断为空
    bool empty() const
    {
        return size == 0 ?
            true :
            false;
    }

    // 队尾入队
    void push(const eleType& ele)
    {
        if (this->empty())
        {
            eleType* ins = new eleType;
            ins.data = ele;

            m_front = ele;
            m_back = ele;
        }
        else if (!this->empty())
        {
            eleType* ins = new eleType;
            ins.data = ele;

            m_back->next = ins;
            ins->prior = m_back;

            m_back = ins;
        }

        m_size++;
    }

    // 队首出队
    void pop()
    {
        if (!this->empty())
        {
            auto deletePtr = m_front;
            m_front = m_front->next;

            delete deletePtr;
        }
        m_size--;
    }

    // 获取首元素
    eleType head()
    {
        // 这里最好使用try catch

        eleType re;

        if (!this->empty())
        {
            re = m_front.data;
        }

        return re;
    }

    // 数量
    int size()
    {
        return m_size;
    }
}