算法漫游指北（第五篇）：栈、队列、栈结构实现、基于列表实现栈、基于链表实现栈、基于列表实现队列、基于链表实现队列

Stack()    建立一个空的栈对象
push()     把一个元素添加到栈的最顶层
pop()      删除栈最顶层的元素，并返回这个元素
peek()     返回最顶层的元素，并不删除它
isEmpty()  判断栈是否为空
size()     返回栈中元素的个数

class Stack(object):
    """栈"""
    def __init__(self):
         self.items = []
?
    def is_empty(self):
        """判断是否为空"""
        return self.items == []
?
    def push(self, item):
        """加入元素"""
        self.items.append(item)
?
    def pop(self):
        """弹出元素"""
        if self.is_empty():
            raise IndexError,‘pop from empty stack‘
        return self.items.pop()
?
    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items)-1]
?
    def size(self):
        """返回栈的大小"""
        return len(self.items)
?
if __name__ == "__main__":
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    print stack.size()
    print stack.peek()
    print stack.pop()
    print stack.pop()
    print stack.pop()

class Node:
    """链表节点类"""
    def __init__(self,val):
        self.val = val
        self.next = None
?
    def __str__(self):
        return str(self.val)
 
class LinkedListStack:
    """链表结构堆栈类"""
    def __init__(self):
        """初始化堆栈的属性"""
        self.head = None
        self.top = self.head  # 堆栈的顶端，当前表示堆栈为空
        self.length = 0
 
    def is_empty(self):
        """判断堆栈是否为空"""
        if self.top == None:
            return True
        else:
            return False
 
    def push(self, item):
        """向堆栈中存入数据"""
        new_node = Node(item)   #创造节点类
        new_node.next = self.top   #设置node为栈顶
        self.top = new_node   #将设置过的栈顶的指针指向原栈顶
        self.length += 1
        print("成功存入数据",item)
 
    def pop(self):
        """从堆栈中取出数据"""
        if self.is_empty():
            print("堆栈已空，不能再取数据")
        node =  self.top     # 先取到原栈顶
        self.top = self.top.next   # 将栈顶设置为原栈顶的下一个元素
        self.length -= 1
        print("取出数据",node.val)
?
        return node.val    # 返回原栈顶的值
?
    def peek(self):
        """获取栈顶元素"""
        if self.is_empty():
            raise Exception("堆栈已空!")
        print(‘查看栈顶元素‘,self.top.val)
        return self.top.val
?
    def size(self):     
        """得到栈的长度"""
        return self.length
?
    def show(self):    #输出栈
        def _traversal(self):
            node = self.top
            while node and node.next:
                yield node 
                node = node.next
            yield node   # 这里如果不yield，则栈底的元素会无法被遍历到，因为最后一个元素并不满足while循环的条件，会中止迭代
        print(‘\n‘.join(map(lambda x:‘|{:^7}|‘.format(str(x)),_traversal(self)))+ ‘\n‘ + 7*‘-‘)
        
 
if __name__ == ‘__main__‘:
    s = LinkedListStack()
    s.push(10)
    s.push(20)
    # s.pop()
    s.show()
    s.push(30)
    s.peek()
    s.show()
    s.pop()
    s.show()

- Queue() 创建一个空的队列
- enqueue(item) 往队列中添加一个item元素
- dequeue() 从队列头部删除一个元素
- is_empty() 判断一个队列是否为空
- size() 返回队列的大小

class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []
?
    def is_empty(self):
        return self.items == []
?
    def enqueue(self, item):
        """进队列"""
        self.items.insert(0,item)
?
    def dequeue(self):
        """出队列"""
        return self.items.pop()
?
    def size(self):
        """返回大小"""
        return len(self.items)
?
if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("nicholas")
    print q.size()
    print q.dequeue()
    print q.dequeue()
    print q.dequeue()

class Node:
    """链表节点类"""
    def __init__(self,val):
        self.val = val
        self.next = None
?
    def __str__(self):
        return str(self.val)
 
class LinkedListQueue:
    """链表结构堆栈类"""
    def __init__(self):
        """初始化队列的属性"""
        self.front = None  #队列头部元素
        self.rear =  None  #队尾元素
        self.length = 0  #队列长度
 
    def is_empty(self):
        """判断队列是否为空"""
        if self.front == None:
            return True
        else:
            return False
 
?
    def enqueue(self,item):
        """进队列，向队列中加入一个元素"""
        node=Node(item)
        if self.is_empty():
            self.front = node
        else:
            self.rear.next=node
        self.rear = node
        self.length += 1
        print(‘向队列中加入‘,item)
?
?
    def dequeue(self):
        """出队列，从队列中取出一个元素"""
        if self.front is None:
            raise "The queue is empty"
        elif self.front is self.rear:
            self.rear = None
        item = self.front.val
        self.front = self.front.next
        self.length -= 1
        print("取出数据",item)
        return item
?
    def peek(self):
        """查看队列头部"""
        if self.is_empty():
            raise Exception("队列已空!")
        print(‘查看队列头部元素‘,self.front.val)
        return self.front.val
?
    def size(self):     
        """得到队列的长度"""
        return self.length
?
    def show(self):    #显示队列
        def _traversal(self):
            node = self.front
            while node and node.next:
                yield node 
                node = node.next
            yield node   # 这里如果不yield，则队列最后的元素会无法被遍历到，因为最后一个元素并不满足while循环的条件，会中止迭代
        print(‘\n‘.join(map(lambda x:‘|{:^7}|‘.format(str(x)),_traversal(self)))+ ‘\n‘ + 7*‘-‘)
        
 
if __name__ == ‘__main__‘:
    s = LinkedListQueue()
    s.enqueue(10)
    s.enqueue(20)
    s.enqueue(30)
    s.enqueue(40)
    s.enqueue(50)
    s.dequeue()
    s.show()
    s.enqueue(60)
    s.peek()
    s.show()
    s.dequeue()
    s.show()