stack(顺序、链式及应用)

时间：2015-04-18 09:57:02 阅读：226 评论：0 收藏：0 [点我收藏+]

（java版）

1. 顺序栈的实现

顺序栈实现1

[java]

package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
* @ClassName: ArrayStack
* @Description: 顺序栈
* @date 2014年1月20日上午8:47:19
* @param <T>
*/
public class ArrayStack<T> implements Serializable {
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = 74027006708386243L;
private Object[] elementData;//定义一个数组用于保存顺序栈的元素
private int size = 0;//保存顺序栈中元素的当前个数
private int capacity;//保存数组的长度
public ArrayStack() {
elementData = new Object[10];//默认长度为10的栈
}
public ArrayStack(int initSize) {
elementData = new Object[initSize];//默认长度为10的栈
}
public ArrayStack(T element) {
this();
elementData[0] = element;
size++;
}
public ArrayStack(T element, int initSize) {
this.capacity = initSize;
elementData = new Object[capacity];
elementData[0] = element;
size++;
}
/**
* @Title: size
* @Description: 栈长度
* @return
*/
public int size() {
return size;
}
/**
* @Title: push
* @Description: 入栈
* @param element
*/
public void push(T element) {
ensureCapacity(size + 1);
elementData[size++] = element;
}
private void ensureCapacity(int minCapacity) {
//如果数组的原有长度小于目前所需的长度
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* @Title: pop
* @Description: 出栈
* @return
*/
public T pop() {
if (!isEmpty()) {
T oldValue = (T) elementData[size - 1];
//释放栈顶元素
elementData[--size] = null;
return oldValue;
} else {
return null;
}
}
/**
* @Title: peek
* @Description: 返回栈顶元素，但不删除栈顶元素
* @return
*/
public T peek() {
if (!isEmpty()) {
return (T) elementData[size - 1];
} else {
throw new IndexOutOfBoundsException("空栈异常");
}
}
/**
* @Title: empty
* @Description: 判断顺序栈是否为空栈
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* @Title: clear
* @Description: 清空顺序栈
*/
public void clear() {
//将底层数组所有元素赋为null
Arrays.fill(elementData, null);
size = 0;
}
public String toString() {
if (size == 0) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (int i = size - 1; i > -1; i--) {
sb.append(elementData[i].toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
}

顺序栈实现2

[java]

package lang;
import java.util.ArrayList;
import java.util.EmptyStackException;
public class ArrayStack2<E> extends ArrayList<E> {
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -4396620094929287983L;
public ArrayStack2() {
super();
}
public ArrayStack2(final int initialSize) {
super(initialSize);
}
public boolean empty() {
return isEmpty();
}
public E peek() throws EmptyStackException {
final int n = size();
if (n <= 0) {
throw new EmptyStackException();
} else {
return get(n - 1);
}
}
public E peek(final int n) throws EmptyStackException {
final int m = (size() - n) - 1;
if (m < 0) {
throw new EmptyStackException();
} else {
return get(m);
}
}
public E pop() throws EmptyStackException {
final int n = size();
if (n <= 0) {
throw new EmptyStackException();
} else {
return remove(n - 1);
}
}
public E push(final E item) {
add(item);
return item;
}
public int search(final Object object) {
int i = size() - 1; // Current index
int n = 1; // Current distance
while (i >= 0) {
final Object current = get(i);
if ((object == null && current == null)
|| (object != null && object.equals(current))) {
return n;
}
i--;
n++;
}
return -1;
}
}

2. 链式栈的实现：

[java]

package lang;
import java.io.Serializable;
/**
* @ClassName: LinkStack
* @Description: 链式栈
* @date 2014年1月20日下午3:46:40
* @param <T>
*/
public class LinkStack<T> implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -4378447264374701299L;
private class Node{
private T data; //保存节点的数据
private Node next; //指向下个节点的引用
public Node(){
}
public Node(T data, Node next){
this.data = data;
this.next = next;
}
}
private Node top; //保存该链栈的栈顶元素
private int size = 0; //保存该链栈中已包含的节点数,即栈的长度
public LinkStack(){
top = null;
}
public LinkStack(T element) {
top = new Node(element , null);
size++;
}
/**
* @Title: size
* @Description: 栈的长度
* @return
*/
public int size(){
return size;
}
/**
* @Title: push
* @Description: 入栈
* @param element
*/
public void push(T element){
top = new Node(element , top);
size++;
}
/**
* @Title: pop
* @Description: 出栈
* @return
*/
public T pop(){
Node oldTop = top;
top = top.next;
oldTop.next = null;
size--;
return oldTop.data;
}
/**
* @Title: peek
* @Description: 访问栈顶元素
* @return
*/
public T peek(){
return top.data;
}
/**
* @Title: empty
* @Description: 判断顺序栈是否为空栈
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* @Title: clear
* @Description: 清空顺序栈
*/
public void clear() {
top = null;//将栈所有元素赋为null
size = 0;
}
public String toString() {
//链栈为空链栈时
if (isEmpty()) {
return "[]";
} else {
StringBuilder sb = new StringBuilder("[");
for (Node current = top ; current != null ; current = current.next ) {
sb.append(current.data.toString() + ", ");
}
int len = sb.length();
return sb.delete(len - 2 , len).append("]").toString();
}
}
}

3. 栈的应用

3.1 将10进制正整数num转换为n进制

[java]

package stack.apply;
import org.junit.Test;
import lang.ArrayStack;
/**
* @ClassName: Conversion
* @Description: 将10进制正整数num转换为n进制
* @date 2014年1月21日上午9:47:22
*/
public class Conversion {
/**
* @Title: conversion
* @Description: 将10进制正整数num转换为n进制
* @param num: 10进制正整数
* @param n: n进制
* @return 转换后的值
*/
private String conversion(int num, int n) {
ArrayStack<Integer> myStack = new ArrayStack<Integer>();
Integer result = num;
while (true) {
// 将余数入栈
myStack.push(result % n);
result = result / n;
if (result == 0) {
break;
}
}
StringBuilder sb = new StringBuilder();
// 按出栈的顺序倒序排列即可
while ((result = myStack.pop()) != null) {
sb.append(result);
}
return sb.toString();
}
@Test
public void testConversion(){
String s = conversion(13,2);
System.out.println(s);
}
}

3.2 行编辑:

输入行中字符‘#‘表示退格, ‘@‘表示之前的输入全都无效.

[java]

package stack.apply;
import org.junit.Test;
import lang.ArrayStack;
/**
* @ClassName: LineEdit
* @Description: 行编辑: 输入行中字符‘#‘表示退格, ‘@‘表示之前的输入全都无效.
* @date 2014年1月21日上午10:17:06
*/
public class LineEdit {
/**
* @Title: lineEdit
* @Description: 行编辑
* @param input
* @return
*/
private String lineEdit(String input) {
ArrayStack<Character> myStack = new ArrayStack<Character>();
char[] arr = input.toCharArray();
for (char c : arr) {
if (c == ‘#‘) {
myStack.pop();
} else if (c == ‘@‘) {
myStack.clear();
} else {
myStack.push(c);
}
}
StringBuilder sb = new StringBuilder();
Character temp = null;
while ((temp = myStack.pop()) != null) {
sb.append(temp);
}
// 反转字符串
sb.reverse();
return sb.toString();
}
@Test
public void testLineEdit(){
String s = lineEdit("abcd#dsa@#usera#22#8");
System.out.println(s);
}
}

3.3 检验符号是否匹配.

‘[‘和‘]‘, ‘(‘和‘)‘成对出现时字符串合法.
例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的

[java]

package stack.apply;
import org.junit.Test;
import lang.ArrayStack;
/**
* @ClassName: Match
* @Description: 检验符号是否匹配. ‘[‘和‘]‘, ‘(‘和‘)‘成对出现时字符串合法.
* 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的
* @date 2014年1月21日上午10:14:47
*/
public class Match {
/**
* @Title: isMatch
* @Description: 检验符号是否匹配
* @param str 输入要匹配的字符串
* @return 是否匹配
*/
public boolean isMatch(String str) {
ArrayStack<Character> myStack = new ArrayStack<Character>();
char[] arr = str.toCharArray();
for (char c : arr) {
Character temp = myStack.pop();
// 栈为空时只将c入栈
if (temp == null) {
myStack.push(c);
}
// 配对时c不入栈
else if (temp == ‘[‘ && c == ‘]‘) {
}
// 配对时c不入栈
else if (temp == ‘(‘ && c == ‘)‘) {
}
// 不配对时c入栈
else {
myStack.push(temp);
myStack.push(c);
}
}
return myStack.isEmpty();
}
@Test
public void testMatch(){
boolean b = isMatch("[[([]([])()[])]]");
System.out.println(b);
}
}
(c版)
判断一行字符串输入"各种括号"是否是合法的-----------------------栈用数组实现

如：[()]是合法的(balance)

[(])是不合法的(imbalance)
[cpp] view plain copy
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
5. typedef struct Mystack *Stack;
7. struct Mystack {
8. int Capacity; /* 栈的容量 */
9. int Top_of_stack; /* 栈顶下标 */
10. char *Array; /* 存放栈中元素的数组 */
11. };
13. /* 栈的创建 */
14. Stack CreateStack(int Max)
15. {
16. Stack S;
17. S = malloc(sizeof(struct Mystack));
18. if (S == NULL)
19. printf("Create stack error!\n");
21. S->Array = malloc(sizeof(char) * Max);
22. if (S->Array == NULL)
23. printf("Create stack error!\n");
25. S->Capacity = Max;
26. S->Top_of_stack = 0;
27. return S;
28. }
30. /* 释放栈 */
31. void DisposeStack(Stack S)
32. {
33. if (S != NULL)
34. {
35. free(S->Array);
36. free(S);
37. }
38. }
40. /* 判断一个栈是否是空栈 */
41. int IsEmpty(Stack S)
42. {
43. return !S->Top_of_stack;
44. }
46. /* 判断一个栈是否满栈 */
47. int IsFull(Stack S)
48. {
49. if (S->Top_of_stack == S->Capacity - 1)
50. return 1;
51. else
52. return 0;
53. }
56. /* 数据入栈 */
57. int Push(int x, Stack S)
58. {
59. if (IsFull(S))
60. printf("The Stack is full!\n");
61. else
62. S->Array[S->Top_of_stack++] = x;
63. }
65. /* 数据出栈 */
66. int Pop(Stack S)
67. {
68. if (IsEmpty(S))
69. printf("The Stack is empty!\n");
70. else
71. S->Top_of_stack--;
72. }
74. /* 将栈顶返回 */
75. char Top(Stack S)
76. {
77. if (!IsEmpty(S))
78. return S->Array[S->Top_of_stack-1];
79. printf("The Stack is empty!\n");
80. return 0;
81. }
83. int main()
84. {
85. int i, len;
86. char str[100];
87. printf("Please input the symbol that you want to balance: \n");
88. scanf("%s", str);
89. len = strlen(str);
90. /* 根据序列的长度来创建栈 */
91. struct Mystack *my_stack = CreateStack(len+1);
92. for (i = 0; i < len; i++)
93. {
94. if (str[i] == ‘{‘ || str[i] == ‘[‘ || str[i] == ‘(‘ )
95. Push(str[i], my_stack);
96. if (str[i] == ‘}‘)
97. {
98. if (Top(my_stack) == ‘{‘)
99. Pop(my_stack);
100. else
101. break;
102. }
103. else if (str[i] == ‘]‘)
104. {
105. if (Top(my_stack) == ‘[‘)
106. Pop(my_stack);
107. else
108. break;
109. }
110. else if (str[i] == ‘)‘)
111. {
112. if (Top(my_stack) == ‘(‘)
113. Pop(my_stack);
114. else
115. break;
116. }
117. }
118. /* 如果最后占空则序列是合法的 */
119. if(IsEmpty(my_stack))
120. printf("The symbol that you input is balance!\n");
121. else
122. printf("The symbol that you input is imbalance!\n");
123. DisposeStack(my_stack);
124. return 0;
125. }
测试：
[cpp] view plain copy
1. shang@shang:~/C$ ./a.out
2. Please input the symbol that you want to balance:
3. {[]}
4. The symbol that you input is balance!
5. shang@shang:~/C$ ./a.out
6. Please input the symbol that you want to balance:
7. [(])
8. The symbol that you input is imbalance!
9. shang@shang:~/C$ ./a.out
10. Please input the symbol that you want to balance:
11. ([{}])
12. The symbol that you input is balance!
13. shang@shang:~/C$
22. 用栈计算逆波兰式
23. 1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  5. typedef struct Mystack *Stack;
  7. struct Mystack {
  8. int Capacity; /* 栈的容量 */
  9. int Top_of_stack; /* 栈顶下标 */
  10. int *Array; /* 存放栈中元素的数组 */
  11. };
  13. /* 栈的创建 */
  14. Stack CreateStack(int Max)
  15. {
  16. Stack S;
  17. S = malloc(sizeof(struct Mystack));
  18. if (S == NULL)
  19. printf("Create stack error!\n");
  21. S->Array = malloc(sizeof(char) * Max);
  22. if (S->Array == NULL)
  23. printf("Create stack error!\n");
  25. S->Capacity = Max;
  26. S->Top_of_stack = 0;
  27. return S;
  28. }
  30. /* 释放栈 */
  31. void DisposeStack(Stack S)
  32. {
  33. if (S != NULL)
  34. {
  35. free(S->Array);
  36. free(S);
  37. }
  38. }
  40. /* 判断一个栈是否是空栈 */
  41. int IsEmpty(Stack S)
  42. {
  43. return !S->Top_of_stack;
  44. }
  46. /* 判断一个栈是否满栈 */
  47. int IsFull(Stack S)
  48. {
  49. if (S->Top_of_stack == S->Capacity - 1)
  50. return 1;
  51. else
  52. return 0;
  53. }
  56. /* 数据入栈 */
  57. int Push(int x, Stack S)
  58. {
  59. if (IsFull(S))
  60. printf("The Stack is full!\n");
  61. else
  62. S->Array[S->Top_of_stack++] = x;
  63. }
  65. /* 数据出栈 */
  66. int Pop(Stack S)
  67. {
  68. if (IsEmpty(S))
  69. printf("The Stack is empty!\n");
  70. else
  71. S->Top_of_stack--;
  72. }
  74. /* 将栈顶返回 */
  75. int Top(Stack S)
  76. {
  77. if (!IsEmpty(S))
  78. return S->Array[S->Top_of_stack-1];
  79. printf("The Stack is empty!\n");
  80. return 0;
  81. }
  83. int main()
  84. {
  85. int i, len, result;
  86. char str[100];
  87. printf("Please input the postfix that you want to compute: \n");
  88. scanf("%s", str);
  89. len = strlen(str);
  90. /* 根据序列的长度来创建栈 */
  91. struct Mystack *my_stack = CreateStack(len+1);
  92. for (i = 0; i < len; i++)
  93. {
  94. if (str[i] >= ‘0‘ && str[i] <= ‘9‘)
  95. Push((int)str[i]-48, my_stack);
  96. else if (str[i] == ‘+‘)
  97. {
  98. int x = Top(my_stack);
  99. Pop(my_stack);
  100. int y =Top(my_stack);
  101. Pop(my_stack);
  102. Push(x+y, my_stack);
  103. //printf("%d\n", Top(my_stack));
  104. }
  105. else if (str[i] == ‘-‘)
  106. {
  107. int x = Top(my_stack);
  108. Pop(my_stack);
  109. int y = Top(my_stack);
  110. Pop(my_stack);
  111. Push(x-y, my_stack);
  112. //printf("%d\n", Top(my_stack));
  113. }
  115. else if (str[i] == ‘*‘)
  116. {
  117. int x = Top(my_stack);
  118. Pop(my_stack);
  119. int y = Top(my_stack);
  120. Pop(my_stack);
  121. Push(x*y, my_stack);
  122. //printf("%d\n", Top(my_stack));
  123. }
  124. else if (str[i] == ‘/‘)
  125. {
  126. int x = Top(my_stack);
  127. Pop(my_stack);
  128. int y = Top(my_stack);
  129. Pop(my_stack);
  130. Push(x/y, my_stack);
  131. //printf("%d\n", Top(my_stack));
  132. }
  133. }
  134. printf("The result is: %d\n", Top(my_stack));
  135. Pop(my_stack);
  136. /* A bug */
  137. // DisposeStack(my_stack);
  139. return 0;
  141. }

stack(顺序、链式及应用)

原文：http://www.cnblogs.com/tangtang-123/p/4436761.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)