如何用数组实现队列和栈

发布网友 发布时间：2022-04-20 04:51

我来回答

共1个回答

热心网友 时间：2022-04-22 20:01

1.实现栈结构：栈结构是先进后出的，只需要一个数组和一个记录位置的变量size，当进来一个元素，size就++，出去一个元素size就–。
2.实现队列结构：相对栈结构要难搞一些，队列的先进先出的，需要一个数组和三个变量，size记录已经进来了多少个元素，in记录刚进来的元素应该放在哪个位置，out表示用户要求弹出的元素所在的位置。size的作用不止于此，它还是in与out 的操作的关键信息，使得in与out解耦，避免的很多的麻烦，好像书本讲的是没有size这个变量的。当in或者out达到底部的时候就跳回0处。

/**
     * 固定数组实现一个队列
     * 队列先进先出，方法有push,pull,peek
     */
    public class CArrayToQueue {
       public static class MyQueue{
           private int out;//新进来的数 放这
           private int in;//用户要求弹出的数
           private int size;//已经进队列的个数
           
            private int arr[];
            public MyQueue(int iniSize){
                arr = new int[iniSize];
             size = 0;
              in = 0;
                out = 0;
           }
           public void push(int num){
                if(size==arr.length){
                 throw new RuntimeException(“the queue is full!”);
              }
               size++;//大小扩展一个
               arr[in] = num;//赋值
                in = in==arr.length-1 ? 0 : in+1;//如果已经到达数组末尾就重新等于0
            }
           public int pull(){
              if(size==0){
                 throw new RuntimeException(“the queue is empty!”);
             }
               size–;
             int t = out;//记录
            out = out==arr.length-1 ? 0 : out+1;//如果已经到达数组末尾就重新等于0
             return arr[t];
            }
           public int peek(){
              if(size==0){
                 throw new RuntimeException(“the queue is empty!”);
             }
               return arr[out];
          }
       }
       public static void main(String[] args) {
          int iniSize = 3;
         MyQueue myQueue = new MyQueue(iniSize);
           myQueue.push(;
          myQueue.push(;
          myQueue.push(;
          System.out.println(myQueue.pull());
         System.out.println(myQueue.pull());
         System.out.println(myQueue.pull());
         myQueue.push(;
          myQueue.push(;
          System.out.println(myQueue.pull());
         System.out.println(myQueue.peek());
     }
    }

•    1

 /**
     * 固定数组实现栈结构
     * 实现方法push,pop,peek
     * 当越界的时候抛出一个运行时异常
     * 简单面试题
     */
    public class CArrayToStack {
       public static class MyStack{
           private int size;//指针位置，也表示栈已经压了多少
            private int[]arr;
           MyStack(int iniSize){//构造方法初始化数组
                arr = new int[iniSize];
             size = 0;
          }
           public void push(int num){
                if(size == arr.length){
                   throw new RuntimeException("栈下标越界！");
              }
               arr[size++] = num;
          }
           public int pop(){
               if(size == 0){
                   throw new RuntimeException("栈中已经没有元素可以弹出！");
               }
               return arr[--size];
           }
           public int peek(){
              if(size == 0){
                   throw new RuntimeException("栈中已经没有元素可以弹出！");
               }
               return arr[size];
         }
       }
       public static void main(String[] args) {
          int len = 
            MyStack myStack = new MyStack(len);
           for (int i = 0; i < len; i++) {
             myStack.push(i);
            }
           for (int i = 0; i < len; i++) {
             System.out.println(myStack.pop());
          }
       }
    }