vector<int> FromTail2HeadPrintLinkList(ListNode* head)
{
if (NULL == head)
{
return;
}
ListNode* tmp = head;
vector<int> res;
while (tmp)
{
res.push_back(tmp->val);
tmp = tmp->next;
}
for (int i = 0, j = res.size() - 1; i < j; i++, j--)
{
int temp = res[i];
res[i] = res[j];
res[j] = temp;
}
return res;
}
3 | 剑指Offer09:用两个栈实现队列
题目
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头
部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
示例
输入
1
:
["CQueue","appendTail","deleteHead","deleteHead","deleteHead"]
],[3],[],[],[
输出
1
:
[null,null,3,-1,-1]
输入:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
],[],[5],[2],[],[
输出:
[null,-1,null,null,5,2]
思路
栈的特性“ 先进后出 ”,队列的特性“ 先进先出 ”
要用栈实现队列就是构造出队列的特性,而两个栈可以模拟这个特性,思路如下
1. 栈1作为输入保存,栈2作为输出保存
2. 往队列尾部输入元素,实质就是栈1的正常入栈操作,从队列的尾部删除元素,也是栈1的正常出栈操作
栈1: 1 2 3 4 5 ; 栈2:
队列尾部加入元素:
1. 栈1入栈新元素 --> 栈1: 1 2 3 4 5 6 ; 栈2:
2. 此时执行队列输出时,将栈1的元素出栈并入栈到栈2,再将栈2输出就得到了正常的队列输出
队列尾部删除元素:
1. 栈1出栈 --> 栈1: 1 2 3 4 ; 栈2:
评论0
最新资源