1.1.4 棧stack與隊(duì)列queue
棧stack
部分定義參考自百度百科棧
- 棧（stack）在計(jì)算機(jī)科學(xué)中是限定僅在表尾進(jìn)行插入或刪除操作的線性表,，是一種后進(jìn)先出（LIFO )的數(shù)據(jù)結(jié)構(gòu)缠诅。
- 棧是一種數(shù)據(jù)結(jié)構(gòu)乍迄，它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底闯两，最后的數(shù)據(jù)在棧頂谅将，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)重慢。
- 棧是只能在某一端插入和刪除的特殊線性表。
- 棧的底層實(shí)現(xiàn)是基于數(shù)組或者鏈表
- c++ stl中stack是一個(gè)容器適配器似踱，stack默認(rèn)的基礎(chǔ)容器為deque容器（一種雙端都可以進(jìn)行刪除插入操作的數(shù)據(jù)結(jié)構(gòu)）
下面的例子說明圖片來自維基百科：
queue隊(duì)列
部分定義參考自百度百科隊(duì)列
- 隊(duì)列是一種特殊的線性表屯援，是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)念脯。
- 隊(duì)列只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作绿店。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭假勿。
- 隊(duì)列的底層實(shí)現(xiàn)也是基于數(shù)組或者鏈表。
- c++ stl中queue是一個(gè)容器適配器恶导，vector浸须、list和deque都能夠作為queue的基礎(chǔ)容器，而與stack一樣queue默認(rèn)的基礎(chǔ)容器也為deque容器
232. Implement Queue using Stacks
使用stack模擬實(shí)現(xiàn)queue的功能裂垦，包括push肌索、pop、peek诚亚、empty
1.舉例子-畫圖-解題思路
實(shí)現(xiàn)queue的push，意味著每次的元素都要放在stack的底部届巩，為了完成這樣的效果，我們首先需要把stack1中的元素挨個(gè)取出放到輔助棧stack2中恕汇，然后把新來的元素直接放到stack1中，最后把stack2中的元素取出來再放到stack1中瘾英。
push示意圖：
pop示意圖：
queue的pop即stack1的top+pop操作（c++的stack缺谴，top只返回最頂元素，不會(huì)出棧湿蛔，pop才會(huì)執(zhí)行出棧操作）
2. 寫核心邏輯代碼
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stack<int> stack2;
// 將stack1中的元素移動(dòng)到stack2中
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
//將新push的元素放入stack1中
stack1.push(x);
//將stack2中的元素放回stack1中
while(!stack2.empty())
{
stack1.push(stack2.top());
stack2.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
//top方法只返回棧的頂值，不會(huì)出棧
int value = stack1.top();
//出棧操作是pop添谊，但沒有返回值
stack1.pop();
return value;
}
/** Get the front element. */
int peek() {
return stack1.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return stack1.empty();
}
private:
stack<int> stack1;
};
3. 邊界條件-無
4. 優(yōu)化
每次push元素都要把元素經(jīng)歷stack1-stack2-stack1這樣的流程是有些浪費(fèi)的察迟。可以考慮一種lazy的方式扎瓶，同樣準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)與算法兩個(gè)stack，pushi時(shí)候新元素直接放到stack1，pop或者peek時(shí)候削彬，先看stack2中是否有元素，有直接出棧，沒有則把stack1中的元素移動(dòng)到stack2中。
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stack1.push(x);
}
void shiftStack()
{
if(stack2.empty())
{
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
shiftStack();
if(!stack2.empty())
{
int value = stack2.top();
stack2.pop();
return value;
}
return 0;
}
/** Get the front element. */
int peek() {
shiftStack();
if(!stack2.empty())
{
return stack2.top();
}
return 0;
}
/** Returns whether the queue is empty. */
bool empty() {
return stack1.empty() && stack2.empty();
}
private:
stack<int> stack1,stack2;
};
5. 小結(jié)
stack 經(jīng)常作為一種輔助手段實(shí)現(xiàn)更為復(fù)雜的一些算法（圖的深度優(yōu)先遍歷）改鲫，我們后面也會(huì)看到。常用的語言c++/java中都內(nèi)置了stack的數(shù)據(jù)類型像棘，請(qǐng)小伙伴們嘗試?yán)斫夂褪褂胹tack〗厍福框架圖將在225題目的小結(jié)中一并給出烟零。
225. Implement Stack using Queues
使用隊(duì)列queue模擬實(shí)現(xiàn)stack的push咸作、pop、top记罚、empty函數(shù)
1.舉例子-畫圖-解題思路
先考慮利用queue實(shí)現(xiàn)stack的push函數(shù)壳嚎。我們要想辦法每次把push的數(shù)據(jù)放到q1（queue）的頭部，這時(shí)需要借助另外一個(gè)q2（queue）烟馅，push到q1前先把q1中的數(shù)據(jù)依次取出放到q2中，然后將新數(shù)據(jù)push到q1中刊驴，最后把q2中數(shù)據(jù)依次取出再放回q1中穿撮。
2. 寫核心邏輯代碼
class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
queue<int> q2;
//step1 step2 將queue1中元素放到queue2中
while(!q1.empty())
{
q2.push(q1.front());
q1.pop();
}
// step2 將新元素放到queue1中
q1.push(x);
//step3 setp4 再將queue2中元素放回queue1中
while(!q2.empty())
{
q1.push(q2.front());
q2.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int value = q1.front();
q1.pop();
return value;
}
/** Get the top element. */
int top() {
return q1.front();
}
/** Returns whether the stack is empty. */
bool empty() {
return q1.empty();
}
private:
queue<int> q1;
};
3. 邊界條件
題目已經(jīng)幫我們限制了各種邊界條件痪欲，不用在代碼中說明
4. 優(yōu)化
還有一種解法是只用一個(gè)queue來完成stack的push函數(shù)。具體思路是：將新元素push到queue1中栗柒，然后將新元素之前的各個(gè)元素依次取出來放到新元素后面知举，這樣新元素最后就位于queue1的頭部了。
//我們只重寫這個(gè)push函數(shù)逛钻，其他函數(shù)的實(shí)現(xiàn)與未優(yōu)化前的版本一致
/** Push element x onto stack. */
void push(int x) {
int length = q1.size();
q1.push(x);
while(length--)
{
q1.push(q1.front());
q1.pop();
}
}
5. 小結(jié)
queue也經(jīng)常作為一種輔助手段實(shí)現(xiàn)更為復(fù)雜的一些算法（圖的廣度優(yōu)先遍歷）锰提，我們后面也會(huì)遇到相應(yīng)的例子。常用的語言c++/java中也都內(nèi)置了queue的數(shù)據(jù)類型立肘。
怎樣應(yīng)對(duì)IT面試與筆試-（一）
怎樣應(yīng)對(duì)IT面試與筆試-（二）
怎樣應(yīng)對(duì)IT面試與筆試-（三）
怎樣應(yīng)對(duì)IT面試與筆試-（四）
怎樣應(yīng)對(duì)IT面試與筆試-（五）
怎樣應(yīng)對(duì)IT面試與筆試-（五-1）
怎樣應(yīng)對(duì)IT面試與筆試-（六）
怎樣應(yīng)對(duì)IT面試與筆試-（七）
怎樣應(yīng)對(duì)IT面試與筆試-（八）
怎樣應(yīng)對(duì)IT面試與筆試-（九）
怎樣應(yīng)對(duì)IT面試與筆試-（十）
怎樣應(yīng)對(duì)IT面試與筆試-（十一）
怎樣應(yīng)對(duì)IT面試與筆試-（十二）
怎樣應(yīng)對(duì)IT面試與筆試-（十三）
怎樣應(yīng)對(duì)IT面試與筆試-（十四）
怎樣應(yīng)對(duì)IT面試與筆試-（十五）
怎樣應(yīng)對(duì)IT面試與筆試-（十六）
