Java模拟栈和队列数据结构的基本示例讲解
程序员文章站
2024-03-11 14:16:37
栈和队列:
一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建;
访问受限,在特定时刻,只有一个数据可被读取或删除;
是一种抽象的结构,内部的实现...
栈和队列:
一般是作为程序员的工具,用于辅助构思算法,生命周期较短,运行时才被创建;
访问受限,在特定时刻,只有一个数据可被读取或删除;
是一种抽象的结构,内部的实现机制,对用户不可见,比如用数组、链表来实现栈。
模拟栈结构
同时,只允许一个数据被访问,后进先出
对于入栈和出栈的时间复杂度都为o(1),即不依赖栈内数据项的个数,操作比较快
例,使用数组作为栈的存储结构
public class stacks<t> { private int max; private t[] ary; private int top; //指针,指向栈顶元素的下标 public stacks(int size) { this.max = size; ary = (t[]) new object[max]; top = -1; } // 入栈 public void push(t data) { if (!isfull()) ary[++top] = data; } // 出栈 public t pop() { if (isempty()) { return null; } return ary[top--]; } // 查看栈顶 public t peek() { return ary[top]; } //栈是否为空 public boolean isempty() { return top == -1; } //栈是否满 public boolean isfull() { return top == max - 1; } //size public int size() { return top + 1; } public static void main(string[] args) { stacks<integer> stack = new stacks<integer>(3); for (int i = 0; i < 5; i++) { stack.push(i); system.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { integer peek = stack.peek(); system.out.println("peek:" + peek); system.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { integer pop = stack.pop(); system.out.println("pop:" + pop); system.out.println("size:" + stack.size()); } system.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); system.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { integer peek = stack.peek(); system.out.println("peek:" + peek); system.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { integer pop = stack.pop(); system.out.println("pop:" + pop); system.out.println("size:" + stack.size()); } } }
上面的例子,有一个maxsize的规定,因为数组是要规定大小的,若想无限制,可以使用其他结构来做存储,当然也可以new一个新的长度的数组。
例,使用linkedlist存储来实现栈
public class stackss<t> { private linkedlist<t> datas; public stackss() { datas = new linkedlist<t>(); } // 入栈 public void push(t data) { datas.addlast(data); } // 出栈 public t pop() { return datas.removelast(); } // 查看栈顶 public t peek() { return datas.getlast(); } //栈是否为空 public boolean isempty() { return datas.isempty(); } //size public int size() { return datas.size(); } public static void main(string[] args) { stacks<integer> stack = new stacks<integer>(3); for (int i = 0; i < 5; i++) { stack.push(i); system.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { integer peek = stack.peek(); system.out.println("peek:" + peek); system.out.println("size:" + stack.size()); } for (int i = 0; i < 5; i++) { integer pop = stack.pop(); system.out.println("pop:" + pop); system.out.println("size:" + stack.size()); } system.out.println("----"); for (int i = 5; i > 0; i--) { stack.push(i); system.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { integer peek = stack.peek(); system.out.println("peek:" + peek); system.out.println("size:" + stack.size()); } for (int i = 5; i > 0; i--) { integer pop = stack.pop(); system.out.println("pop:" + pop); system.out.println("size:" + stack.size()); } } }
例,单词逆序,使用statck结构
public class wordreverse { public static void main(string[] args) { reverse("株式会社"); } static void reverse(string word) { if (word == null) return; stackss<character> stack = new stackss<character>(); char[] chararray = word.tochararray(); int len = chararray.length; for (int i = 0; i <len; i++ ) { stack.push(chararray[i]); } stringbuilder sb = new stringbuilder(); while (!stack.isempty()) { sb.append(stack.pop()); } system.out.println("反转后:" + sb.tostring()); } }
打印:
反转后:社会式株
模拟队列(一般队列、双端队列、优先级队列)
队列:
先进先出,处理类似排队的问题,先排的,先处理,后排的等前面的处理完了,再处理
对于插入和移除操作的时间复杂度都为o(1),从后面插入,从前面移除
双端队列:
即在队列两端都可以insert和remove:insertleft、insertright,removeleft、removeright
含有栈和队列的功能,如去掉insertleft、removeleft,那就跟栈一样了;如去掉insertleft、removeright,那就跟队列一样了
一般使用频率较低,时间复杂度 o(1)
优先级队列:
内部维护一个按优先级排序的序列。插入时需要比较查找插入的位置,时间复杂度o(n), 删除o(1)
/* * 队列 先进先出,一个指针指示插入的位置,一个指针指示取出数据项的位置 */ public class queueq<t> { private int max; private t[] ary; private int front; //队头指针 指示取出数据项的位置 private int rear; //队尾指针 指示插入的位置 private int nitems; //实际数据项个数 public queueq(int size) { this.max = size; ary = (t[]) new object[max]; front = 0; rear = -1; nitems = 0; } //插入队尾 public void insert(t t) { if (rear == max - 1) {//已到实际队尾,从头开始 rear = -1; } ary[++rear] = t; nitems++; } //移除队头 public t remove() { t temp = ary[front++]; if (front == max) {//列队到尾了,从头开始 front = 0; } nitems--; return temp; } //查看队头 public t peek() { return ary[front]; } public boolean isempty() { return nitems == 0; } public boolean isfull() { return nitems == max; } public int size() { return nitems; } public static void main(string[] args) { queueq<integer> queue = new queueq<integer>(3); for (int i = 0; i < 5; i++) { queue.insert(i); system.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { integer peek = queue.peek(); system.out.println("peek:" + peek); system.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { integer remove = queue.remove(); system.out.println("remove:" + remove); system.out.println("size:" + queue.size()); } system.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); system.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { integer peek = queue.peek(); system.out.println("peek:" + peek); system.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { integer remove = queue.remove(); system.out.println("remove:" + remove); system.out.println("size:" + queue.size()); } } }
/* * 双端队列<span style="white-space:pre"> </span>两端插入、删除 */ public class queueqt<t> { private linkedlist<t> list; public queueqt() { list = new linkedlist<t>(); } // 插入队头 public void insertleft(t t) { list.addfirst(t); } // 插入队尾 public void insertright(t t) { list.addlast(t); } // 移除队头 public t removeleft() { return list.removefirst(); } // 移除队尾 public t removeright() { return list.removelast(); } // 查看队头 public t peekleft() { return list.getfirst(); } // 查看队尾 public t peekright() { return list.getlast(); } public boolean isempty() { return list.isempty(); } public int size() { return list.size(); } }
/* * 优先级队列 队列中按优先级排序,是一个有序的队列 */ public class queueqp { private int max; private int[] ary; private int nitems; //实际数据项个数 public queueqp(int size) { this.max = size; ary = new int[max]; nitems = 0; } //插入队尾 public void insert(int t) { int j; if (nitems == 0) { ary[nitems++] = t; } else { for (j = nitems - 1; j >= 0; j--) { if (t > ary[j]) { ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序,给定序列本来就是有序的,所以效率o(n) } else { break; } } ary[j + 1] = t; nitems++; } system.out.println(arrays.tostring(ary)); } //移除队头 public int remove() { return ary[--nitems]; //移除优先级小的 } //查看队尾 优先级最低的 public int peekmin() { return ary[nitems - 1]; } public boolean isempty() { return nitems == 0; } public boolean isfull() { return nitems == max; } public int size() { return nitems; } public static void main(string[] args) { queueqp queue = new queueqp(3); queue.insert(1); queue.insert(2); queue.insert(3); int remove = queue.remove(); system.out.println("remove:" + remove); } }