数据结构--栈的实现（顺序栈和链栈）

谁践踏了优雅 2021-08-14 00:41 577阅读 0赞

栈

栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。

在这里插入图片描述

栈的抽象数据类型

  1. package pers.zhang.stack;
  3. /** * @author zhang * @date 2020/1/16 - 14:05 * * 栈接口，描述栈的抽象数据类型，泛型参数T表示数据元素的数据类型 */
  4. public interface SStack<T> { 
  5.     //判断栈是否为空
  6.     boolean isEmpty();
  8.     //元素x入栈
  9.     void push(T x);
  11.     //出栈，返回栈顶元素
  12.     T pop();
  14.     //取出栈顶元素，未出栈
  15.     T get();
  16. }

栈的实现

栈有两种基本的实现：

  • 顺序栈：使用数组实现
  • 链栈：使用栈节点实现

在这里插入图片描述

顺序栈

在这里插入图片描述

  1. package pers.zhang.stack;
  3. /** * @author zhang * @date 2020/1/16 - 14:12 * * 顺序栈，实现栈接口 */
  4. public class SeqStack<T> implements SStack<T> { 
  6.     //存储栈数据元素的Object数组
  7.     private Object element[];
  9.     //栈顶元素下表
  10.     private int top;
  12.     //构造容量为size的栈
  13.     public SeqStack(int size){ 
  14.         this.element = new Object[Math.abs(size)];
  15.         this.top = -1;
  16.     }
  18.     //默认构造，构造容量为64的空栈
  19.     public SeqStack(){ 
  20.         this(64);
  21.     }
  23.     //判断栈是否为空，若为空返回true
  24.     @Override
  25.     public boolean isEmpty() { 
  26.         return this.top == -1;
  27.     }
  29.     //元素x入栈，空对象不操作
  30.     @Override
  31.     public void push(T x) { 
  32.         if(x == null)
  33.             return;
  34.         if(this.top == element.length - 1){ //栈满，需要扩容
  35.             Object[] temp = this.element;
  36.             this.element = new Object[temp.length * 2];//重新申请一个2倍容量的数组
  37.             for(int i = 0; i < temp.length; i++)//复制元素
  38.                 this.element[i] = temp[i];
  39.         }
  40.         this.top++;//移动栈顶指针
  41.         this.element[this.top] = x;//入栈
  42.     }
  44.     //出栈，返回栈顶元素，若栈空返回null
  45.     @Override
  46.     public T pop() { 
  47.         return this.top == -1 ? null : (T) this.element[this.top--];
  48.     }
  50.     //取出栈顶元素，未出栈，若栈空返回null
  51.     @Override
  52.     public T get() { 
  53.         return this.top == -1 ? null : (T) this.element[this.top];
  54.     }
  56.     //返回栈所有元素的描述字符串，形式为“(,)”，算法同顺序表
  57.     @Override
  58.     public String toString(){             
  59.         String str = "(";
  60.         if (this.top != -1)
  61.             str += this.element[this.top].toString();
  62.         for (int i= this.top - 1; i >= 0; i--)
  63.             str += ", "+this.element[i].toString();
  64.         return str + ") ";
  65.     }
  66. }

链栈

在这里插入图片描述
在这里插入图片描述

节点类：

  1. public class Node<T> { 
  2.     //数据域，保存数据元素
  3.     public T data;
  5.     //地址域，引用后继节点
  6.     public Node<T> next;
  8.     public Node(){ 
  9.         this(null,null);
  10.     }
  12.     public Node(T data, Node<T> next){ 
  13.         this.data = data;
  14.         this.next = next;
  15.     }
  17.     public String toString(){ 
  18.         return this.data.toString();
  19.     }
  21.     public boolean equals(Object obj){ 
  22.         return obj == this || obj instanceof Node && this.data.equals(((Node<T>)obj).data);
  23.     }
  25. }

链栈的实现：

  1. package pers.zhang.stack;
  3. import pers.zhang.linearList.LinearList;
  4. import pers.zhang.linearList.Node;
  6. /** * @author zhang * @date 2020/1/16 - 14:28 * * 链栈，实现栈接口 */
  7. public class LinkedStack<T> implements SStack<T> { 
  9.     //栈顶节点，同单链表节点一致
  10.     private Node<T> top;
  12.     //构造空栈
  13.     public LinkedStack(){ 
  14.         this.top = null;
  15.     }
  17.     //判断栈是否为空，若空返回true
  18.     @Override
  19.     public boolean isEmpty() { 
  20.         return this.top == null;
  21.     }
  23.     //元素x入栈，空对象不操作
  24.     @Override
  25.     public void push(T x) { 
  26.         if(x == null)
  27.             return;
  28.         this.top = new Node<>(x, this.top);//头插入，x节点作为新的栈顶
  29.     }
  31.     //出栈，返回栈顶元素，栈空返回null
  32.     @Override
  33.     public T pop() { 
  34.         if(this.top == null)
  35.             return null;
  36.         T temp = this.top.data;//保存栈顶节点元素
  37.         this.top = this.top.next;//删除栈顶节点
  38.         return temp;
  39.     }
  41.     //取出栈顶元素，未出栈，空栈返回null
  42.     @Override
  43.     public T get() { 
  44.         return this.top == null ? null : this.top.data;
  45.     }
  47.     //返回栈所有元素的描述字符串，形式为“(,)”。算法同不带头结点的单链表
  48.     public String toString(){ 
  49.         String str = "(";
  50.         for (Node<T> p = this.top; p != null; p = p.next){ 
  51.             str += p.data.toString();
  52.             if (p.next != null)
  53.                 str += ", ";//不是最后一个结点时后加分隔符
  54.         }
  55.         return str + ")";//空表返回()
  56.     }
  57. }

测试

  1. package pers.zhang.stack;
  3. /** * @author zhang * @date 2020/1/16 - 14:36 */
  4. public class Stack_ex { 
  5.     public static void main(String args[])
  6.     { 
  7. /* SeqStack<String> stack = new SeqStack<String>(20); System.out.print("Push: "); char ch='a'; for(int i=0;i<5;i++) { String str = (char)(ch+i)+""; stack.push(str); System.out.print(str+" "); } */
  8.         LinkedStack<Integer> stack = new LinkedStack<Integer>();
  9.         System.out.print("Push: ");
  10.         for (int i=1; i<=5; i++)
  11.         { 
  12.             Integer intobj = new Integer(i);
  13.             stack.push(intobj);
  14.             System.out.print(intobj+" ");
  15.         }
  17.         System.out.println("\nStack: "+stack.toString());
  18.         System.out.print("Pop : ");
  19.         while(!stack.isEmpty())                  //全部出栈
  20.             System.out.print(stack.pop().toString()+" ");
  21.         System.out.println();
  22.     }
  23. }

输出如下：

  1. Push: a  b  c  d  e  
  2. Stack: (e, d, c, b, a) 
  3. Pop : e  d  c  b  a  
  5. Push: 1  2  3  4  5  
  6. Stack: (5, 4, 3, 2, 1) 
  7. Pop : 5  4  3  2  1

发表评论

表情：
评论列表 （有 0 条评论，577人围观）

还没有评论，来说两句吧...

相关阅读