stack

definition

Stack is a last in first out (LIFO) data structure. In the push down stack, only two operations are allowed: push the object into the stack and pop the object from the stack. Elements can only be added and deleted at the top of the stack. Push adds the object to the top of the stack, and pop removes the object from the top.

A well understood example is a stack of books. You can take (delete) only the books at the top, or add new books at the top.

application

• The simplest application of the stack is to reverse a word. You push the given word letter by letter onto the stack (stack), and then pop the letter from the stack (stack).
• Undo mechanism in the text editor; this is done by saving all text changes on the stack.
• to flash back. Think about how to find the way out of the maze?
• Language processing:
  • The space for parameters and local variables is created internally using the stack
  • The compiler's syntax check for matching braces is achieved by using the stack
  • Support recursion

Given a string, {XXX [XXX {XXX}] XX {x [XXX] XXX {XXX} XX}

Judge whether the {}[] () appears in pairs

• realization

# test_stack_and_queue.py
import pytest


class Stack:
    """
    Create a simulation stack stack
    """
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)

    def pop(self):
        self._data.pop()

    def top(self):
        return self._data[-1]

    def get_size(self):
        if len(self._data) == 0:
            return True
        else:
            return False

    def get_data(self):
        return self._data


class TestStack:
    """
    Create a test class
    """
    def setup(self):
        self.stack = Stack()

    def pattern(self, data):
        brackets_dict = {")": "(", "]": "[", "}": "{"}
        for p in data:
            if p in "{[(":
                self.stack.push(p)
            elif p in ")]}":
                """handle stack in_data No data"""
                try:
                    top = self.stack.top()
                    self.stack.pop()
                    """Determine whether the brackets correspond"""
                    if brackets_dict[p] != top:
                        return False
                except IndexError:
                    return False
        return self.stack.get_size()

    """Assertion validation"""
    def test_pattern_1(self):
        test_data = '{xxx[xxx{xxx}]xx{x[xxx]xxx{xxx}xx}x}'
        assert self.pattern(test_data)== True

    def test_pattern_2(self):
        assert self.pattern('{@')==False

    def test_pattern_3(self):
        assert self.pattern('{}')==True

    def test_pattern_4(self):
        assert self.pattern("{}{}{}[]()")==True

if __name__ == '__main__':
    pytest.main(['-s'])
"""
test_stack_and_queue.py ....

============================== 4 passed in 0.02s ==============================
"""

queue

Queue is a first in first out (FIFO) data structure. A well understood example is a row of students in the canteen square. New lines added to the back of the queue, while removal (or service) occurs in the front. Queuing means inserting an object into the back of the queue, and dequeuing means deleting the previous item.

• realization

Simulate a FIFO data structure, append data at the end of the queue, and then pop data at the head of the queue.

class Queue:

    def __init__(self):
        self._data = []

    def put(self, item):
        self._data.append(item)

    def get(self):
        result = self._data[0]
        self._data.remove(result)
        return result
    
if __name__ == '__main__':
    """test"""
    q = Queue()
    q.put('Zhang San')
    q.put('Li Si')
    q.put('Wang Wu')
    print(q.get())
    print(q.get())
    print(q.get())
"""
Zhang San
 Li Si
 Wang Wu
"""

reference material

https://www.andrew.cmu.edu/course/15-121/lectures/Stacks and Queues/Stacks and Queues.html