---

5-1 栈和队列

---

目录

小节	位置
5.1.1	栈的概念
5.1.2	栈的python实现
5.1.3	队列的概念
5.1.4	队列的python实现

5.1.1 栈的概念

栈是限制仅在表的一端进行插入和删除操作的线性表。
通常称插入、删除的这一端为【栈顶】， 另一端称为栈底。当表中没有元素时称为空栈。
由于栈中元素的插入和删除操作都只能在栈顶进行，所以总是后进栈的先出栈。即：
(LIFO) Last In First Out. 后进先出

栈的基本操作有如下几种:

操作名称	操作内容
init()	将栈初始化为空
empty()	判空栈，判断栈是否为空
size()	求长度，返回栈中元素的个数
top()	取栈顶， 读取栈顶元素，但并不修改栈
pop()	若栈非空，则删除栈顶元素，（亦称 弹出）
push(x)	在栈顶插入元素，（亦称为 压入/压栈）

5.1.2 栈的python实现

5.1.2.1 顺序栈

就是用顺序表来实现栈，其 python code 如下所示:

class Sequence_Stack(object):
    def __init__(self):
        '''使用空列表进行初始化'''
        self.__list = []
    
    def is_empty(self):
        '''判断栈是否为空'''
        return self.__list == []

    def size(self):
        '''返回栈里元素的个数'''
        return len(self.__list)

    def top(self):
        '''返回栈顶元素'''
        if self.is_empty():
            return None
        else:
            return self.__list[-1]

    def pop(self):
        '''弹出栈顶元素'''
        return self.__list.pop()

    def push(self, val):
        '''在栈顶压入元素'''
        self.__list.append(val)
        return True        

5.1.2.2 链栈

一般将链表头部作为栈顶，这样可以避免在 入栈 和 出栈的时候进行大量的遍历操作。

class LNode(object):
    def __init__(self, val=None):
        self.val = val    # 数据域
        self.next = None  # 指针域

class Link_stack(object):
    def __init__(self):
        self.__top = None

    def is_empty(self):
        return self.__top is None

    def size(self):
        count = 0
        cur = self.__top
        while cur is not None:
            count += 1
            cur = cur.next

        return count

    def top(self):
        if self.is_empty():
            return None
        else:
            return self.__top.val

    def pop(self):
        cur = self.__top
        if cur is not None:
            self.__top = cur.next # 修改头结点
            return cur.val
        else:
            return None

    def push(self, val):
        node = LNode(val)
        node.next = self.__top
        self.__top = node # 修改头结点
        return True

5.1.3 队列的概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的 前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。前端称为队头 ，后端称为队尾。
FIFO (First In First Out) 先进先出

队列的基本操作有如下几种:

操作名称	操作内容
init()	将队列初始化为空
empty()	判断队列是否为空
size()	求长度，返回队列中元素的个数
front()	取队头元素，若队列未空，则函数返回队头 数据元素，队列不变。
rear()	取队尾元素，若队列未空，则函数返回队尾 数据元素，队列不变。
enqueue(x)	入队列，若队列未满，在原队尾后加入数据元素x，使x成为新的队尾元素。
dequeue()	出队列，若队列未空，则将队列的队头元素删除。

5.1.4 队列的python实现

5.1.4.1 顺序表实现

class Sq_Queue(object):
    def __init__(self):
        '''使用空列表进行初始化'''
        self.__list = []

    def is_empty(self):
        '''判断队列是否为空'''
        return self.__list == []

    def size(self):
        '''返回队列里元素的个数'''
        return len(self.__list)

    def front(self):
        '''返回队头元素'''
        if self.is_empty():
            return None
        else:
            return self.__list[0]

    def rear(self):
        '''返回队尾元素'''
        if self.is_empty():
            return None
        else:
            return self.__list[-1]

    def dequeue(self):
        '''弹出队头元素'''
        return self.__list.pop(0)

    def enqueue(self, val):
        '''在队尾压入元素'''
        self.__list.append(val)
        return True

5.1.4.2 链表实现

我们在插入的时候，选择在链表尾部使用尾插法插入，所以链表尾部视为队尾rear；
在删除时，为了方便起见，我们可以把头结点认为是front.

class LNode(object):
    def __init__(self, val=None):
        self.val = val    # 数据域
        self.next = None  # 指针域
        
class L_Queue(object):
    def __init__(self):
        # 初始化时同时设置头和尾两个指针
        self.__front = None
        self.__rear = None

    def is_empty(self):
        return self.__front is None

    def size(self):
        if self.is_empty():
            return 0
        else:
            cnt, cur = 1, self.__front
            while cur != self.__rear:
                cur = cur.next
                cnt +=1
            return cnt 

    def front(self):
        res = None if self.is_empty() else self.__front.val
        return res

    def rear(self):
        res = None if self.is_empty() else self.__rear.val
        return res

    def dequeue(self):
        cur = self.__front
        if cur is None:
            return None
        else:
            self.__front = cur.next
            if self.__front is None:
                # 出队后队列为空(原队列仅含一个元素)
                self.__rear = None
            return cur.val


    def enqueue(self, val):
        node = LNode(val)
        if self.__rear is None:
            # 说明当前链表(队列)为空
            self.__front = node
            self.__rear = node
        else:
            self.__rear.next = node
            self.__rear = node
        return True