oneinstack 一键配置_PHP_Python_前端_Linux 等等学习笔记

用栈-stack实现队列queue-LeetCode

队列（ Queue）是一系列有顺序的元素的集合，新元素的加入在队列的一端，这一端叫做“队尾”（ rear），已有元素的移除发生在队列的另一端，叫做“队首”（ front）。当一个元素被加入到队列之后，它就从队尾开始向队首前进，直到它成为下一个即将被移出队列的元素。

最新被加入的元素必须处于队尾，在队列停留最长时间的元素处于队首。这种原则有时候叫做“先进先出”（ FIFO, first-in first-out），有时候也叫做“先到先服务”。

引自：problem solving with algorithms and data structures using python

先用python简单的实现一个队列queue感受一下：

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(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(4)
    q.enqueue(&#;dog&#;)
    q.enqueue(True)
    print(q.size())
    q.dequeue()
    print(q.size())
    q.enqueue()
    print(q.size())

可以看出来，为了实现队列这个抽象数据类型，创建一个新的类是最好的方式。利用简单而强大的列表（ List）来帮助建立队列的新类。需要决定列表的哪一端做队尾，哪一端用来做队首。上面的一段代码设定队列的队尾在列表的 0 位置。这使得我们能够利用列表的 insert 功能来向队列的队尾添加新的元素。而 pop 操作则可以用来移除队首的元素（也就是列表的最后一个元素）。这也意味着 enqueue（入队）的复杂度是 O(n)，而 dequeue （出队列）的复杂度是 O(1)。

接下来进入正题，如何用栈来实现一个队列：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

使用两个栈inStack，outStack，其中假定inStack负责push操作，outStack负责pop操作。

//python3:
def __init__(self):
        self.inStack = []
        self.outStack = []

//C语言
typedef struct {
    struct Stack* inStack;
    struct Stack* outStack;
} MyQueue;

2. 实现队列的push（）操作，每次进行添加操作，都会相应得对栈inStack进行添加元素。

//C语言
void myQueuePush(MyQueue* obj, int x) {
    StackPush(obj->inStack, x);
}

//python3:
def push(self, x: int) -> None:
        self.inStack.append(x)

3. 实现队列的pop（）操作，每次进行删除操作，栈outStack负责pop操作：

首先判断栈outStack是否为空？

a.如果outStack为空，则判断inStack是否为空？如果inStack也为空，则输出错误信息，此时队列为空。如果inStack不为空，则将栈inStack中的所有数据存储到outStack中。执outStack.push(inStack.top()), inStack.pop()。然后在对栈outStack执行，outStack.pop()操作，将队列的头元素删除。

b.如果outStack不为空，则直接对outStack执行 outStack.pop()操作。

//python3:
def pop(self) -> int:
        if(self.outStack == []):
            while(self.inStack != []):
                data = self.inStack.pop()
                self.outStack.append(data)
        return self.outStack.pop()

//C语言
int myQueuePop(MyQueue* obj) {
    int ret = 0;
    if(!IsStackEmpty(obj->outStack))
    {
        StackPop(obj->outStack, &ret);
    }
    else
    {
        if(!IsStackEmpty(obj->inStack))
        {
            while (!IsStackEmpty(obj->inStack))
            {
                StackPop(obj->inStack, &ret);
                StackPush(obj->outStack, ret);
            }
            StackPop(obj->outStack, &ret);
        }
        else
        {
            printf(&#;queue is empty&#;);
        }     
    }
    return ret;
}

4.实现队列的front()操作，方法如pop操作相同，只是在最后一步使用outStack.top()返回值。

 //python3:
def peek(self) -> int:
        if(self.outStack == []):
            while(self.inStack != []):
                self.outStack.append(self.inStack.pop())
        return self.outStack[-1]

//C语言
int myQueuePeek(MyQueue* obj) {
    int ret = 0;
    if(!IsStackEmpty(obj->outStack))
    {
        ret = StackTop(obj->outStack);
    }
    else
    {
        if(!IsStackEmpty(obj->inStack))
        {
            while (!IsStackEmpty(obj->inStack))
            {
                StackPop(obj->inStack, &ret);
                StackPush(obj->outStack, ret);
            }
            ret = StackTop(obj->outStack);
        }
        else
        {
            printf(&#;queue is empty&#;);
        }   
    }    
    return ret;
}

5.实现队列的size()操作，和empty()操作，就是对inStack,outStack分别执行操作。

代码清单：

c语言：

struct List
{
    int data;
    struct List* next;
};
struct Stack
{
    struct List* head;
    int size;
};

struct Stack* StackInit(void)
{
    struct Stack* stack = NULL;
    stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->head = (struct List*)malloc(sizeof(struct List));
    stack->head->next = NULL;
    stack->size = 0;
    return stack;
}

int StackPush(struct Stack* stack, int data)
{
    struct List* temp = (struct List*)malloc(sizeof(struct List));
    temp->data = data;
    temp->next = stack->head->next;
    stack->head->next = temp;
    stack->size++;
    printf(&#;push:%d \n&#;,data);
    return 0;
}

int IsStackEmpty(struct Stack* stack)
{
    return stack->size == 0;
}

int StackPop(struct Stack* stack, int* data)
{
    struct List* temp = NULL;
    if(IsStackEmpty(stack))
        return -1;
    
    temp = stack->head->next;
    *data = temp->data;
    stack->head->next = temp->next;
    stack->size--;
    free(temp);
    printf(&#;pop:%d\n&#;,*data);
    return 0;
}

int StackTop(struct Stack* stack)
{
    int temp = 0;
    if(IsStackEmpty(stack))
        return -1;
    temp = stack->head->next->data;
    printf(&#;top:%d\n&#;,temp);
    return temp;
}

void StackFree(struct Stack* stack)
{
    free(stack);
}

typedef struct {
    struct Stack* inStack;
    struct Stack* outStack;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    
    MyQueue* q = NULL;
    q = (MyQueue*)malloc(sizeof(MyQueue));
    q->inStack = StackInit();
    q->outStack = StackInit();
    return q;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    StackPush(obj->inStack, x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int ret = 0;
    if(!IsStackEmpty(obj->outStack))
    {
        StackPop(obj->outStack, &ret);
    }
    else
    {
        if(!IsStackEmpty(obj->inStack))
        {
            while (!IsStackEmpty(obj->inStack))
            {
                StackPop(obj->inStack, &ret);
                StackPush(obj->outStack, ret);
            }
            StackPop(obj->outStack, &ret);
        }
        else
        {
            printf(&#;queue is empty&#;);
        }
        
    }
    
    return ret;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    int ret = 0;
    if(!IsStackEmpty(obj->outStack))
    {
        ret = StackTop(obj->outStack);
    }
    else
    {
        if(!IsStackEmpty(obj->inStack))
        {
            while (!IsStackEmpty(obj->inStack))
            {
                StackPop(obj->inStack, &ret);
                StackPush(obj->outStack, ret);
            }
            ret = StackTop(obj->outStack);
        }
        else
        {
            printf(&#;queue is empty&#;);
        }
        
    }
    
    return ret;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return IsStackEmpty(obj->inStack) && IsStackEmpty(obj->outStack);

}

void myQueueFree(MyQueue* obj) {
    StackFree(obj->inStack);
    StackFree(obj->outStack);
}

python3:

class MyQueue:

    def __init__(self):
        self.inStack = []
        self.outStack = []

    def push(self, x: int) -> None:
        self.inStack.append(x)

    def pop(self) -> int:
        if(self.outStack == []):
            while(self.inStack != []):
                data = self.inStack.pop()
                self.outStack.append(data)
        return self.outStack.pop()

    def peek(self) -> int:
        if(self.outStack == []):
            while(self.inStack != []):
                self.outStack.append(self.inStack.pop())
        return self.outStack[-1]

    def empty(self) -> bool:
        return self.inStack == [] and self.outStack == []

栈的实现和应用-python3
栈stack的数组和单链表实现
最小栈实现-LeetCode
最小栈实现-LeetCode-python3
基于单链表实现的栈解题-LeetCode

oneinstack 一键配置_PHP_Python_前端_Linux 等等 学习笔记