【18. 模拟栈和队列】

模拟栈

特点：栈是先进后出。

#include <iostream>
usign namespace std;
const int N = 100010;
int stk[N], tt;       //tt表示栈顶,初始值设为0

                      //插入
stk[++ tt] = x;

                      //弹出
tt --;

                      //判断栈是否为空
if(tt > 0) not empty
else empty
    
                      //栈顶
stk[tt];

题目

实现一个栈，栈初始为空，支持四种操作：

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

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

输入格式

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

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1 ≤ M ≤ 100000
1 ≤ x ≤ 109
所有操作保证合法。

输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

代码

#include <iostream>
#include <string>
using namespace std;

const int N = 100010;
int stk[N], tt;    // tt 表示栈顶,初始为0

//插入
void push(int x)
{
stk[ ++ tt] = x;
}


//弹出
void pop()
{
tt --;
}


//判断栈是否为空

void empty()
{
if (tt > 0)  cout << "NO" << endl;
else cout << "YES" << endl;
}


//栈顶
void query()
{
stk[tt]; 
cout << stk[tt] << endl;
}

int main()
{
int m;
cin >> m;
while (m --)
{
  int x;
      string op;
      cin >> op;
      if (op == "push")
      {
          cin >>x;
          push(x);

      }
      else if (op == "query")
      {
          query();

      }
      else if (op == "pop")
      {
          pop();
      }
      else
      {
          empty();
      }
}


}

模拟队列

特点：先进先出。

//在队尾插入元素，在对头取出元素
int q[N], hh, tt = -1;   //tt代表队头，hh代表队尾  对头初始值设置为-1，也可以向栈一样设置为0

//插入
q[ ++ tt] = x;

//弹出
hh ++;

//判断队列是否为空
if (hh <= tt) not empty
else empty
    
//取出队头元素
 q[hh]
//取出队尾元素
 q[tt]

题目

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

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

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

输入格式

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

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

1 ≤ M ≤ 100000
1 ≤ x ≤ 109
所有操作保证合法。

输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

代码

#include <iostream>
#include <string>
using namespace std;

const int N = 100010;
int q[N], hh, tt = -1;

//插入
void push(int x)
{
   q[ ++ tt]  =x;
}


//弹出
void pop()
{
   hh ++;
}


//判断是否为空
void empty()
{
   if (hh <= tt)  cout << "NO" << endl;
   else cout << "YES" << endl;
}



//取出队头元素
void query()
{
   q[hh];
   cout << q[hh] << endl;
   
}

int main()
{
  
   int m;
   cin >> m;
   while (m --)
   {
       string op;
       cin >> op;
       int x;
       if (op == "push")
       {
           cin >> x;
           push(x);
       }
       else if (op == "pop")
       {
           pop();
       }
       else if (op == "empty")
       {
           empty();
       }
       else
       {
           query();
       }
   }
   return 0;
}