数据结构:栈与队列

简介: 数据结构:栈与队列

一、模拟栈:

1.算法模板:

// tt表示栈顶
int stk[N], tt = 0;
 
// 向栈顶插入一个数
stk[ ++ tt] = x;
 
// 从栈顶弹出一个数
tt -- ;
 
// 栈顶的值
stk[tt];
 
// 判断栈是否为空
if (tt > 0)
{
 
}

2.例题:

实现一个栈,栈初始为空,支持四种操作:

  1. push x – 向栈顶插入一个数 x;
  2. pop – 从栈顶弹出一个数;
  3. empty – 判断栈是否为空;
  4. query – 查询栈顶元素。

现在要对栈进行 M个操作,其中的每个操作 3和操作 4都要输出相应的结果。

输入格式

第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令为 push xpopemptyquery 中的一种。

输出格式

对于每个 emptyquery 操作都要输出一个查询结果,每个结果占一行。

其中,empty 操作的查询结果为 YESNOquery 操作的查询结果为一个整数,表示栈顶元素的值。

数据范围

1≤M≤100000

1≤x≤10^9

所有操作保证合法。

输入样例:

10push5
query
push6pop
query
pop
empty
push4
query
empty

输出样例:

5
5
YES
4
NO

思路:

数组模拟栈:

用top表示栈顶所在的索引。初始时,top = -1。表示没有元素。

向栈顶插入一个数 x:push x :栈顶所在索引往后移动一格,然后放入x。st[++top] = x。

从栈顶弹出一个数:pop : top 往前移动一格。top–。

判断栈是否为空:empty :top 大于等于 0 栈非空小于 0 栈空。top == -1 ? “YES” : “NO”

查询栈顶元素:query : 返回栈顶元素。st[top]

#include<iostream>
 
using namespace std;
 
const int N=100010;
int tt=0;
int st[N];
 
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string op;
        int x;
        cin>>op;
        if(op=="push")
        {
            cin>>x;
            st[ ++ tt] = x;
        }
        else if(op=="pop")
        {
            tt--;
        }
        else if(op=="empty")
        {
            if(tt>0)
                cout<<"NO"<<endl;
            else 
                cout<<"YES"<<endl;
        }
        else
        {
            cout<<st[tt]<<endl;
        }
    }
    return 0;
}

二、模拟队列

1.算法模板:

A.普通队列:

// hh 表示队头,tt表示队尾
int q[N], hh = 0, tt = -1;
 
// 向队尾插入一个数
q[ ++ tt] = x;
 
// 从队头弹出一个数
hh ++ ;
 
// 队头的值
q[hh];
 
// 判断队列是否为空
if (hh <= tt)
{
 
}

B.循环队列:

// hh 表示队头,tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
 
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
 
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
 
// 队头的值
q[hh];
 
// 判断队列是否为空
if (hh != tt)
{
 
}

2.思路:

就是一个特殊的数组。这个数组,最前面叫队头,最后面叫队尾。只允许在最后面添加元素,只允许在最前面删除元素。

用一个数组 q 保存数据。

hh 代表队头q[hh] 就是队头元素, q[hh + 1] 就是第二个元素。

tt 代表队尾q[tt] 就是队尾元素, q[tt + 1] 就是下一次入队,元素应该放的位置。

[hh, tt] 左闭右闭,代表队列中元素所在的区间

3.例题:

实现一个队列,队列初始为空,支持四种操作:

  1. push x – 向队尾插入一个数 x;
  2. pop – 从队头弹出一个数;
  3. empty – 判断队列是否为空;
  4. query – 查询队头元素。

现在要对队列进行 M个操作,其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令为 push xpopemptyquery 中的一种。

输出格式

对于每个 emptyquery 操作都要输出一个查询结果,每个结果占一行。

其中,empty 操作的查询结果为 YESNOquery 操作的查询结果为一个整数,表示队头元素的值。

数据范围

1≤M≤100000

1≤x≤10^9

所有操作保证合法。

输入样例:

10
push6
empty
query
pop
empty
push 3
push 4
pop
query
push6

输出样例:

NO
6
YES
4

思路:

出队pop:因为 hh 代表队头,[hh, tt] 代表元素所在区间。所以出队可以用 hh++实现,hh++后,区间变为[hh + 1, tt]。

入队push:因为 tt 代表队尾,[hh, tt] 代表元素所在区间。所以入出队可以用 tt++实现,tt++后,区间变为[hh, tt + 1], 然后在q[tt+1]位置放入入队元素

是否为空empty:[hh, tt] 代表元素所在区间,当区间非空的时候,对列非空。也就是tt >= hh的时候,对列非空。

询问队头query:用 hh 代表队头,q[hh] 就是队头元素,返回 q[hh] 即可。

#include<iostream>
 
using namespace std;
 
const int N=100010;
//[hh, tt] 之间为队列(左闭右闭)
int q[N];
int hh=0;//队头位置
int tt=-1;
 
int main()
{
    //操作次数
    int n;
    cin>>n;
    while(n--)
    {
        //操作方式
        string op;
        cin>>op;
        int x;
        if(op=="push")
        {
            cin>>x;
            q[++tt]=x;//入队:队尾先往后移动一格,再放入要插入的数据
        }
        else if(op=="pop")
        {
            hh++;//出队:队头往后移动一格
        }
        else if(op=="empty")
        {
            if(hh>tt)cout<<"YES"<<endl;//[hh, tt]表示队列区间,当 hh>tt时,区间不为空
            else cout<<"NO"<<endl;
        }
        else 
        {
            //hh指向队头,q[hh]代表队头元素
            cout<<q[hh]<<endl;
        }
    }
    return 0;
}

三、单调栈

1.算法模板:

常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

2.思路:

用单调递增栈,当该元素可以入栈的时候,栈顶元素就是它左侧第一个比它小的元素。

以:3 4 2 7 5 为例,过程如下:

3.例题:

给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1

输入格式

第一行包含整数 N,表示数列长度。

第二行包含 N 个整数,表示整数数列。

输出格式

共一行,包含 N个整数,其中第 i 个数表示第 i个数的左边第一个比它小的数,如果不存在则输出 −1

数据范围

1≤N≤10^5

1≤数列中元素≤10^9

输入样例:

5
3 4 2 7 5

输出样例:

-1 3 -1 2 2
#include<iostream>
 
using namespace std;
 
const int N=100010;
 
int stk[N],tt;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        while(tt&&stk[tt]>=x)tt--;//如果栈顶元素大于当前待入栈元素,则出栈
        if(!tt)cout<<"-1 ";//如果栈空,则没有比该元素小的值
        else cout<<stk[tt]<<" ";//栈顶元素就是左侧第一个比它小的元素。
        stk[++tt]=x;
    }
    return 0;
}

四、单调队列:

1.算法模板:

常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

2.思路:

最小值和最大值分开来做,两个for循环完全类似,都做以下四步:

1.解决队首已经出窗口的问题;

2.解决队尾与当前元素a[i]不满足单调性的问题;

3.将当前元素下标加入队尾;

4.如果满足条件则输出结果;

需要注意的细节:

上面四个步骤中一定要先3后4,因为有可能输出的正是新加入的那个元素;

队列中存的是原数组的下标,取值时要再套一层,a[q[]];

算最大值前注意将hh和tt重置;

此题用cout会超时,只能用printf;

hh从0开始,数组下标也要从0开始。

3.例题:

给定一个大小为 n≤10^6 的数组。

有一个大小为 k滑动窗口,它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为 [1 3 -1 -3 5 3 6 7]k3

窗口位置

最小值

最大值

[1 3 -1] -3 5 3 6 7

-1

3

1 [3 -1 -3] 5 3 6 7

-3

3

1 3 [-1 -3 5] 3 6 7

-3

5

1 3 -1 [-3 5 3] 6 7

-3

5

1 3 -1 -3 [5 3 6] 7

3

6

1 3 -1 -3 5 [3 6 7]

3

7

你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 nk,分别代表数组长度和滑动窗口的长度。

第二行有 n个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

输入样例:

8 3
1 3 -1 -3 5 3 6 7

输出样例:

-1 -3 -3 -3 3 3
3 3 5 5 6 7

题目中提到了滑动窗口,我们先以示例为例看下什么是滑动窗口?在示例中,我们从数组中第一个元素开始遍历,由于窗口的大小是3,因此当遍历到第三个元素时,窗口就形成了。

之后,继续遍历元素时,为了保持窗口的大小为3,左侧元素就需要从窗口中剔除。这样使得窗口一直在向右移动,直到考察到最后一个元素结束,这就是所谓的滑动窗口。

# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;
 
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", &a[i]);
        if (i - k + 1 > q[hh]) ++ hh;                  // 若队首出窗口,hh加1
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调,tt减1
        q[++ tt] = i;                                  // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
    }
    cout << endl;
    hh = 0; tt = -1;                                   // 重置!
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 > q[hh]) ++ hh;
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }
    return 0;
}


目录
相关文章
|
7天前
|
存储 算法 调度
数据结构期末复习(3)栈和队列
数据结构期末复习(3)栈和队列
14 0
|
14天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
29 0
|
15天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
|
19天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
|
19天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
|
19天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
|
19天前
|
存储 算法 编译器
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
【数据结构】栈算法(算法原理+源码)
|
23天前
|
存储
【数据结构】什么是栈?
【数据结构】什么是栈?
24 0
【数据结构】什么是栈?
|
27天前
|
存储 设计模式 算法
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
52 0
|
28天前
|
存储
用队列和栈分别实现栈和队列
用队列和栈分别实现栈和队列
16 1

热门文章

最新文章