并发栈被广泛应用于并行应用程序和操作系统中。并发栈支持线性栈常用的push和pop操作,并且能够满足可线性化的后进先出语义。并发栈算法可以充分利用多核处理器的优势,获得更高的性能。目前已有的栈的并发算法主要包括加锁和通用构造两种实现方式,但其性能效果并不理想。其中基于锁的方式难以实现高的并行性,并且某些线程的延迟或停止会阻塞其他线程的运行。而通用构造方式实现复杂,效率不高,实用性不强。因此研究实用的并发栈算法势在必行。无等待特性保证了所有的线程一定能够在有限的步骤内完成,在工程实践中容错性较强,不容易产生故障。因此,即使某个线程突然崩溃,也不会影响其他线程的正常运行。论文在已有研究的基础上,对阻塞和非阻塞的并发栈算法进行研究,完成了以下工作:(1)提出并实现了一种新的无等待的并发栈算法。算法的基本思想是所有的入栈和出栈操作均需要新建结点插入到链表头部,出栈操作在插入结点后还需要遍历链表查找匹配的入栈结点,查找正确出栈结点这一操作使用了引用计数的思想。同时算法采用了帮助机制保证入栈和出栈操作的结点的插入是无等待的,从而保证整个算法是无等待的。目前还没有出现过基于计数思想的栈的研究,因此算法对并发栈的研究具有一定的实用价值;(2)同时论文对目前的并发栈的研究工作做了综述,对各种栈的实现及其优缺点做了详细介绍,说明了目前并发栈的研究现状;(3)最后讨论了程序的正确性证明的必要性,并从可线性化性和无等待特性两方面对算法的正确性进行了证明。