题目:
Given an absolute path for a file (Unix-style), simplify it.
For example,
path ="/home/", =>"/home"
path ="/a/./b/../../c/", =>"/c"
分析:
路径化简。
基本思路就是使用栈来模拟进入某一路径或者返回上一级。
注意以下边界情况：
- "/../" 应化简为 "/"
- "/home//foo/" 应化简为 "/home/foo"
Tag Archives: 栈
LeetCode #225 Implement Stack using Queues (队列实现栈)
题目：
Implement the following operations of a stack using queues.
- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- empty() — Return whether the stack is empty.
分析：
使用队列实现栈的数据结构。
1个队列。入栈时，先将要入栈的元素添加到队尾，然后将除了这个元素之外的所有元素依次出队，再入队。这样可以保证新入栈的元素总是在队列的最前面。
出栈时，直接出队即可。
Continue reading LeetCode #225 Implement Stack using Queues (队列实现栈)
LeetCode #232 Implement Queue using Stacks (栈实现队列)
题目：
Implement the following operations of a queue using stacks.
- push(x) — Push element x to the back of queue.
- pop() — Removes the element from in front of queue.
- peek() — Get the front element.
- empty() — Return whether the queue is empty.
分析：
使用栈来实现队列的数据结构。
2个栈，stack1用来入队，stack2用来出队。
出队时，如果stack2不为空，则stack2直接弹出一个元素；如果为空，则stack1弹出所有元素，stack1每弹出一个元素就压入stack2，最后stack2再弹出一个元素。
Continue reading LeetCode #232 Implement Queue using Stacks (栈实现队列)