栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。
创新互联是一家专注于成都网站设计、网站建设与策划设计,余庆网站建设哪家好?创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:余庆等地区。余庆做网站价格咨询:028-86922220
LinkedList数据结构是一种双向的链式结构，每一个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素，和数组的顺序存储结构（如：ArrayList）相比，插入和删除比较方便，但速度会慢一些。
栈的定义
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
实现代码：
package com.weisou.dataStruct;
import java.util.LinkedList;
@SuppressWarnings("unchecked")
public class MyStack {
LinkedList linkList = new LinkedListObject();
public void push(Object object) {
linkList.addFirst(object);
}
public boolean isEmpty() {
return linkList.isEmpty();
}
public void clear() {
linkList.clear();
}
// 移除并返回此列表的第一个元素
public Object pop() {
if (!linkList.isEmpty())
return linkList.removeFirst();
return "栈内无元素";
}
public int getSize() {
return linkList.size();
}
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(2);
myStack.push(3);
myStack.push(4);
System.out.println(myStack.pop());
System.out.println(myStack.pop());
}
}
队列定义
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
实现代码：
package com.weisou.dataStruct;
import java.util.LinkedList;
/**
*
* @author gf
* @date 2009-11-13
*/
public class MyQueue {
LinkedList linkedList = new LinkedList();
//队尾插
public void put(Object o){
linkedList.addLast(o);
//队头取 取完并删除
public Object get(){
if(!linkedList.isEmpty())
return linkedList.removeFirst();
else
return "";
}
public boolean isEmpty(){
return linkedList.isEmpty();
}
public int size(){
return linkedList.size();
}
public void clear(){
linkedList.clear();
}
/**
* @param args
*/
public static void main(String[] args) {
MyQueue myQueue= new MyQueue();
myQueue.put(1);
myQueue.put(2);
myQueue.put(3);
System.out.println(myQueue.get());
}
}
单栈排序
Tom最近在研究一个有趣的排序问题:有一个1~n的输入序列和1个栈S，Tom希望借助以下2种操作实现将输入序列升序排序。
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
如果一个1-n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可单栈排序排列”。
【输入】第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】输出文件共一行，如果输入的排列不是“可单栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
------------------------------
定理：考虑对于任意两个数q[i]和q[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得ijk且q[k]q[i]q[j]。
充分性证明：即如果满足上述条件,那么q[i]和q[j]一定不能压入同一个栈：
反证法:假设这两个数压入了同一个栈,那么在压入q[k]的时候栈内情况如下:
+----+
|q[j] |
+----+
|... |
+----+
|q[i] |
+----+
因为q[k]比q[i]和q[j]都小,所以很显然,当q[k]没有被弹出的时候,另两个数也都不能被弹出(否则输出序列的数字顺序就不是1,2,3,…,n了)。而之后,无论其它的数字在什么时候被弹出,q[j]总是会在q[i]之前弹出，而q[j]q[i],这显然是不正确的.
必要性证明：如果两个数不可以压入同一个栈,那么它们一定满足上述条件。
证明逆否命题：也就是"如果不满足上述条件,那么这两个数一定可以压入同一个栈." 不满足上述条件有两种情况:
情况1：对于任意ijk且q[i]q[j],q[k]q[i];
情况2：对于任意ij,q[i]q[j].
第一种情况：在q[k]被压入栈的时候,q[i]已经被弹出栈。那么,q[k]不会对q[j]产生任何影响(这里可能有点乱,因为看起来,q[j]q[k]的时候是会有影响的,但实际上,这还需要另一个数r,满足jkr且 q[r]q[j]q[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q[k]对q[j]没有影响)。 第二种情况：可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈. 这样,原命题的逆否命题得证,所以原命题得证。
由此得出有解的判断方法：对所有的数对(i,j)满足1≤ij≤n,检查是否存在ijk满足q[k]q[i]。
var
n,top,i,j,k:longint;{序列长度为n，栈指针为top}
ans:string;{操作序列}
st:array [1..1000000] of longint;{栈}
begin
read(n);{读序列长度}
top:=0;j:=1;ans:='';{栈和输出序列空，从1开始输出}
for i:=1 to n do{依次处理每个数字}
begin
read(k);ans:=ans+'a ';inc(top);st[top]:=k;{读当前数字，进行a操作，该数字入栈}
while st[top]=j do {若栈顶满足递增要求，则出栈（进行b操作），下一个输出数字应+1，这一过程反复进行，直至不满足条件为止}
begin dec(top);inc(j);ans:=ans+'b 'end end;
if j=n {若未输出1¨n，则失败退出；否则输出操作序列}
then writeln(0)
else writeln(copy(ans,1,length(ans)-1))
end.
================================================================
双栈排序
【问题描述】Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a：如果输入序列不为空，将第一个元素压入栈S1
操作b：如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c：如果输入序列不为空，将第一个元素压入栈S2
操作d：如果栈S2不为空，将S2栈顶元素弹出至输出序列
+--------------------
s1 |
+--------------------
+--------------------
s2 |
+--------------------
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。
例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：a,c,c,b,a,d,d,b
(这个图网上有，你自己找找吧）
当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，a,c,c,b,a,d,d,b是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【输入】输入文件twostack.in的第一行是一个整数n。第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
========================================
简述题意
有两个队列和两个栈,分别命名为队列1(q1),队列2(q2),栈1(s1)和栈2(s2)。最初的时候,q2,s1和s2都为空,而q1中有n个数(n≤1000),为1~n的某个排列.现在支持如下四种操作: a操作,将 q1的首元素提取出并加入s1的栈顶； b操作,将s1的栈顶元素弹出并加入q2的队列尾；
c操作,将 q1的首元素提取出并加入s2的栈顶； d操作,将s2的栈顶元素弹出并加入q2的队列尾；请判断,是否可以经过一系列操作之后,使得q2中依次存储着1,2,3,…,n.如果可以,求出字典序最小的一个操作序列.
1、判断是否有解和任意两个数能否压入同一个栈
⑴、对任意两个数q[i]和q[j],若存在一个k,使得ijk且q[k]q[i]q[j]，则这两个数分别入s1栈和s2栈
⑵、将s1栈和s2栈中的数字组合成两个顶点子集，同一顶点子集内不会出现任何连边,即不能压入同一个栈的所有数字被分到了两个栈中。任两个不在同一栈的数字间连边。此时我们只考虑检查是否有解,所以只要化O(n)时间检查这个图是不是二分图,就可以得知是否有解了。
======================================================
二分图及二分图的匹配
二分图是一种特殊类型的图：图中的顶点集被划分成X与Y两个子集,图中每条边的两个端点一定是一个属于X而另一个属于Y。二分图的匹配是求边的一个子集，该子集中的任意两条边都没有公共的端点。
======================================================
找字典序最小的解
1、确定每个数字入哪个栈，即构造二分图
把二分图染成1和2两种颜色,染色为1的结点被压入s1栈, 染色为2结点被压入s2栈。为了字典序尽量小,我们希望让编号小的结点优先压入s1栈。 由于二分图的不同连通分量之间的染色是互不影响的,所以可以每次选取一个未染色的编号最小的结点,将它染色为1，并从它开始DFS染色,直到所有结点都被染色为止。这样,我们就得到了每个结点应该压入哪个栈中。
2、从数字1开始，按照目标序列的递增顺序构造操作序列
先处理入栈：按照搜索递增顺序每个顶点：若顶点i的颜色为1，则进行a操作，q1[i]入s1栈；若顶点i的颜色为2，则进行c操作，q1[i]入s2栈。
后处理出栈：若s1栈的栈顶元素为目标序列的当前数字k，则进行b操作，数字k出s1栈；若s2栈的栈顶元素为目标序列的当前数字k，则进行d操作，数字k出s2栈。
然后k+1,继续模拟，直至k为n为止。
==========================================================
数据结构
var
a,b,head,next,point,color:array[0..2001]of longint;{初始序列为a（对应q1），后缀的最小值序列为b，其中b[i]=min{a[k]}(i=k=n)；邻接表的表首顶点为head，后继指针为next，顶点序列为point，顶点的涂色序列为color}
s:array[1..2,0..1000]of longint;{s[1]栈，栈首指针为s[1,0];s[2]栈, 栈首指针为s[2,0]}
n,p,i,j,last:longint;{序列长度为n，当前应取数字为last}
procedure badend;{输出失败信息}
begin
writeln(0);close(output);halt;
end;
procedure addedge(a,b:longint);{（a,b）进入邻接表}
var t:longint;
begin
inc(p);point[p]:=b;{增加顶点b}
if head[a]=0 {（a,b）进入邻接表}
then head[a]:=p
else begin
t:=head[a];
while next[t]0 do t:=next[t];
next[t]:=p;
end;
end;
procedure dfs(now:longint);
var t:longint;
begin
t:=head[now];{搜索与顶点now相邻的所有顶点}
while t0 do
begin
if color[point[t]]=0{若顶点now相邻的顶点point[t]未涂色，则该顶点涂互补色，沿该顶点递归下去}
then begin
color[point[t]]:=3-color[now];dfs(point[t]);
end;
if color[point[t]]=color[now] then badend;{若顶点now与相邻顶点point[t]涂相同色，则失败退出}
t:=next[t];{访问与顶点now相邻的下一个顶点}
end;
end;
begin
assign(input,'twostack.in');reset(input);{输入文件读准备}
assign(output,'twostack.out');rewrite(output);{输出文件写准备}
fillchar(s,sizeof(s),0);fillchar(a,sizeof(a),0);{两栈空}
readln(n);{读入排列}
for i:=1 to n do read(a[i]);
b[n+1]:=maxlongint;p:=0;
for i:=n downto 1 do{计算b[i]= }
begin
b[i]:=b[i+1];
if a[i]b[i] then b[i]:=a[i];
end;
for i:=1 to n do
for j:=i+1 to n do
if (b[j+1]a[i])and(a[i]a[j]) {若a[i]和a[j]不能不能压入同一个栈，则(i,j)和(j,i)进入邻接表}
then begin addedge(i,j);addedge(j,i);end;
for i:=1 to n do{所有未涂色的顶点涂颜色1，递归}
if color[i]=0 then begin color[i]:=1;dfs(i);end;
last:=1;{目标序列初始化}
for i:=1 to n do{模拟输出序列}
begin
if color[i]=1 {a[i]入s[1]或s[2]栈}
then write('a ')
else write('c ');
inc(s[color[i],0]);s[color[i],s[color[i],0]]:=a[i];
while (s[1,s[1,0]]=last)or(s[2,s[2,0]]=last) do
begin{将s[1]或s[2]栈顶的数字last取出}
if s[1,s[1,0]]=last then begin write('b ');dec(s[1,0]);end;{将s[1]栈顶的last取出}
if s[2,s[2,0]]=last then begin write('d ');dec(s[2,0]);end;{将s[2]栈顶的last取出}
inc(last);{按递增要求取下一个数字}
end;
end;
close(input);close(output);{关闭输入输出文件}
end.
//这是JDK提供的栈
import java.util.Stack;
public class UsingStack {
public static void main(String[] args) {
//构造栈对象，使用类型限制，只能存储Integer数据
StackInteger s = new StackInteger();
//1、2、3依次入栈
s.push(1);
s.push(2);
s.push(3);
//3、2、1依次出栈
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
}
}
//这是我写的顺序结构的栈
import java.util.EmptyStackException;
import java.util.Vector;
public class UsingStack{
public static void main(String[] args){
//构造栈对象，使用类型限制，只能存储Integer数据
MyStackInteger s = new MyStackInteger();
//1、2、3依次入栈
s.push(1);
s.push(2);
s.push(3);
//3、2、1依次出栈
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
}
}
/**
* 栈类
* @author developer_05
* @param T
*/
class MyStackT extends VectorT{
/**
* 构造方法
*/
public MyStack(){
}
/**
* 入栈方法
* @param item 待入栈的元素
* @return 返回入栈的元素
*/
public T push(T item) {
addElement(item);
return item;
}
/**
* 出栈方法(同步处理)
* @return 返回出栈元素
*/
public synchronized T pop() {
T obj;
int len = size();
if (len == 0)
throw new EmptyStackException();
obj = elementAt(len - 1);
removeElementAt(len - 1);
return obj;
}
/**
* 判断栈是否为空的方法
* @return 返回true(栈空)或false(栈非空)
*/
public boolean empty() {
return size() == 0;
}
private static final long serialVersionUID = 1L;
}
Java栈的实现
public class MyStack { //定义一个堆栈类
int[] array; //用int数组来保存数据，根据需要可以换类型
int s_size; //定义堆栈的宽度
public MyStack(int i){ //定义一个带参数构造器
array=new int[i]; //动态定义数组的长度
s_size=0; //堆栈的默认宽度为0
}
public MyStack(){ //默认构造器
this(50); //默认构造器可容纳50个元素
}
public void push(int i){ //压栈
array[this.s_size]=i;
this.s_size++;
}
public int pop(){ //从堆栈中取元素，从栈顶开始取
if(this.s_size!=0){
int t=array[s_size-1]; //用中间变量保存栈顶的元素
array[s_size-1]=0; //取完元素该位置设为0
s_size--; //栈的大小减1
return t; //返回栈顶元素
}else{
System.out.println("This stack is empty"); //当栈为空时显示提示信息，返回0
return 0;
}
}
public boolean isEmpty(){ //判断栈是否为空
return this.s_size==0;
}
public int top(){ //从栈顶取值，功能和 pop() 方法一样
if(!this.isEmpty()){
int t=array[this.s_size-1];
array[this.s_size-1]=0;
this.s_size--;
return t;
}else{
System.out.println("This stack is empty!");
return 0;
}
}
public void printAll(){ //打印出堆栈中的所有元素的值，不是取出，元素依然在堆栈里
if(!this.isEmpty()){
for(int i=this.s_size - 1;i=0;i--){
System.out.println(array[i]);
}
}
}
//下面是测试代码
public static void main(String[] args){
MyStack stack=new MyStack();
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
//System.out.println(stack.isEmpty());
stack.printAll();
System.out.println("===========");
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.top());
System.out.println(stack.top());
}
}
使用java.util包中的Stack类创建一个栈对象
public Object push(Object data);输入数据，实现压栈
public Object pop();输出数据，实现弹栈
public boolean empty()判空
public Object peek();查看栈顶元素
可以去查查API嘛
我也是学java的，大家一起进步。
下面给你介绍四种常用排序算法：
1、冒泡排序
特点：效率低，实现简单
思想（从小到大排）：每一趟将待排序序列中最大元素移到最后，剩下的为新的待排序序列，重复上述步骤直到排完所有元素。这只是冒泡排序的一种，当然也可以从后往前排。
2、选择排序
特点：效率低，容易实现。
思想：每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾，剩下的位待排序序列，重复上述步骤直到完成排序。
3、插入排序
特点：效率低，容易实现。
思想：将数组分为两部分，将后部分元素逐一与前部分元素比较，如果当前元素array[i]小，就替换。找到合理位置插入array[i]
4、快速排序
特点：高效，时间复杂度为nlogn。
采用分治法的思想：首先设置一个轴值pivot，然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小的两部分，接下来对划分完的子序列进行快排直到子序列为一个元素为止。