栈

栈**

博客分类：

• 数据结构 数据结构

【栈】 是限定仅在表尾进行插入或删除操作的线性表 表尾称为栈顶，表头称为栈底 特点：后进先出

操作： 1.推入push 2.弹出pop

栈的数组实现

Java代码

1. public class ArrayStack {
3. private List list = new ArrayList();
5. public boolean isEmpty(){
6. return list.size()==0;
7. }
9. public void push(E element){
10. list.add(element);
11. }
13. public void pop(){
14. list.remove(list.size()-1);
15. }
17. public E getPop(){
18. return list.get(list.size()-1);
19. }
21. public List getElements(){
22. List result = new ArrayList();
23. for(E e : list){
24. result.add(((Element)e).getValue());
25. }
26. return result;
27. }
29. }

栈的链表实现

Java代码

1. public class LinkedStack{
3. private static class Node{
5. E element;
7. Node next;
9. public Node(E element){
10. this.element = element;
11. }
13. }
15. private Node top = new Node(null);
17. private int size = 0;
19. public boolean isEmpty() {
20. return size == 0;
21. }
23. public void push(E element){
24. Node newNode = new Node(element);
25. if(!isEmpty()){
26. newNode.next = getPopNode();
27. top.next = newNode;
28. }else{
29. top.next = newNode;
30. }
31. size++;
32. }
34. public void pop(){
35. if(isEmpty()){
36. throw new RuntimeException("The stack is empty");
37. }
38. Node firstNode = top.next;
39. top.next = firstNode.next;
40. firstNode.next = null;
41. size--;
42. }
44. public E getPop(){
45. return getPopNode().element;
46. }
48. private Node getPopNode(){
49. if(isEmpty()){
50. throw new RuntimeException("The stack is empty");
51. }
52. return top.next;
53. }
55. public List getElements(){
56. if(isEmpty()){
57. return null;
58. }else{
59. List elements = new ArrayList();
60. Node node = (Node) top;
61. while(node.next!=null){
62. node = node.next;
63. elements.add(((Element)node.element).getValue());
64. }
65. return elements;
66. }
67. }
69. }

来源： [http://tangyanbo.iteye.com/blog/1472830](http://tangyanbo.iteye.com/blog/1472830)