java语言中用LinkList实现堆栈

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。

创新互联是一家专注于成都网站设计、网站建设与策划设计,余庆网站建设哪家好?创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:余庆等地区。余庆做网站价格咨询: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.

Java如何实现堆栈

//这是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实现数据结构“栈

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代码实现栈内存?

使用java.util包中的Stack类创建一个栈对象

public Object push(Object data);输入数据，实现压栈

public Object pop();输出数据，实现弹栈

public boolean empty()判空

public Object peek();查看栈顶元素

可以去查查API嘛

我也是学java的，大家一起进步。

java实现几种常见排序算法

下面给你介绍四种常用排序算法：

1、冒泡排序

特点：效率低，实现简单

思想（从小到大排）：每一趟将待排序序列中最大元素移到最后，剩下的为新的待排序序列，重复上述步骤直到排完所有元素。这只是冒泡排序的一种，当然也可以从后往前排。

2、选择排序

特点：效率低，容易实现。

思想：每一趟从待排序序列选择一个最小的元素放到已排好序序列的末尾，剩下的位待排序序列，重复上述步骤直到完成排序。

3、插入排序

特点：效率低，容易实现。

思想：将数组分为两部分，将后部分元素逐一与前部分元素比较，如果当前元素array[i]小，就替换。找到合理位置插入array[i]

4、快速排序

特点：高效，时间复杂度为nlogn。

采用分治法的思想：首先设置一个轴值pivot，然后以这个轴值为划分基准将待排序序列分成比pivot大和比pivot小的两部分，接下来对划分完的子序列进行快排直到子序列为一个元素为止。

网页题目：代码实现栈排序java 顺序栈入栈代码
URL标题：http://kswjz.com/article/hhcpss.html