介紹

棧(stack) : 具有先進(jìn)后出，后進(jìn)先出的特點(diǎn)。

• C++ Stack（堆棧） 是一個(gè)容器類的改編，為程序員提供了堆棧的全部功能，——也就是說(shuō)實(shí)現(xiàn)了一個(gè)先進(jìn)后出（FILO）的數(shù)據(jù)結(jié)構(gòu)。

empty() 堆棧為空則返回真 pop() 移除棧頂元素 push() 在棧頂增加元素 size() 返回棧中元素?cái)?shù)目 top() 返回棧頂元素

C++ stack 的棧是不能遍歷的

• 隊(duì)列(Queue) : 具有先進(jìn)先出的特點(diǎn)。

q.empty() 如果隊(duì)列為空返回true，否則返回false q.size() 返回隊(duì)列中元素的個(gè)數(shù) q.pop() 刪除隊(duì)列首元素但不返回其值 q.front() 返回隊(duì)首元素的值，但不刪除該元素 q.push() 在隊(duì)尾壓入新元素 q.back() 返回隊(duì)列尾元素的值，但不刪除該元素

stack

題目1:獲取stack中最大的元素

解題思路：使用2個(gè)stack,一個(gè)是常規(guī)的stack,另一個(gè)stack 存儲(chǔ)在比較過(guò)程中大的元素。

class stackWithMax { private:stack<int> valueStack;stack<int> maxStack;public:void push(int);int pop();int max(); };void stackWithMax::push(int value) {if(maxStack.empty() || maxStack.top() <=value){maxStack.push(value);}valueStack.push(value); }int stackWithMax::pop() {int value=valueStack.top();valueStack.pop();if(value == maxStack.top()){maxStack.pop()}return value; }int stackWithMax::max() {return maxStack.pop(); }

題目2:通過(guò)stack 實(shí)現(xiàn)隊(duì)列Queue

我們知道stack輸出順序和queue的順序是相反的
解題思路: 通過(guò)兩個(gè)棧，互相傾倒的方式，當(dāng)一個(gè)棧的元素，傾倒另一個(gè)棧上，從而使得原來(lái)?xiàng)Ｖ凶詈蟪鰲５脑刈钕瘸鰲?#xff0c;從而顛倒了出棧的順序。

class Queue { private: stack<int> inputStack; stack<int> outputStack; public: void enqueue(int); int dequeue(); ];void Queue::enqueue(int value) {inputStack.push(value); }int Queue::dequeue() {int value;if(!outputStack.empty()){value=outputStak.top();outputStack.pop();return value;}while(!inputStack.empty()){.outputStack.push(inputStack.top())inputStack.pop();}value=outputStack.top();outputStack.pop();return value; }

題目3: 如何對(duì)Stack進(jìn)行升序排列

解題思路:假設(shè)使用兩個(gè)Stack A 和 B ,隊(duì)列A中元素是沒(méi)有順序的，將隊(duì)列A中的元素有序的加入隊(duì)列B中，從隊(duì)列A中取一個(gè)元素，假設(shè)該元素不符合隊(duì)列B當(dāng)前的排列順序，我們就取stackB上的元素，直到元素可以按順序入棧。

stack<int> sort(stack<int> &input) {stack<int> output;while(!input.empty()){int value=input.top();input.pop();while(!output.empty() && output.top <value){input.push(output.top())output.pop();}output.push(value);}return output; }

“save or latter” 問(wèn)題

有一類問(wèn)題有這樣的特性：當(dāng)前節(jié)點(diǎn)的解依賴后驅(qū)節(jié)點(diǎn)。
對(duì)于某一類當(dāng)前節(jié)點(diǎn)，如果不能獲知后驅(qū)節(jié)點(diǎn)，就無(wú)法得到有意義的解。這類問(wèn)題可以通過(guò)stack（或等同于stack的若干個(gè)臨時(shí)變量）

解決：先將當(dāng)前節(jié)點(diǎn)入棧，然后看其后續(xù)節(jié)點(diǎn)的值，直到其依賴的所有節(jié)點(diǎn)都完備時(shí)，再?gòu)臈Ｖ袕棾鲈摴?jié)點(diǎn)求解。某些時(shí)候，甚至需要反復(fù)這個(gè)過(guò)程：將當(dāng)前節(jié)點(diǎn)的計(jì)算結(jié)果再次入棧，直到其依賴的后續(xù)節(jié)點(diǎn)完備。

題目1：驗(yàn)證括號(hào)的有效性

給定一個(gè)只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號(hào)必須用相同類型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。

注意：空字符串可被認(rèn)為是有效字符串

思路

由于要對(duì)照字符串對(duì)稱位置上的括號(hào)是否對(duì)應(yīng)，決定采用棧來(lái)解決這一問(wèn)題，若字符串長(zhǎng)度不為偶數(shù)則直接返回false，遍歷字符串，讀到前括號(hào)時(shí)入棧，讀到后括號(hào)時(shí)若棧空則返回false,若棧不空則用棧頂元素與其比較，能對(duì)應(yīng)則出棧，不能則返回false。最后檢查棧空，若空則返回true

代碼實(shí)現(xiàn):

bool isLeftParentheses(char left,char right) {return input == '(' || input == '[' || input == '{'; }bool isMatchParentheses(char left,char right) {swithc(left){case '(':return right == ')';case '[':return right == ']';case '{':return right == '}';}return false; }bool isValidParentheses(string input) {stack<char> parenthesesStack;for(int i=0;i<input.length;i++){if(isLeftParentheses(input[i]))parenthesesStack.push(input[i]);else:{if (parenthesesStack.empty() || !isMatchParentheses(parenthesesStack.top(),inut[i])){return false;}else if(!parenthesesStack.empty() && isMatchParentheses(parenthesesStack.top(),inut[i]) ){parenthesesStack.pop();}else{return false;}}}return parenthesesStack.empty(); }

代碼2

{ class Solution { public:bool isValid(string s) {if(s.size()%2!=0){return false;}stack <char>stk;for(int i=0;i<s.size();i++){if(s[i]=='('||s[i]=='{'||s[i]=='['){stk.push(s[i]);}else{if(stk.empty()){return false;}else{if(s[i]==')'&&stk.top()=='('){stk.pop();}else if(s[i]=='}'&&stk.top()=='{'){stk.pop();}else if(s[i]==']'&&stk.top()=='['){stk.pop();}else{return false;}}}}return stk.empty();} };}

參考博客：C++有效的括號(hào)

用stack解決Top-Down結(jié)構(gòu)的問(wèn)題

所謂的Top-Down結(jié)構(gòu)，從邏輯理解角度來(lái)看，實(shí)際上就是一種樹(shù)形結(jié)構(gòu)，從頂層出發(fā)，逐漸向下擴(kuò)散，例如二叉樹(shù)的周游問(wèn)題。在實(shí)際運(yùn)算的時(shí)候，我們先解決子問(wèn)題，再利用子問(wèn)題的結(jié)構(gòu)解決當(dāng)前問(wèn)題。

由于Stack的LIFO特征，可以利用Stack數(shù)據(jù)結(jié)構(gòu)消除遞歸。Recursion通常用函數(shù)調(diào)用自身實(shí)現(xiàn)，在系統(tǒng)調(diào)用的時(shí)候系統(tǒng)會(huì)分配額外的空間，并且需要用指針記錄返回的位置，故overhead比較大

題目1： 二叉樹(shù)的中序遍歷

中序遍歷：首先遍歷根結(jié)點(diǎn)的左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷其右子樹(shù)。

未完待續(xù)。。。

總結(jié)

以上是生活随笔為你收集整理的C++练习11： 栈 和队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。