[数据结构与算法]数据结构与算法2-栈与队列

数据结构与算法-栈与队列

往期内容
1-链表
2-栈与队列
3-字符串
4-树
5-图
6-贪心算法
7-递归与分治
8-排序
9-查询
10-动态规划
11-STL库

基本概念

栈：先进后出，后进先出
队列：先进先出，后进后出

一、栈

栈的存储结构有两种：线性顺序结构和链式存储结构

1.1 顺序存储结构

实质是一个线性表

#define MAXSIZE 10
//栈的顺序存储结构
typedef int SElemType;
struct SqStack
{
    SElemType data[MAXSIZE];
    int top;//用于栈顶的指针    
};

1.2 共享栈

线性存储结构必须事先确定数组存储空间的大小，如果不够用，需要扩展数组的容量，非常麻烦。
一个指针指向栈1另一个指向栈2，当top1和top2相差为1栈满

#define MAXSIZE 10
//共享栈
typedef int SElemType;
struct SqStack
{
    SElemType data[MAXSIZE];
    int top1;//用于栈1顶的指针    
    int top2;//用于栈2顶的指针 
};

1.3 链式存储结构

typedef int SElemType;
//链式栈的节点
struct StackNode
{
    SElemType data;
    StackNode *next;//用于栈顶的指针    
};
typedef StackNode *LinkStackPtr;


//链式栈的结构
typedef struct LinkStack
{
    LinkStackPtr top;//指向栈顶的指针
    int count;//计数
}LinkStack;

二、栈基本操作

2.1入栈push

• 顺序存储结构

/*
入栈操作：bool Push(SqStack *S,SElemType e)
功能：将e数据，压入S栈中
*/
bool Push(SqStack *S,SElemType e)
{
    //判断栈是否已经满了
    if(S->top==(MAXSIZE-1))
    {   
        return false;
    }
    (*S).top++;//移动指针
    S->data[S->top]=e;//将元素压入栈中


    return true;
}

• 共享栈

/*
入栈操作：bool Push(SqStack *S,SElemType e,int stackNumber)
功能：将e数据，压入S栈中，第三个参数判断是那个栈压入的数据
*/
bool Push(SqStack *S,SElemType e,int stackNumber)
{
    if(S->top1+1==S->top2)//栈满
    {
        return false;
    }
    if(stackNumber==1)//栈1压入元素
    {
        S->top1++;
        S->data[S->top1]=e;
    }
    if(stackNumber==2)//栈2压入元素
    {
        S->data[--S->top2]=e;
    }
    return true;

}

• 链式存储结构
  头插法

/*
入栈操作：bool Push(SqStack *S,SElemType e)
功能：将e数据，压入S栈中
头插法：保证访问栈顶元素的时间复杂度为O(1)
*/
bool Push(LinkStack *S,SElemType e)
{
    //插入数据，申请新的空间
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top;
    S->top=s;
    S->count++;

    return true;
}

2.2 出栈pop

• 顺序存储结构

/*
出栈操作
*/
bool Pop(SqStack *S,SElemType *e)
{
    //判断栈是否为空
    if(S->top==-1)//切记栈为空的判断条件是-1，不是零。
    {
        return false;
    }

    *e=S->data[S->top];
    S->top--;

    return true;
}

• 共享栈

/*
出栈操作
*/
bool Pop(SqStack *S,SElemType *e,int stackNumber)
{
    if(stackNumber==1)//栈1弹出数据
    {
        if(S->top1==-1)//栈1空的条件
        {
            return false;
        }
        *e=S->data[S->top1];
        S->top1--;
    }
    if(stackNumber==2)//栈2弹出数据
    {   
        if(S->top2==MAXSIZE)//栈2空的条件
        {
            return false;
        }
        *e=S->data[S->top2++];
    }
    return true;
}

• 链式存储结构

/*
出栈操作
*/
bool Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(S->count==-1)//栈空
        return false;

    *e=S->top->data;
    p=S->top;
    S->top=p->next;
    free(p);
    S->count--;

    return true;
}

三、队列

队列用数组构建容易尝试越界，因此采用循环队列的方法。同时队列还可以采用链式存储的方法。

3.1 循环队列

#define  MAXSIZE 13

//循环队列的顺序存储结构
typedef int QElemType;

struct  SqQueue
{
    QElemType data[MAXSIZE];
    int front;//头指针
    int rear;//尾指针(空的尾部)
};

3.2 链式存储结构

//#define MAXSIZE 10
//链式队列->链式队列的长度理论上无限制
typedef int QElemType;


//链式队列的节点
typedef struct QNode
{
    QElemType data;
    QNode *next;//用于栈顶的指针    
}QNode,*QueuePtr;


//链式栈的结构
struct LinkQueue
{
    QueuePtr front,rear;//指向对头和对尾的指针
};

四、链式存储结构

4.1 入队

• 循环队列
  使用两个指针front和rear分别纪录队首和队尾的位置，
  入队的时候改变队尾指针 (Q->rear+1)%MAXSIZE;，
  出队时候改变队首指针 (Q->front+1)%MAXSIZE;
  队伍的长度为： (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
  当队首和队尾相等时，队列为空 (Q->rear+1)%MAXSIZE==Q->front
  当队首和队尾相差1时，队列为满 Q->rear==Q->front

//循环队列的初始化
bool InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
    return true;
}

//求队列当前的长度
int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

//入队操作
bool EnQueue(SqQueue *Q,QElemType e)
{
    //判断队是否满了
    if((Q->rear+1)%MAXSIZE==Q->front)
        return false;
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;

    return true;
}

• 链式存储结构

/*
入队操作：bool Push(SqStack *S,SElemType e)
功能：将e数据，压入S栈中
*/
bool EnQueue(LinkQueue *Q,QElemType e)
{
    //插入数据，申请新的空间
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if(!s)//分配内存失败
        return false;
    //尾部插入节点
    s->data=e;
    s->next=NULL;
    
    Q->rear->next=s;
    Q->rear=s;//当前节点设置为尾部节点

    return true;
}

4.2 出队

• 循环队列

//出队操作
bool DeQueue(SqQueue *Q,QElemType *e)
{
    //判断队是否空了
    if(Q->rear==Q->front)
    {
        cout<<"空"<<endl;
        return false;
    }
    *e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;

    return true;
}

• 链式存储结构

/*
出队操作
*/
bool DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    //判断队列为空
    if(Q->front==Q->rear)
        return false;
    p=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;

    if(p==Q->rear)//如果删除后队头是队尾，则将删除后rear指向头结点
        Q->rear=Q->front;

    free(p);
    return true;

}

五、Leetcode刷题

5.1 常用的stack queue priority_queue

备注：堆的操作与栈的操作完全一致

5.2 队列实现栈

Leetcode-225 用队列实现栈
思路：先将该数据放入临时队列中，在将原始队列中的数据也放入队列中，在将临时队列中的数据弹入到原始队列中

class MyStack {
public:
    /** Initialize your data structure here. */
    queue<int> res_queue;//可以定义为私有的成员变量
    MyStack() {

    }
    
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> temp_queue;
        temp_queue.push(x);

        while(!res_queue.empty())
        {
            temp_queue.push(res_queue.front());
            res_queue.pop();
        }

        while(!temp_queue.empty())
        {
            res_queue.push(temp_queue.front());
            temp_queue.pop();
        }

    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int num=res_queue.front();
        res_queue.pop();
        return num;
    }
    
    /** Get the top element. */
    int top() {
        return res_queue.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return res_queue.empty();
    }
};

5.3 栈实现队列

Leetcode-232 用栈实现队列
思路：先将原始栈中数据弹入到临时栈中，再将该输入压入原始栈中，在将临时栈中的数据弹入到原始栈中。

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> res_stack;
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stack<int> temp_stack;

        while(!res_stack.empty())
        {
            temp_stack.push(res_stack.top());
            res_stack.pop();
        }
        res_stack.push(x);
        while(!temp_stack.empty())
        {
            res_stack.push(temp_stack.top());
            temp_stack.pop();
        }


    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x=res_stack.top();
        res_stack.pop();
        return x;
    }
    
    /** Get the front element. */
    int peek() {
        return res_stack.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return res_stack.empty();
    }
};

5.4 最小栈

Leetcode-155 最小栈
思路：使用一个栈存放当前最小的元素

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    stack<int> minStack;
    stack<int> resStack;
    void push(int val) {
        resStack.push(val);
        if(minStack.empty())
        {
            minStack.push(val);
        }
        else
        {
            if(val<minStack.top())
            {
                minStack.push(val);
            }
            else
            {
                minStack.push(minStack.top());
            }
        }
    }
    
    void pop() {
        resStack.pop();
        minStack.pop();
    }
    
    int top() {
        return resStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
};

5.5 栈的压入、弹出序列

Leetcode-31 栈的压入、弹出序列
思路：用栈模拟新的过程，并于popped比较，相同则弹出，知道栈为空停止

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()==0) return true;

        int i=0;
        int j=0;

        stack<int> resultStack;//模拟入栈过程
        while(i<pushed.size())
        {
            resultStack.push(pushed[i]);
            while(!resultStack.empty() && resultStack.top()==popped[j])//每来一个相同数据，弹栈
            {
                resultStack.pop();
                j++;
            }
            i++;
        }

        return resultStack.empty();
    }
};

5.6 数组中的第K个最大元素

Leetcode-215 数组中的第K个最大元素
思路：维护一个size为k的小顶堆，弹出堆顶的元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int ,vector<int>,greater<int>> Q;//小顶堆
        for(int i=0;i<k;i++)
        {
            Q.push(nums[i]);
        }
        for(int i=k;i<nums.size();i++)
        {
            if(nums[i]>Q.top())
            {
                Q.pop();
                Q.push(nums[i]);
            }
        }

        return Q.top();
    }
};

5.7 数据流中的中位数

Leetcode-295 数据流中的中位数

class MedianFinder {
public:
    /** initialize your data structure here. */
    //思路：维护两个堆，最大堆存储数据的一半，最小堆存储数据的一半

    priority_queue<int ,vector<int>,greater<int>> min_queue;
    priority_queue<int ,vector<int>,less<int>> max_queue;


    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(max_queue.empty())
        {
            max_queue.push(num);
        }
        else if(max_queue.size()==min_queue.size())
        {
            if(num>max_queue.top())
            {
                min_queue.push(num);
            }
            else
            {
                max_queue.push(num);
            }
        }
        else if(max_queue.size()>min_queue.size())
        {
            if(num>max_queue.top())
            {
                min_queue.push(num);
            }
            else
            {
                min_queue.push(max_queue.top());
                max_queue.pop();
                max_queue.push(num);
            }
        }
        else
        {
            if(num<min_queue.top())
            {
                max_queue.push(num);
            }
            else
            {
                max_queue.push(min_queue.top());
                min_queue.pop();
                min_queue.push(num);
            }
        }
            
    }
    
    double findMedian() {
        if(min_queue.size()==max_queue.size())
            return (min_queue.top()+max_queue.top())/2.0;
        else if(min_queue.size()>max_queue.size())
            return min_queue.top();
        else
            return max_queue.top();
    }
};