栈在语言中模板类

Word count: 1.4kReading time: 5 min

 2022/05/02 

栈在语言中模板类

栈的运用

栈在高级算法中是一种不可或缺的工具，单独使用可能不会太多次数。

小邋遢的衣橱

小邋遢 MS.Jinlin 是个爱打扮的公主，他有很多晚礼服如”LALA” “NIHAOMA”、”WOBUHAO”、”NIHAOBUHAO”等众多衣服，可是由于衣服太多他要把它们装进箱子，但是作为公主，肯定是会突发奇想觉得哪件衣服好看，就把他拿了出来，当然那件衣服上面的衣服也被拿出来了，而且会弄乱了，小邋遢在经过几次的叠衣服和取衣服后，他想知道箱子里最上面的衣服是哪一件，如果箱子为空的话，就告诉她 Empty ，如果有多件一样的衣服，肯定是取走最上面的那一件啦。

输入描述

第 11 行，输入N，代表共计进行了几次操作。

第 22 行至第 N+1 行，进行 in out 操作（in 为放入衣服，out 为取出衣服）

格式如下：

in name1
out name2

输出描述

输出 N 次操作结束后箱子最上面的衣服名字，若箱子为空，输出 Empty。

利用c++内置栈模板解题

C++内置栈模板

C++中栈的定义

LIFO stack 堆栈，它是一种容器适配器，专门设计用于在 LIFO 上下文（后进先出）中操作，其中元素仅从容器的一端插入和提取。

stack 被实现为容器适配器它们是使用特定容器类的封装对象作为其类底层容器的，提供一组特定的成员函数来访问其元素。元素推入 / 弹出从的 “后面” 特定容器，这被称为的顶部堆栈。

底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。

C++ 的 stack 模板定义了如下操作：
- top()：
  
  返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
- push(const T& obj)：
  
  可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
- push(T&& obj)：
  
  以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
- pop()：
  
  弹出栈顶元素。
- size()：
  
  返回栈中元素的个数。

C++代码

#include <iostream>
#include <stack>//记得头文件
using namespace std;
stack<string> mystack;//声明一个栈类
//stack<数据类型> 栈的名字

int main(){
    int N;
    cin>>N;
    while(N--){
        string op,name;
        cin>>op>>name;
        if(op=="in"){
            mystack.push(name);
        }
        else{
            while(mystack.top()!=name){
                mystack.pop();
            }
            mystack.pop();
        }   
    }
     if(mystack.empty()){
            cout<<"Empty"<<endl;
        }
        else{
            cout<<mystack.top()<<endl;
        }
    return 0;
}

利用java内置栈类解题

java内置栈类

java内栈的定义

栈是 Vector 的一个子类，它实现了一个标准的后进先出的栈，至于什么是 Vector，大家可以理解为能力超强的数组，在后面的课程中，我们会进行讲解。
堆栈定义了默认构造函数，用来创建一个空栈。

Java 的 stack 模板定义了如下操作流程
- push():
  
  执行 push 时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。
- peek():
  
  执行 peek 时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。
- pop():
  
  执行 pop 时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。
- empty():
  
  继承于 Vector，返回是否为空
- size():
  
  继承 Vector,返回元素的个数。

Java代码

import java.util.Scanner;//import
import java.util.Stack;//要加";"
//注意拼写
public class Main{
    static Stack Mystack=new Stack();

    public static void main(String[] args){
        int N;
        Scanner in=new Scanner(System.in);
        N=in.nextInt();//int的i为大写

       for(int i=0;i<N;i++){//java中不能while(N--)int类型不能转换成bool类型
       //可以
       //while(M>0){M--}

            String op,name;
            op=in.next();
            name=in.next();
            if(op.contains("in")){//也可以用op.equals("in")
            //contains和equals的区别是
            //contains是这字符串是否包含（"in"）
            //equals是这字符串是否和（"in"）相同

            Mystack.push(name);
            }
            else{
                while(!Mystack.peek().equals(name)){
                    Mystack.pop();
                }
                Mystack.pop();
            }
        }
        if(Mystack.empty()){
            System.out.println("Empty");
        }
        else{
            System.out.println(Mystack.peek());
        }
    }
}

Python的栈的实现

由于 Python 没有现成的栈的定义，要想使用，只能进行自己模拟，模拟方法可以使用上面使用的方法，也可以看一下下面讲的高级点的方法，声明并定义一个栈类的方法，推荐使用下面的方法，上面的代码还是主要讲理论使用。

Python代码



class MyStack:
    def __init__(self):
        self._data = [] # 使用list存储栈元素

    def is_empty(self):
        return self._data == []

    def push(self, elem):
        self._data.append(elem)

    def pop(self):
        if self._data == []:

            raise Warning ("此栈为空，错误操作");

        return self._data.pop()

    def top(self):
        if self._data == []:
            raise Warning("此栈为空，错误操作");

        return self._data[-1]



if __name__=='__main__':


    N=int (input())

    Stack =MyStack()

    while N>0:
        N-=1
        op=input().split()

        if(op[0]=='in'):
            Stack.push(op[1])

        else :
            while(Stack.top()!=op[1]):
                Stack.pop()
            Stack.pop()

    if(Stack.is_empty()) :
        print("Empty")

    else:
        print(Stack.top())