栈的定义
栈是一种操作受限的线性表。只能在一端进行读取、插入、删除操作。实际上就是对链表、数组两个基本的数据结构进行操作限制。
特性表现：后进先出。
目的：对数据的操作加以限制，防止暴露太多的接口，加强数据的封装性。
栈的基本操作
栈的常见操作可以分为以下几种:
1、实现一个顺序栈、链式栈。实际是对数组、链表操作进行限制。
2、入栈 。将新元素存入栈顶。
3、出栈。将栈顶元素删除。
4、返回栈顶元素，而不删除。实际上就是在出栈前存储元素值。
Java 数组实现顺序栈代码
public class ArrayStack{
private int[] nums;
private int count;//记录数组元素个数
//初始化顺序栈
public ArrayStack(int n)
{
nums=new int[n];
count=0;
}
//入栈
public void Push(int x)
{
if(nums.length==count)
System.out.println("队列已满无法入队");
nums[count++]=x;
}
//出栈
public int Pop()
{
if(count==0)
throw new RuntimeException("栈为空，不可进行出栈操作");
int temp=int[count-1];
count--;
return temp;
}
//返回栈顶数,且不删除元素
public int Peek()
{
return nums[count];
}
}
Java 链表实现链式栈代码
class Node
{
private int val;
Node next;
public Node(int x,Node node)//节点初始化
{
val=x;
next=node;
}
public int getVal()
{
return val;
}
public void setVal(int n)
{
this.val=n;
}
}
public class ListStack
{
Node node;
//链表栈初始化
public ListStack()
{
node=null;
}
//入栈
public void Push(int x)
{
node =new Node(x,node);//头结点插入，新的数压栈，node 指向的变成新结点
}
//出栈
public int Pop()
{
if(node==null)
throw new RuntimeException("栈为空，不可进行出栈操作");
int temp=node.getVal();
node=node.next;
return temp;
}
//返回栈顶元素,且不删除元素
public int Peek()
{
if(node==null)
throw new RuntimeException("栈为空，栈顶无值");
return node.getVal();
}
}
总结：无论是顺序栈还是链式栈，在执行单次出栈、入栈操作时都是常数级别的操作所以时间复杂度都为 O(1)、空间复杂度为 O(1)。
面试考点
栈内元素排序
题目：按升序对栈进行排序，要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。
思路：
1、用栈实现选择排序法思想，每默认栈顶的数为最小数。
2、先将栈中的数按照从小到大的顺序压入临时栈 tempStack。
3、再将 tempStack 中依次压入 stack ，则 stack 升序排序完成
Java 代码实现
import java.util.Stack;
public class SortStack {
public void Sort(Stack<Integer> stack) {
Stack<Integer> tempStack = new Stack<>();
while (stack.size() != 0) {
int temp = stack.pop();
if (tempStack.size() == 0 || temp > tempStack.peek()) // 若是 tempStack 空，或是 temp 值大于 tempStack 栈顶值则将 temp 压栈
{
tempStack.push(temp);
} else {
//将新出现的最小值插入至合适位置，即 tempStack 栈顶出现小于 temp 元素，或是 tempStack 栈空 插入 temp
while (tempStack.size() != 0 && temp < tempStack.peek()) {
stack.push(tempStack.pop());
}
tempStack.push(temp);
}
}
while (tempStack.size() != 0)
stack.push(tempStack.pop());
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
SortStack stk = new SortStack();
stack.push(9);
stack.push(4);
stack.push(7);
stack.push(2);
stack.push(1);
stk.Sort(stack);
System.out.println(stack.size());
while (stack.size() != 0)
System.out.println(stack.pop());
}
}
| 
发表于 2019-3-10 20:44
|
发表于 2019-3-11 10:36
我也以为说的是内存中的，原来是容器。不过原理类似，还是很清晰的