LeetCode (225):用队列实现栈

LeetCode 相关的文章:

1、 LeetCode | 206.反转链表

2、 LeetCode | 24.两两交换链表中的节点

3、 LeetCode | 141.环形链表

4、 LeetCode | 20.有效的括号

这次来写一下 LeetCode 的第 225 题,用队列实现栈。

题目描述

题目直接从 LeetCode 上截图过来,题目如下:

上面的题就是 用队列实现栈 题目的截图,同时 LeetCode 给出了一个类的定义,然后要求实现 用队列实现栈 的完整的数据结构。这次我没有使用 C 语言,而是使用了 C++ 语言,整个类的定义如下:

class MyStack {

public:

/** Initialize your data structure here. */

MyStack() {

}


/** Push element x onto stack. */

void push(int x) {

}


/** Removes the element on top of the stack and returns that element. */

int pop() {

}


/** Get the top element. */

int top() {

}


/** Returns whether the stack is empty. */

bool empty() {

}

};


/**

* Your MyStack object will be instantiated and called as such:

* MyStack* obj = new MyStack();

* obj->push(x);

* int param_2 = obj->pop();

* int param_3 = obj->top();

* bool param_4 = obj->empty();

*/

从上面的类定义可以看出,这次的实现和之前几篇文章中的题目有所不同,之前的是要求实现一个函数体,而这次是实现一个完整的类定义。

类定义中有几个要实现的成员函数,分别是, push 完成入栈 pop 完成出栈 top 用来获取栈顶元素 empty 用来判断栈是否为空

问题分析

在数据结构中,队列和栈是两个完全不同的数据结构。 队列是一个先进先出的数据结构,具有从队尾入队,从队头出队的特性。 栈是一个后进先出(先进后出)的数据结构,无论出栈还是入栈,始终都是在栈顶进行操作

队列和栈这两种数据结构的操作如下图所示。

上面的第一幅图是队列,队列只能从队尾入队,从队头出队。

上面的第二幅图是栈,入栈和出栈只能在栈顶的位置进行操作。

在第一幅图中有四个元素在队列中,我们要模拟栈结构执行 pop 操作的话,应该将元素 4 出队,但是队列的 pop 操作出队的却是元素 1,因此,我们没有办法直接让元素 4 出队。

当然了,直接让元素 4 出队是不可能了,但是我们可以利用其他的方式让其出队。在元素 4 出队前,依次让元素 1、2 和 3 出队再入队,此时元素 4 就到了队头,这时让元素 4 出队就可以了。用一组图演示一下元素 4 出队的情况。

我们要让元素 4 出队,就需要将元素 4 移动到队头,那么就需要将元素 1 出队,然后再入队到队尾,然后依次这样操作元素 2 和元素 3。然后元素 4 就到了队头,执行队列的 pop 操作就可以让其出队了。

下次出队的时候,可以将元素 3 移动到队头,然后出队。此时队列中还剩元素 1 和元素 2。如果有入队的,那么就直接放到队列的队尾即可。

通过这样的操作,就让队列实现了栈的操作。

代码实现

依据我的思路来写代码,代码还是比较简单的,代码如下:

class MyStack {

private:

queue<int> q;

public:

/** Initialize your data structure here. */

MyStack() {


}


/** Push element x onto stack. */

void push(int x) {

q.push(x);

}


/** Removes the element on top of the stack and returns that element. */

int pop() {

int size = q.size();

int n = 0;

int tmp;


while (n < size - 1) {

tmp = q.front();

q.pop();

q.push(tmp);


n ++;

}


tmp = q.front();

q.pop();


return tmp;

}


/** Get the top element. */

int top() {

return q.back();

}


/** Returns whether the stack is empty. */

bool empty() {

return q.empty();

}

};



/**

* Your MyStack object will be instantiated and called as such:

* MyStack* obj = new MyStack();

* obj->push(x);

* int param_2 = obj->pop();

* int param_3 = obj->top();

* bool param_4 = obj->empty();

*/

我直接使用了 C++ 的 queue 这个队列,queue 支持队列的所有操作。queue 支持队列常用操作有:

push(): 队尾入队

pop():   队头出队

size():   队列长度

empty():队列是否为空

front():  返回队头元素的值

back():  返回队尾元素的值

整个题目中最复杂的部分应该就是出栈的操作,而整个出栈的操作其实一个循环就可以了。

提交结果

在写完 MyStack 类后,点击右下角的 “ 执行代码 ”,然后观察  “输出” 和 “预期结果”  是否一致,一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后,系统会使用更多的测试用例来测试我们写的函数体, 如果所有的测试用例都通过了,那么就会给出 “通过” 的字样, 如果没有通过,会给出失败的那一组测试用例,我们继续修改代码 。我们以上代码 “提交” 以后的截图如下:

这个题目重点就是在考察思路了,有谁在实际的项目中会这么玩数据结构呢?

喜欢就点在看哦~

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章