495. Implement Stack【easy】
2024-08-26 10:00:38
Implement a stack. You can use any data structure inside a stack except stack itself to implement it.
Have you met this question in a real interview?
Example
push(1)
pop()
push(2)
top() // return 2
pop()
isEmpty() // return true
push(3)
isEmpty() // return false
解法一：
class Stack {
public:
struct Node {
int val;
Node *prev, *next;
Node(int v) {
val = v;
prev = NULL;
next = NULL;
}
};
Node *dummy;
Node *tail;
Stack() {
dummy = new Node();
tail = dummy;
}
~Stack() {
}
void push(int x) {
tail->next = new Node(x);
tail->next->prev = tail;
tail = tail->next;
}
// Pop the top of the stack
void pop() {
if (dummy->next == NULL) {
return;
}
Node *prev = tail->prev;
prev->next = NULL;
tail = prev;
}
// Return the top of the stack
int top() {
if (dummy->next == NULL) {
return -;
}
return tail->val;
}
// Check the stack is empty or not.
bool isEmpty() {
if (dummy->next == NULL) {
return true;
}
return false;
}
};
用链表实现栈，因为栈pop出的是最后一个，如果用尾插法的单向链表明显不太方便，所以用双向链表。
参考@YI 的代码
https://yixuanwangblog.wordpress.com/2016/09/04/lintcode-495-implement-stack/
解法二：
class ListNode{
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
};
public class Stack {
ListNode head;
public Stack(){
head = new ListNode(0);
}
/*
* @param x: An integer
* @return: nothing
*/
public void push(int x) {
ListNode node = new ListNode(x);
node.next = head.next;
head.next = node;
}
/*
* @return: nothing
*/
public int pop() {
ListNode top = head.next;
head.next = head.next.next;
return top.val;
}
/*
* @return: An integer
*/
public int top() {
return head.next.val;
}
/*
* @return: True if the stack is empty
*/
public boolean isEmpty() {
if (head.next == null) {
return true;
} else{
return false;
}
}
}
用链表实现栈，使用头插法。
参考@zhengyang2015 的代码
https://zhengyang2015.gitbooks.io/lintcode/implement_stack_495.html
最新文章
- 向上弹出菜单jQuery插件
- git之常用指令
- linux shell工具集合
- ECS 安装redis 及安装PHPredis的扩展
- Andaroid L新特性
- MM32 RTC学习(兼容STM32)
- 使用 Cordova+Visual Studio 创建跨平台移动应用（2）
- 一起来学jquery!
- mockplus 原型设计工具
- 中国科学技术大学统一身份认证系统CAS
- 使用普通用户执行 docker
- python之约束, 异常处理, md5
- Oracle简单语句查询
- VB.NET文件读写（C#可以改写）
- 谷歌算法研究员：我为什么钟爱PyTorch？
- 界面编程之QT的Socket通信20180730
- Word揭秘：公式还能这么玩！
- Django内置的分页模块
- HP-UNIX平台修改Oracle processes参数报错：ORA-27154、ORA-27300、ORA-27301、ORA-27302
- go系列（5）- beego自己写controller