首页 > 代码库 > 数据结构-栈与队列
数据结构-栈与队列
- 相比于数组这种存储数据的数据，栈(Stock)和队列(Queue)主要作用是在程序中作为构思算法的辅助工具，是一种程序员开发过程中的便利工具。Stock和Queue具有访问受限以及更加抽象的特征。
一、栈
栈只允许访问最后一个插入的元素，即栈是先进后出(FILO)的一种数据结构。栈主要提供的算法包括push，pop和peek。其中push是插入一个元素，pop是弹出最近添加的一个元素，peek是返回最近添加的一个元素。
栈的底层实现可以是数组，也可以是链表，这里采用数组实现一个栈，代码如下：
1 public class Stock1<T> { 2 private static final int EMPTY_TOP = -1; 3 private int maxSize; 4 private Object[] stockArray; 5 private int top; 6 7 public Stock1() { 8 this(16); 9 }10 11 public Stock1(int initialCapacity) {12 if (initialCapacity < 0) {13 throw new IllegalArgumentException("The initialCapacity value must > 0, this value is:" + initialCapacity);14 }15 16 this.maxSize = initialCapacity;17 this.top = EMPTY_TOP;18 this.stockArray = new Object[this.maxSize];19 }20 21 public void push(T value) {22 this.checkIndex(this.top + 1);23 this.stockArray[++this.top] = value;24 }25 26 @SuppressWarnings("unchecked")27 public T pop() {28 this.checkIndex(this.top);29 return ((T) this.stockArray[this.top--]);30 }31 32 @SuppressWarnings("unchecked")33 public T peek() {34 this.checkIndex(this.top);35 return (T) this.stockArray[this.top];36 }37 38 public boolean isEmpty() {39 return this.top == EMPTY_TOP;40 }41 42 public boolean isFull() {43 return this.top == this.maxSize - 1;44 }45 46 public int size() {47 return this.top + 1;48 }49 50 private void checkIndex(int index) {51 if (index < 0 || index >= maxSize) {52 throw new IllegalArgumentException("The index is error, index:=" + index + ", the max index is:" + (maxSize - 1));53 }54 }55 56 @Override57 public String toString() {58 StringBuffer sb = new StringBuffer(this.maxSize);59 for (int i = this.top; i >= 0; i--) {60 sb.append(this.stockArray[i]).append(",");61 }62 return "[" + sb.substring(0, Math.max(sb.length() - 1, 0)) + "]";63 }64 }
二、队列
队列和栈一样，也只允许访问一个元素，但是这个元素是最早插入的，即队列是一个先进先出(FIFO)的数据结构。队列主要提供的算法包括insert，remove和peek。其中insert是在队列的尾部插入一个元素；remove是在队列的头部删除一个元素，并返回；peek是返回队列头部的元素的值。
队列的底层实现和栈一样，可以是数组或者是链表，代码如下：
1 public class Queue1<T extends Comparable<T>> { 2 private static int EMPTY_INDEX = 0; 3 protected final int maxSize; 4 protected final Comparable<T>[] queueArray; 5 protected int head; 6 protected int tail; 7 protected int size; 8 9 @SuppressWarnings("unchecked")10 public Queue1(int initialCapacity) {11 if (initialCapacity < 0) {12 throw new IllegalArgumentException("The initialCapacity value must > 0, this value is:" + initialCapacity);13 }14 15 this.maxSize = initialCapacity;16 this.queueArray = (Comparable<T>[]) Array.newInstance(Comparable.class, this.maxSize);17 this.head = EMPTY_INDEX;18 this.tail = EMPTY_INDEX;19 this.size = 0;20 }21 22 public void push(T value) {23 if (isFull()) {24 throw new IllegalArgumentException("The queue is full, can‘t push value to this queue.");25 } else {26 this.size++;27 this.queueArray[(this.tail++) % this.maxSize] = value;28 }29 }30 31 @SuppressWarnings("unchecked")32 public T pop() {33 if (isEmpty()) {34 throw new IllegalArgumentException("The queue is empty, can‘t pop value.");35 } else {36 this.size--;37 return (T) this.queueArray[(this.head++) % this.maxSize];38 }39 }40 41 @SuppressWarnings("unchecked")42 public T peek() {43 if (isEmpty()) {44 throw new IllegalArgumentException("The queue is empty, can‘t peek value.");45 } else {46 return (T) this.queueArray[this.head % this.maxSize];47 }48 }49 50 public boolean isEmpty() {51 return this.size == 0;52 }53 54 public boolean isFull() {55 return this.size == this.maxSize;56 }57 58 public int size() {59 return this.size;60 }61 }
这段代码中我将insert方法换成了push方法，remove方法换成了pop方法。
三、优先级队列
优先级队列和普通队列类似，区别在于在remove元素的时候，返回的元素值是按照某种顺序来定义的。实现优先级队列有两种方式：
第一种，在插入元素的时候，按顺排列。即每次插入的时候，都会将要插入的元素插入到对应位置，并移动其他元素。此时插入的时间复杂度是O(n2)，但是这样删除的代码和普通队列一样。
第二中，在插入元素的时候，直接将元素填充到队列尾部，但是在删除的时候，search全部数据，选择出要删除的数据出来。此时插入时间复杂度O(1)，删除复杂度为O(n2)。
我们采用第一种方式来实现一个队列，针对插入数据慢的问题，我们可以采用堆来解决这个问题，以后再说。代码如下：
第一种代码是继承普通队列，只修改push方法:
1 public class PriorityQueue1<T extends Comparable<T>> extends Queue1<T> { 2 public PriorityQueue1(int initialCapacity) { 3 super(initialCapacity); 4 } 5 6 public void push(T value) { 7 if (isFull()) { 8 throw new IllegalArgumentException("This queue is full"); 9 } else {10 int index = super.head;11 for (int i = 0; i < super.size; i++) {12 int compareResult = super.queueArray[index++ % super.maxSize].compareTo(value);13 if (compareResult >= 0) {14 index--;15 break;16 }17 }18 19 for (int i = super.tail; i > index; i--) {20 super.queueArray[i % super.maxSize] = super.queueArray[(i - 1) % super.maxSize];21 }22 23 super.queueArray[index] = value;24 super.tail++;25 super.size++;26 }27 }28 }
第二种是不继承普通队列，自己实现：
1 public class PriorityQueue2<T extends Comparable<T>> { 2 protected final int maxSize; 3 protected int nItems; 4 protected Comparable<T>[] basicArray; 5 6 @SuppressWarnings("unchecked") 7 public PriorityQueue2(int initialCapacity) { 8 if (initialCapacity < 0) { 9 throw new IllegalArgumentException("The initialCapacity value must > 0, this value is:" + initialCapacity);10 }11 12 this.maxSize = initialCapacity;13 this.basicArray = (Comparable<T>[]) Array.newInstance(Comparable.class, this.maxSize);14 this.nItems = 0;15 }16 17 public boolean isEmpty() {18 return this.nItems == 0;19 }20 21 public boolean isFull() {22 return this.nItems == this.maxSize;23 }24 25 public int size() {26 return this.nItems;27 }28 29 public void push(T value) {30 if (this.isFull()) {31 throw new IllegalArgumentException("This queue is full, can‘t push value.");32 } else {33 int index = 0;34 for (; index < this.nItems; index++) {35 if (this.basicArray[index].compareTo(value) <= 0) {36 break;37 }38 }39 40 for (int j = this.nItems; j > index; j--) {41 this.basicArray[j] = this.basicArray[j - 1];42 }43 44 this.basicArray[index] = value;45 this.nItems++;46 }47 }48 49 @SuppressWarnings("unchecked")50 public T pop() {51 if (this.isEmpty()) {52 throw new IllegalArgumentException("This queue is empty, can‘t pop value.");53 } else {54 return (T) this.basicArray[--nItems];55 }56 }57 58 @SuppressWarnings("unchecked")59 public T peek() {60 if (this.isEmpty()) {61 throw new IllegalArgumentException("This queue is empty, can‘t peek value.");62 } else {63 return (T) this.basicArray[this.nItems - 1];64 }65 }66 }
四、其他代码
1.解析表达式，将中缀表达式转换成后缀表达式
1 public class InToPost { 2 private Stock1<Character> stock; 3 private Queue1<String> queue; 4 private String input; 5 private StringBuffer sb; 6 7 public InToPost(String input) { 8 if (input != null && input.length() != 0) { 9 this.input = input.trim(); 10 } else { 11 this.input = ""; 12 } 13 14 this.stock = new Stock1<>(this.input.length()); 15 this.sb = new StringBuffer(this.input.length()); 16 this.queue = new Queue1<>(this.input.length()); 17 } 18 19 public String getInput() { 20 return input; 21 } 22 23 public String getOutput() { 24 return this.sb.toString(); 25 } 26 27 public String doTranshi() { 28 StringBuffer tmp = new StringBuffer(); 29 30 for (int j = 0; j < this.input.length(); j++) { 31 char ch = this.input.charAt(j); 32 switch (ch) { 33 case ‘+‘: 34 case ‘-‘: 35 pushValueToQueue(tmp.toString()); 36 sb.append(tmp.toString()); 37 tmp = new StringBuffer(); 38 gotPot(ch, 1); 39 break; 40 41 case ‘*‘: 42 case ‘/‘: 43 pushValueToQueue(tmp.toString()); 44 sb.append(tmp.toString()); 45 tmp = new StringBuffer(); 46 gotPot(ch, 2); 47 break; 48 49 case ‘(‘: 50 this.stock.push(ch); 51 break; 52 53 case ‘)‘: 54 pushValueToQueue(tmp.toString()); 55 sb.append(tmp.toString()); 56 tmp = new StringBuffer(); 57 while (!this.stock.isEmpty()) { 58 char chx = this.stock.pop(); 59 if (chx == ‘(‘) { 60 break; 61 } else { 62 sb.append(chx); 63 pushValueToQueue(String.valueOf(chx)); 64 } 65 } 66 break; 67 68 default: 69 tmp.append(ch); 70 break; 71 } 72 } 73 74 pushValueToQueue(tmp.toString()); 75 sb.append(tmp.toString()); 76 77 while (!this.stock.isEmpty()) { 78 char ch = this.stock.pop(); 79 this.sb.append(ch); 80 pushValueToQueue(String.valueOf(ch)); 81 } 82 83 return this.getOutput(); 84 } 85 86 private void gotPot(char ch, int prec) { 87 while (!this.stock.isEmpty()) { 88 char chx = this.stock.pop(); 89 if (chx == ‘(‘) { 90 this.stock.push(chx); 91 break; 92 } else { 93 int prec2 = 2; 94 if (chx == ‘+‘ || chx == ‘-‘) { 95 prec2 = 1; 96 } 97 if (prec2 >= prec) { 98 sb.append(chx); 99 pushValueToQueue(String.valueOf(chx));100 } else {101 this.stock.push(chx);102 break;103 }104 }105 }106 this.stock.push(ch);107 }108 109 private void pushValueToQueue(String value) {110 if (value =http://www.mamicode.com/= null || value.trim().length() == 0) {111 return;112 }113 this.queue.push(value.trim());114 }115 116 public Queue1<String> getQueue() {117 return this.queue;118 }119 }120 121 class InToPostUtil {122 public static String doTranshi(String line) {123 return new InToPost(line).doTranshi();124 }125 }126 127 class InToPostApp {128 public static void main(String[] args) {129 System.out.println(InToPostUtil.doTranshi(null));130 System.out.println(InToPostUtil.doTranshi(""));131 System.out.println(InToPostUtil.doTranshi(" "));132 System.out.println(InToPostUtil.doTranshi("a*b+c"));133 System.out.println(InToPostUtil.doTranshi("a*(b+c)"));134 System.out.println(InToPostUtil.doTranshi("a*(b+c*d)"));135 System.out.println(InToPostUtil.doTranshi("a*(b+c*d/(e-f*g))"));136 }137 }
2.计算后缀表达式的值
1 package com.augmentum.gby.ds; 2 3 public class ParsePost { 4 private String line; 5 private InToPost inToPost; 6 7 public ParsePost(String line) { 8 this.line = line; 9 this.inToPost = new InToPost(this.line);10 }11 12 public double doParse() {13 String reline = this.inToPost.doTranshi();14 if (reline == null || reline.length() == 0) {15 throw new IllegalArgumentException("The input line value is empty. can‘t calc those value.");16 } else {17 Stock1<Double> stock = new Stock1<>(reline.length());18 Queue1<String> queue = this.inToPost.getQueue();19 while (!queue.isEmpty()) {20 String value =http://www.mamicode.com/ queue.pop();21 if ("+".equals(value) || "-".equals(value) || "*".equals(value) || "/".equals(value)) {22 double num1 = stock.pop();23 double num2 = stock.pop();24 switch (value.charAt(0)) {25 case ‘+‘:26 stock.push(num1 + num2);27 break;28 case ‘-‘:29 stock.push(num2 - num1);30 break;31 case ‘*‘:32 stock.push(num2 * num1);33 break;34 case ‘/‘:35 stock.push(num2 / num1);36 break;37 }38 } else {39 stock.push(Double.valueOf(value));40 }41 }42 return stock.pop();43 }44 }45 }46 47 class ParsePostUtil {48 public static double doParse(String line) {49 return new ParsePost(line).doParse();50 }51 }52 53 class ParsePostApp {54 public static void main(String[] args) {55 System.out.println(InToPostUtil.doTranshi("2*((3+4)*5+5)"));56 System.out.println(InToPostUtil.doTranshi("2*3+4") + "; The result is:" + ParsePostUtil.doParse("2*3+4"));57 System.out.println(InToPostUtil.doTranshi("2*(3+4)") + "; The result is:" + ParsePostUtil.doParse("2*(3+4)"));58 System.out.println(InToPostUtil.doTranshi("2*(3+4*5)") + "; The result is:" + ParsePostUtil.doParse("2*(3+4*5)"));59 System.out.println(InToPostUtil.doTranshi("2*3+4*5") + "; The result is:" + ParsePostUtil.doParse("2*3+4*5"));60 System.out.println(InToPostUtil.doTranshi("2*((3+4)*5+5)") + "; The result is:" + ParsePostUtil.doParse("2*((3+4)*5+5)"));61 System.out.println(InToPostUtil.doTranshi("2*((3+4)*5+9)") + "; The result is:" + ParsePostUtil.doParse("2*((3+4)*5+9)"));62 System.out.println(InToPostUtil.doTranshi("20*3+4") + "; The result is:" + ParsePostUtil.doParse("20*3+4"));63 System.out.println(InToPostUtil.doTranshi("20.5*4+4") + "; The result is:" + ParsePostUtil.doParse("20.5*4+4"));64 }65 }
数据结构-栈与队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。