栈

栈是一种线性的数据结构，遵循先进后出的原则，最后入栈的元素最先被去除，也就是说栈只能在栈顶进行插入和删除操作，而不能在栈中间或底部进行操作。

实现

#include <bits/stdc++.h>
using namespace std;

struct Stack
{
private:
    int size;
    int top;
    int *arr;

public:
    Stack(int size) : top(-1), size(size)
    {
        arr = new int[size];
    }

    bool IsEmpty()
    {
        return top == -1;
    }

    int Push(int val)
    {
        if (top + 1 == size)
        {
            // 自动扩容
            int *temp = new int[size * 2];
            copy(arr, arr + size, temp);
            arr = temp;
            size *= 2;
        }

        arr[++top] = val;
        return val;
    }

    int Pop()
    {
        return arr[top--];
    }

    int Top()
    {
        if (top >= 0)
        {
            return arr[top];
        }
        else
        {
            return -1;
        }
    }

    void Print()
    {
        for (int i = 0; i <= top; i++)
        {
            cout << arr[i] << " ";
        }
        cout << endl;
    }

    int GetSize()
    {
        return size;
    }

    int GetTop()
    {
        return top;
    }
};

int main()
{
    Stack *stack = new Stack(10);
    for (int i = 0; i <= 20; i++)
    {
        stack->Push(i);
    }

    for (int i = 0; i <= 20; i++)
    {
        cout << stack->Pop() << " ";
    }
}

队列

与栈类似，先进先出

实现

#include <bits/stdc++.h>
using namespace std;

struct Queue
{

private:
    //最大容量
    int size;
    //头位置
    int head;
    //尾重要
    int tail;
    //元素数量
    int count;

    int *data;

public:
    Queue(int n) : size(n), head(0), tail(0), count(0)
    {
        data = new int[n];
    }

    int push(int val)
    {
        if (count == size)
        {
            return 0;
        }

        data[tail++] = val;
        if (tail == size)
            tail = 0;
        count++;
        return 1;
    };
    int pop()
    {
        if (empty())
        {
            return 0;
        }

        head++;
        count--;
        return 1;
    };
    int front()
    {
        return data[head];
    };

    bool empty()
    {
        return count == 0;
    };

    void print()
    {
        cout << "count=" << count << endl;
        if (count == 10)
        {
        }
        int newt = tail - 1;
        for (int i = 0; i < size; i++)
        {
            if (tail > head)
            {
                if (i >= head && i < tail)
                {
                    cout << data[i] << " ";
                }
                else
                {
                    cout << "o ";
                }
            }
            else
            {
                if (i >= head || i < tail)
                {
                    cout << data[i] << " ";
                }
                else
                {
                    cout << "o ";
                }
            }
        }
        cout << endl;
        for (int i = 0; i < size; i++)
        {
            if (i == head || i == tail - 1)
            {
                cout << "↑"
                     << " ";
            }
            else
            {
                cout << "  ";
            }
        }
        cout << endl;

        for (int i = 0; i < size; i++)
        {
            if (i == head && i == tail - 1)
            {

                cout << "h&t"
                     << " ";
                continue;
            }
            if (i == head)
            {
                cout << "h"
                     << " ";
                continue;
            }
            if (i == tail - 1)
            {
                cout << "t"
                     << " ";
                continue;
            }
            cout << "  ";
        }
        cout << endl;
    }
};

int main()
{
    Queue *queue = new Queue(10);
    queue->push(2);
    queue->push(3);
    queue->push(5);
    queue->push(2);
    queue->push(3);
    queue->push(5);
    queue->push(2);
    queue->push(3);
    queue->push(5);

    queue->pop();
    queue->pop();
    queue->pop();
    queue->push(2);
    queue->push(3);
    queue->push(5);
    queue->pop();

    queue->push(5);
    // queue->push(5);
    // queue->pop();
    queue->pop();

    queue->print();

    return 0;
}

练习

leetcode p20 有效的括号

可以使用栈解决，如果是左括号则入栈，如果是右括号则匹配，匹配不上就返回false，最后栈不为空也是false.

import collections

class Solution:
    def isValid(self, s: str) -> bool:
        ss = collections.deque()
        mapping = {")": "(", "}": "{", "]": "["}
        
        for i in s:
            if i in mapping.values():  
                ss.append(i)
            elif i in mapping:  
                if not ss or ss.pop() != mapping[i]:  
                    return False
        
        return not ss 

leetcode P225用队列实现栈

from collections import deque

class MyStack:

    def __init__(self):
        self.deque1 = deque()

    def push(self, x: int) -> None:
        self.deque1.appendleft(x)
        for i in range(len(self.deque1)-1):
            self.deque1.appendleft(self.deque1.pop())

    def pop(self) -> int:
        return self.deque1.pop()

    def top(self) -> int:
        return self.deque1[-1]

    def empty(self) -> bool:
        return len(self.deque1)==0