目录
1.概述
计算机科学中，stack是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书。
说明：栈是线性的，只能在一端进行操作，分为栈顶和栈底两部分，包括入栈和出栈操作。
2.栈的接口设计
下面看一下栈的接口设计：
很简单，就是入栈，出栈，判断是否为空等操作。
3.用链表来实现栈
下面看一下如何用链表来实现栈：
代码：
public class L12_LinkedListStack<E> implements L12_Stack<E> {
/**定义节点类*/
public class Node{
E value;
Node next;
public Node() {
}
public Node(E value, Node next) {
this.value = value;
this.next = next;
}
}
private int capacity;//栈的容量
private int size;//栈中有效数据个数
Node head = new Node(null,null);
/*向栈顶添加元素*/
@Override
public boolean push(E value) {
if(isFUll())
return false;
Node node = new Node(value, head.next);
head.next = node;
size++;
return true;
}
/*弹出栈顶的元素*/
@Override
public E pop() {
if (isEmpty())
return null;
Node p = head.next;
head.next = p.next;
size--;
return p.value;
}
/*返回栈顶元素*/
@Override
public E peek() {
if (isEmpty())
return null;
return head.next.value;
}
@Override
public boolean isEmpty() {
return head.next==null;
}
@Override
public boolean isFUll() {
return size == capacity;
}
}
说明：总的来说还是很简单的，只要会链表的相关操作，那么就可以轻松实现
4.用数组来实现栈
下面来看一下如何用数组来实现栈：
代码：
public class L12_ArrayStack<E> implements L12_Stack<E>{
private E[] array;
private int top;//栈顶指针
public L12_ArrayStack(int capacity) {
this.array = (E[])new Object[capacity];
}
@Override
public boolean push(E value) {
if (isFUll())
return false;
array[top] = value;
top++;
return true;
}
@Override
public E pop() {
if (isEmpty())
return null;
E value = array[--top];
//top--;
return value;
}
@Override
public E peek() {
if (isEmpty())
return null;
return array[top-1];
}
@Override
public boolean isEmpty() {
return top == 0 ;
}
@Override
public boolean isFUll() {
return top == array.length;
}
}
说明：用数组实现栈也很简单。其中的关键点就是定义了一个指针top，你可以理解其为指针，也可以理解其为栈中有效元素的个数。这就是数组来实现一些线性数据的好处，数组的元素个数相当于一个指针，一个指针的值也相当于数组中元素的个数。
5.用两个栈来实现一个队列
下面俩看一下如何用两个栈来模拟一个队列：
代码：
public class L13_TwoStackToQueue {
L12_ArrayStack<Integer> s1 = new L12_ArrayStack(100);//前半个
L12_ArrayStack<Integer> s2 = new L12_ArrayStack(100);//后半个
/**入队操作，就是直接在后半个栈中压栈就行*/
public void push(int x){
s2.push(x);
}
/**出队操作*/
public int pop(){
if (s1.isEmpty()){
while (!s2.isEmpty()){
s1.push(s2.pop());
}
}
return s1.pop();
}
/**返回队首元素*/
public int peek(){
if (s1.isEmpty()){
while (!s2.isEmpty()){
s1.push(s2.pop());
}
}
return s1.peek();
}
public boolean empty(){
return s1.isEmpty() && s2.isEmpty();
}
}
说明：
栈只有一端可以操作，是先入后出的，队列是两端都可以操作，是先入先出的。那么肯定要有两个栈，一个做队首，一个做队尾。入队操作就是后面栈的入栈操作。关键在与于出队。我们可以将后面栈的元素依次出栈，然后再将这些元素依次压入到前面的一个栈中，这样就改变了元素的顺序，再使用前面一个栈的出栈操作，就实现了出队操作。判断空就是两个栈都为空时队列才为空。
6.用一个队列来实现一个栈
下面来看一下如何用一个队列来实现一个栈：
代码：
public class L14_QueueToStack {
L9_ArrayQueue1<Integer> q1 = new L9_ArrayQueue1(100);
private int size = 0;//记录队列中元素的个数
public void push(int x){
q1.offer(x);
for (int i = 0; i < size; i++) {
q1.offer(q1.poll());
}
size++;
}
public int poll(){
size--;
return q1.poll();
}
public int pop(){
return q1.peek();
}
public boolean empty(){
return q1.isEmpty();
}
}
说明：
首先，我们要明确哪里是栈顶，哪里相当于栈底。结合题目看，队首为栈顶，队尾为栈底。这个实现的关键在与入栈操作。当我们从队尾入队后，前面已经入队的元素就跑到栈顶了，这不符合栈的规则。怎么才能让后入的元素在栈顶即在队首？我们可以将前面已经入队的元素依次弹出，然后再将这些元素依次入队，这样我们新加入的元素就这栈顶了，也就是队首了。然后出栈操作和判断空就很简单了。
7.总结
栈其实也很简单。就是很简单入栈，出栈等操作。栈是单端口操作的数据结构，入栈和出栈都只在一个端口。栈可以用链表和数组来实现。栈的特点就是先入后出。
暂时就这么多吧
