栈原理

Word count: 850Reading time: 4 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++解法

const int maxsize=1000;//数据类型别忘了
//定义栈
string stack[maxsize];//栈  C++的string的s为小写
int top=0;//栈顶
//int top=-1;可以不用空stack[0]
bool in(string name){//入栈
    if(top>=maxsize){//栈满
        return 0;
    }
    else{
        stack[++top]=name;//要++top
        //当top=0时，会空stack[0]
        //可以将top=-1来解决
        //top++;
        return 1;
    }
}

bool inEmpty(){//判断是否栈空//其实可有可无，但没有每次要用的时候就要判断
    if(top==0){
        return 1;
    }
    else{
        return 0;
    }
}

bool out(){//出栈
    if(inEmpty()){
        return 0;
    }
    else{
        top--;//出栈，栈顶-1
        return 1;
    }
}

string gettop(){//获得栈顶元素
    if(inEmpty()){
        return "";
    }
    else{
        return stack[top];
    }
}

int main(){
    int N;
    cin>>N;

    while(N--){
        string op,name;
        cin>>op>>name;
        if(op=="in"){//进栈
            in(name);
        }
        else{
            while(gettop()!=name){//把要找的元素的后面的元素全不出栈
                out();
            }
            out();//把要找的元素出栈
        }
    }

    if(inEmpty()){
        cout<<"Empty"<<endl;//栈空
    }
    else{
        cout<<gettop()<<endl;//输出栈顶元素
    }
    return 0;
}

重点是定义栈，进栈，出栈，获得栈顶元素

java解法



import java.util.Scanner;

public class Main {

 final static  int maxsize=100005;

  static String[] Mystack =new String[maxsize]; //栈
  static int Top=0;         //栈顶指针

  static boolean in(String  name)
  {
      if(Top>=maxsize) return false;
      else {
          Mystack[++Top]=name;
          return true;
      }

  }
  static boolean isEmpty(){

      if(Top!=0) return false;
      else return true;

  }

  static boolean out()
  {
      if(isEmpty()) return false;
      else{
          Top--;
          return true;
      }
  }
  static String getTop()
  {
      if(isEmpty()) return "";
      else return Mystack[Top];
  }

  public static void main(String[] args)

  {
      int N;
      Scanner in=new Scanner(System.in);
      N=in.nextInt();
      for(int i=0;i<N;i++)
      {
          String op,name;
         op=in.next();
         name=in.next();
         // System.out.println(op+"  "+name);
          if(op.contains("in") )in(name);
          else {
              while(!getTop().equals(name)){
                 // System.out.println(getTop());
                  out();
              }
              out();
          }
      }
      if(isEmpty()) System.out.println("Empty");
      else System.out.println(getTop());
  }
}

Python解法


MyStack=[]
Top=-1


def inStack(name):

  global Top,MyStack
  MyStack.append(name) #使用python不需要考虑是否够用
  Top+=1


def isEmpty():

  global MyStack
  if(len(MyStack)==0):
      return True
  else:
      return False

def getTop():
  global Top,MyStack
  if(isEmpty()):
      return ""
  else:
      return MyStack[Top]


def outStack():
  global Top,MyStack
  if(isEmpty()):
      return False
  else :
      del MyStack[Top]
      Top-=1
      return  True


if __name__=='__main__':

  N=0
  N=int (input())

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

      if(op[0]=='in'):
          inStack(op[1])

      else :
          while(getTop()!=op[1]):
              outStack()
          outStack()

  if(isEmpty()) : 
      print("Empty")

  else:
      print(getTop())