highlight: vs2015
大家好晃择，我是melo蚣录，一名大二上軟件工程在讀生，經(jīng)歷了一年的摸滾立宜，現(xiàn)在已經(jīng)在工作室里邊準(zhǔn)備開發(fā)后臺(tái)項(xiàng)目啦冒萄。
不過這篇文章呢，還是想跟大家聊一聊數(shù)據(jù)結(jié)構(gòu)與算法橙数，學(xué)校也是大二上才開設(shè)了數(shù)據(jù)結(jié)構(gòu)這門課尊流，希望可以一邊學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)一邊積累后臺(tái)項(xiàng)目開發(fā)經(jīng)驗(yàn)。
上次的文章灯帮，我們已經(jīng)初步入門了數(shù)據(jù)結(jié)構(gòu):鏈表 想入門數(shù)據(jù)結(jié)構(gòu)崖技，卻總是拜倒在鏈表的石榴裙下?逻住，入門后你是否堅(jiān)持下來了呢，是不是在棧堆里邊徘徊不前了迎献，這篇帶你來攻破ta瞎访！
普通棧
知識點(diǎn)
后進(jìn)先出(只能在一端操作)
image.png
只能對棧頂(表尾)進(jìn)行插入和刪除
image.png
保證棧頂先出即可
image.png
**空棧最好是top=-1
image.png
應(yīng)用場景
1)子程序的調(diào)用：在跳往子程序前，會(huì)先將下個(gè)指令的地址存到堆棧中吁恍，直到子程序執(zhí)行完后再將地址取出扒秸，以回到原來的程序中。
2)處理遞歸調(diào)用：和子程序的調(diào)用類似冀瓦，只是除了儲(chǔ)存下一個(gè)指令的地址外伴奥，也將參數(shù)、區(qū)域變量等數(shù)據(jù)存入堆棧中翼闽。
3)表達(dá)式的轉(zhuǎn)換 [中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式] 與求值(實(shí)際解決)拾徙。
4)二叉樹的遍歷。
5)圖形的深度優(yōu)先(depth一first)搜索法感局。
數(shù)組實(shí)現(xiàn)棧
Java版
注意構(gòu)造器尼啡，是根據(jù)maxSize，然后記得this.maxSize=maxSize
class ArrayStack{
//棧的大小
private int maxSize;
//維護(hù)的數(shù)組
private int[] stack;
//棧頂
private int top;
public ArrayStack() {
}
public ArrayStack(int maxSize) {
this.stack = new int[maxSize];
this.top = -1;
this.maxSize=maxSize;
}
public int pop(){
if(isEmpty()){
throw new RuntimeException("棧已空");
}
return this.stack[top--];
}
public void push(int val){
if(isFull()){
throw new RuntimeException("棧已滿");
}
stack[++top]=val;
}
public boolean isFull(){
return this.top==this.maxSize-1;
}
public boolean isEmpty(){
return this.top==-1;
}
}
C語言版
頭文件SqStack.h
#include"Common.h"
typedef struct{
ElemType* elem;//存儲(chǔ)空間基址
int top;//棧頂?shù)南乱晃? int size;//當(dāng)前分配的內(nèi)存容量
int increment;//擴(kuò)容時(shí)的增量
}SqStack;
Status initStack_Sq(SqStack& S, int size, int inc);//初始化順序棧
Status DestroyStack_Sq(SqStack& S);//銷毀順序棧
Status StackEmpty_Sq(SqStack& S);//判斷是否為空棧
void ClearStack_Sq(SqStack& s);//清空棧
Status Push_Sq(SqStack& S, ElemType e);//元素入棧
Status Pop_Sq(SqStack& S, ElemType& e);//元素出棧,用e返回
Status GetTop_Sq(SqStack S, ElemType& e);//取棧頂元素,用e返回
頭文件Common.h
Status起別名(可觀性更好一點(diǎn)询微，類似Java中的封裝返回結(jié)果)
定義一些相關(guān)的Status返回值
定義ElemType崖瞭，方便擴(kuò)展，更換元素?cái)?shù)據(jù)類型
#include<stdio.h>
#include<stdlib.h>
//定義一些返回值
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//默認(rèn)使用int類型返回值
typedef int Status;
//需要更改元素類型就在此更換int
typedef int ElemType;
源文件SqStack.cpp
#include"Common.h"
#include"SqStack.h"
//初始化順序棧
Status initStack_Sq(SqStack &S, int size, int inc) {
S.elem = (ElemType*)malloc(size * sizeof(ElemType));
if (S.elem == NULL || size <= 0 || inc <= 0) return ERROR;
S.size = size;
S.increment = inc;
S.top = 0;
return OK;
}
//銷毀順序棧
Status DestroyStack_Sq(SqStack &S) {
S.top = 0;
S.size = 0;
S.increment = 0;
free(S.elem);
/*此處后來發(fā)現(xiàn),free操作并不會(huì)改變指針的值
(所以并不會(huì)變成NULL),只是讓他所指向的內(nèi)存空間失效了,
不能正常訪問了而已
*/
/*
//若銷毀失敗
if (S.elem!=NULL) return ERROR;
*/
return OK;
}
//判斷是否為空棧
Status StackEmpty_Sq(SqStack& S) {
return S.top == 0;
}
//清空棧
void ClearStack_Sq(SqStack& S) {
S.top = 0;
}
//元素入棧
Status Push_Sq(SqStack& S, ElemType e) {
if (S.top >= S.size) {
S.elem = (ElemType*)realloc(S.elem, sizeof(ElemType) * (S.size + S.increment));
}
if (S.elem == NULL) return ERROR;
S.elem[S.top] = e;
S.top++;
return OK;
}
//元素出棧,用e返回
Status Pop_Sq(SqStack& S, ElemType& e) {
if (StackEmpty_Sq(S)) return ERROR;
e = S.elem[--S.top];
return OK;
}
//取棧頂元素,用e返回
Status GetTop_Sq(SqStack S, ElemType& e) {
if (StackEmpty_Sq(S)) return ERROR;
e = S.elem[S.top-1];
return OK;
}
注意
此處有點(diǎn)小問題喔拓提，就是棧的銷毀操作读恃，起初我是
free(S.elem);
//若銷毀失敗
if (S.elem!=NULL) {
return ERROR;
}
后來再回過頭來看這篇博客的時(shí)候，發(fā)現(xiàn)free后其實(shí)S.elem并不會(huì)等于NULL代态，為此我又整理了一篇關(guān)于"迷途"指針的問題寺惫，具體可參照 迷途指針
鏈棧
**判空
當(dāng)top指針剛好指向基址的時(shí)候，說明此時(shí)鏈棧為空
image.png
入棧(滿了就擴(kuò)容)
直接S.top==NULL蹦疑，就是棧滿了的情況
image.png
#include "allinclude.h" //DO NOT edit this line
Status Push_Sq2(SqStack2 &S, ElemType e) {
// Add your code here
//其實(shí)可以直接S.top==NULL即可
if(*(S.top)>=S.size){
S.elem=(ElemType*)realloc(S.elem,sizeof(ElemType)*(S.size+S.increment));
if(S.elem==NULL) return ERROR;
}
*(S.top)=e;
S.top++;
return OK;
}
進(jìn)制轉(zhuǎn)換
image.png
#include "allinclude.h"
void Conversion(int N, int rd)
{ // Add your code here
SqStack stack;
//初始化棧
InitStack_Sq(stack,10,1);
//N>0
while(N>0){
Push_Sq(stack,N%rd);
N/=rd;
}
//再出棧便可實(shí)現(xiàn)逆序打印出來(因?yàn)闂５奶匦?
while(!StackEmpty_Sq(stack)){
ElemType temp;
Pop_Sq(stack,temp);
printf("%d",temp);
}
}
括號匹配
(力扣)20有效的括號
最初版本
思路
- 特判右括號西雀，判斷是否跟棧頂元素匹配
- 若棧已經(jīng)為空了，說明左括號不夠用來匹配歉摧，無效
- 若不匹配艇肴，也無效
- 若匹配，則將匹配到的左括號出棧叁温，暫時(shí)有效
- 其他情況(左括號)直接壓入棧
- 最后出循環(huán)的時(shí)候再悼，若棧中還有元素說明左括號沒有被匹配完，也無效
細(xì)節(jié)
- 有不符合的直接return false
優(yōu)化
- 奇數(shù)個(gè)直接無效
bool isValid(char * s){
int length = strlen(s);
//初始化為-1
int top=-1;
char stack[length] ;
//若本身就是奇數(shù)個(gè),則直接無效
if(length%2!=0){
return false;
}
//遍歷字符串
for(int i=0;i<length;i++){
//特判右括號
if(s[i]==')'){
//若棧已空或者棧頂元素不匹配,直接false
if(top<0||stack[top]!='('){
return false;
}
//否則將匹配到的左括號出棧
top--;
}
//同理
else if(s[i]=='}'){
if(top<0||stack[top]!='{'){
return false;
}
top--;
}
else if(s[i]==']'){
if(top<0||stack[top]!='['){
return false;
}
top--;
}
//若是左括號.直接加入棧
else stack[++top]=s[i];
}
//出來時(shí)若棧不為空,說明沒有完全匹配掉
if(top!=-1){
return false;
}
return true;
}
改進(jìn)版本
- 先統(tǒng)一處理右括號變成左括號膝但，以便后續(xù)可以直接統(tǒng)一判斷相不相等即可
細(xì)節(jié)
- 注意要先
//若是左括號.直接加入棧
else{
stack[++top]=s[i];
continue;
}
bool isValid(char * s){
int length = strlen(s);
//初始化為-1
int top=-1;
char stack[length] ;
//若本身就是奇數(shù)個(gè),則直接無效
if(length%2!=0){
return false;
}
//遍歷字符串
for(int i=0;i<length;i++){
//將右括號統(tǒng)一變成左括號,后續(xù)可以直接統(tǒng)一判斷相不相等即可
if(s[i]==')') s[i]='(';
else if(s[i]=='}') s[i]='{';
else if(s[i]==']') s[i]='[';
//若是左括號.直接加入棧
else{
stack[++top]=s[i];
continue;
}
//若棧已空或者棧頂元素不匹配,直接false
if(top<0||stack[top]!=s[i]){
return false;
}else{
//否則將匹配到的左括號出棧
top--;
}
}
//出來時(shí)若棧不為空,說明沒有完全匹配掉
if(top!=-1){
return false;
}
return true;
}
題解(最優(yōu))
用函數(shù)將右括號預(yù)處理包裝起來了冲九，而且如果不是右括號，會(huì)返回0跟束，直接解決了上邊的三個(gè)都不符合得再else和continue的情況
- 要用個(gè)ch來保存!!!!!!!!!!!!!!!!!!!!!!!!莺奸，因?yàn)橹皇莻髦党蠛ⅲ瑳]有傳引用
char pairs(char a) {
if (a == '}') return '{';
if (a == ']') return '[';
if (a == ')') return '(';
return 0;
}
bool isValid(char* s) {
int n = strlen(s);
if (n % 2 == 1) {
return false;
}
int stk[n + 1], top = 0;
for (int i = 0; i < n; i++) {
//注意要用個(gè)ch來保存
char ch = pairs(s[i]);
if (ch) {
if (top == 0 || stk[top - 1] != ch) {
return false;
}
top--;
} else {
stk[top++] = s[i];
}
}
return top == 0;
}
細(xì)節(jié)容易出錯(cuò)版本
我這里是直接compare(exp[i])，但是沒有修改到exp[i]灭贷，他依然是右括號温学，下邊仍然拿這個(gè)來測就錯(cuò)了
#include "allinclude.h"
int compare(char str){
if(str==')') return '(';
if(str=='}') return '{';
if(str==']') return '[';
return 0;
}
Status matchBracketSequence(char* exp, int n)
{ // Add your code here
//若是空字符串或者奇數(shù)長度,則直接不匹配
if(n==0||n%2!=0) return false;
SqStack stack;
InitStack_Sq(stack,n,1);
for(int i=0;i<n;i++){
//若是右括號
if(compare(exp[i])){
ElemType temp;
GetTop_Sq(stack,temp);
//若非空且匹配,則出棧
if(stack.top==0||exp[i]!=temp){
return false;
}else{
Pop_Sq(stack,temp);
}
}
//若是左括號則直接入棧
else{
Push_Sq(stack,exp[i]);
}
}
//若非空,說明左括號沒有匹配完
if(!StackEmpty_Sq){
return false;
}
return true;
}
最后
- 最近偷懶了，一直有在認(rèn)真記錄筆記甚疟，但是卻疏于整理仗岖，沒有發(fā)出來，希望近幾天可以抽出更多時(shí)間來繼續(xù)整理隊(duì)列古拴，哈希表箩帚，排序等方面的知識
