5.stack栈基本应用

栈特点FILO先进后出，数据首先被压入push栈顶之上，成为新的栈顶，弹出pop从栈顶中移除一个元素，并将栈顶指针下移一位。

使用数组模拟栈

class SimpleStack {
    final int maxSize;

    int[] data;

    int top;

    public SimpleStack(int maxSize) {
        this.maxSize = maxSize;
        top = -1;
        data = new int[maxSize];
    }
	
    // 栈顶指针是否已经等于了最大容量-1
    public boolean isFull() {
        return this.top == maxSize - 1;
    }

    // 栈顶指针为-1
    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int i) {
        if (isFull()) {
            throw new RuntimeException("stack is full!");
        }
        // 数组元素赋值并上移top栈顶
        data[++top] = i;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("stack is empty!");
        }
		// 先弹出元素再下移栈顶指针
        return data[top--];
    }

    public void print() {
        if (isEmpty()) {
            System.out.println("stack is empty!");
        }
        // 从栈顶开始打印
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n ", i, data[i]);
        }
    }

    // 只查看不弹出(不一定top栈顶指针)
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("stack is empty can't peek");
        }
        return data[top];
    }
}

使用队列实现栈的功能

node节点数据结构，这里使用了泛型方便调用者使用。

class StackNode<T> {
    public T data;

    public StackNode<T> next;

    @Override
    public String toString() {
        return "StackNode{" +
                "data=" + data +
                '}';
    }
}

stack实现

class ListStack<T> {

    private final int maxSize;

    private StackNode<T> first;

    ListStack(int maxSize) {
        this.maxSize = maxSize;
    }

    public T peek() {
        if (first == null || first.next == null) {
            return first.data;
        }
        StackNode<T> temp = first;

        while (temp.next != null) {
            temp = temp.next;
        }
        return temp.data;
    }

    public void push(T data) {
        StackNode<T> node = new StackNode<>();
        node.data = data;
        if (first == null) {
            first = node;
        } else {
            if (isFull()) {
                throw new RuntimeException("stack is full!");
            }
            StackNode<T> temp = first;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    public void print() {
        if (first == null) {
            throw new RuntimeException("stack is empty!");
        }
        ListStack<T> newStack = reverse();
        StackNode<T> temp = newStack.first;
        while (true) {
            System.out.println(temp.data);
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
    }

    public ListStack<T> reverse() {
        ListStack<T> reverseStack = new ListStack<>(maxSize);
        if (first == null) {
            return reverseStack;
        }
        if (first.next == null) {
            reverseStack.first = first;
        }

        int size = size();
        for (int i = size - 1; i >= 0; i--) {
            StackNode<T> temp = first;
            int move = 0;
            while (move < i) {
                temp = temp.next;
                move++;
            }
            reverseStack.push(temp.data);
        }

        return reverseStack;
    }

    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("stack is empty!");
        }
        if (first.next == null) {
            T result = first.data;
            first = null;
            return result;
        }

        StackNode<T> temp = first;
        while (true) {
            if (temp.next.next == null) {
                break;
            }
            temp = temp.next;
        }
        StackNode<T> result = temp.next;
        temp.next = null;
        return result.data;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public boolean isFull() {
        return maxSize == size();
    }

    public int size() {
        int size = 0;

        if (first == null) {
            return size;
        } else {
            StackNode<T> temp = first;
            while (true) {
                size++;
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
        }
        return size;
    }
}

分步分析

• 添加 跟单向链表没区别 直接找到最后一个节点 next 指向新节点即可

  public void push(T data) {
          StackNode<T> node = new StackNode<>();
          node.data = data;
          if (first == null) {
              first = node;
          } else {
              if (isFull()) {
                  throw new RuntimeException("stack is full!");
              }
              StackNode<T> temp = first;
              while (temp.next != null) {
                  temp = temp.next;
              }
              temp.next = node;
          }
      }
  

• 弹出

  1. 首先需要找到最后一个元素的前一个元素 用于断开 next指针

  2. 临时变量保存一下temp.next 最后一个元素

  3. 将倒数第二个指针的next指向null 断开链接

      public T pop() {
          if (isEmpty()) {
              throw new RuntimeException("stack is empty!");
          }
          if (first.next == null) {
              T result = first.data;
              first = null;
              return result;
          }
  
          StackNode<T> temp = first;
          while (true) {
              if (temp.next.next == null) {
                  break;
              }
              temp = temp.next;
          }
          StackNode<T> result = temp.next;
          temp.next = null;
          return result.data;
      }
  

• 反转 我这里使用了一个新的stack来保存数据返回，不破坏源数据

  循环size()次保证每个元素都被添加进去，每次移动size-1个元素

  public ListStack<T> reverse() {
          ListStack<T> reverseStack = new ListStack<>(maxSize);
          if (first == null) {
              return reverseStack;
          }
          if (first.next == null) {
              reverseStack.first = first;
          }
  
          int size = size();
          for (int i = size - 1; i >= 0; i--) {
              StackNode<T> temp = first;
              int move = 0;
              while (move < i) {
                  temp = temp.next;
                  move++;
              }
              reverseStack.push(temp.data);
          }
  
          return reverseStack;
      }