Python干货整理之数据结构篇

悠悠 2023-06-11 10:26 27阅读 0赞

### 1 stack的实现 ###

实现接口：

*  init() 用于初始化stack，数据类型为list
 *  size() 用于获得stack的大小
 *  push() 用于往栈中添加元素，添加的元素类型可以是int或者list
 *  top(）获取栈顶元素
 *  pop() 弹出并返回栈顶元素
 *  print\_stack() 打印栈

class Stack(object):
        def __init__(self):
            self.len = 0
            self._stack = []
            
        def init(self, init_list):
            self._stack = init_list
            self.len = len(init_list)
        
        def size(self):
            return self.len
        
        def push(self, val):
            if isinstance(val, int):
                self._stack.append(val)
                self.len += 1
            elif isinstance(val, list):
                self._stack.extend(val)
                self.len += len(val)
            else:
                assert isinstance(val, int) or isinstance(val, list)
        
        def top(self):
            return None if self.len == 0 else self._stack[self.len - 1]
        
        def pop(self):
            if self.len == 0:
                assert self.len > 0
            else:
                self.len -= 1
                return self._stack.pop()
            return None
        
        def print_stack(self):
            print('Bottom |', *self._stack, '| Top >')

测试结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70][]

### 2 quque的实现 ###

实现接口：

*  init() 用于初始化队列，数据类型为list
 *  size() 用于获得队列的大小
 *  push() 用于往队列尾部添加元素，添加的元素类型可以是int或者list
 *  rear(）获取队列尾部元素
 *  front() 获取队列头部元素
 *  pop() 弹出并返回队列头部元素
 *  print\_queue() 打印队列

class Queue(object):
        def __init__(self):
            self.len = 0
            self._queue = []
            
        def init(self, init_list):
            self._queue = init_list
            self.len = len(init_list)
        
        def size(self):
            return self.len
        
        def push(self, val):
            if isinstance(val, int):
                self._queue.append(val)
                self.len += 1
            elif isinstance(val, list):
                self._queue.extend(val)
                self.len += len(val)
            else:
                assert isinstance(val, int) or isinstance(val, list)
        
        def rear(self):
            return None if self.len == 0 else self._queue[self.len - 1]
        
        def front(self):
            return None if self.len == 0 else self._queue[0]
        
        def pop(self):
            assert self.len > 0
            self.len -= 1
            return self._queue.pop(0)
        
        def print_queue(self):
            print('Front |', *self._queue, '| Rear >')

测试结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70]: /images/20230531/c26196f794e94e8eaef96a2b0f4decd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 1]: /images/20230531/da5f7fa9cee049c38f661a1031c6b085.png