目錄
一、棧的概念及結(jié)構(gòu)
?二、棧的實(shí)現(xiàn)
三、初學(xué)棧的練習(xí)題
一、棧的概念及結(jié)構(gòu)
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
二、棧的實(shí)現(xiàn)
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小。
?
具體實(shí)現(xiàn)代碼如下：
#pragma once
//Stack.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 支持動(dòng)態(tài)增長(zhǎng)的棧
//使用數(shù)組實(shí)現(xiàn)
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 棧頂
int _capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個(gè)數(shù)
int StackSize(Stack* ps);
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps);
// 銷(xiāo)毀棧
void StackDestroy(Stack* ps);//Stack.c
#include "Stack.h"
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_top = 0;
ps->_capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//容量滿了
if (ps->_capacity == ps->_top)
{
//如果數(shù)組的容量為0，就賦值為4,；如果數(shù)組的容量不為0且容量滿了，就擴(kuò)大為原來(lái)容量的二倍。
int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newCapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
ps->_top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
return ps->_a[ps->_top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
int StackEmpty(Stack* ps)
{
return ps->_top;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}test.c
#include "Stack.h"
void test01()
{
Stack st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
while (StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestroy(&st);
}
int main()
{
test01();
return 0;
}三、初學(xué)棧的練習(xí)題
題1：
給定一個(gè)只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判斷字符串是否有效。
有效字符串需滿足：
- 左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
- 左括號(hào)必須以正確的順序閉合。
- 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類(lèi)型的左括號(hào)。
?思路：當(dāng)輸入的字符串中出現(xiàn)左括號(hào)時(shí)就進(jìn)棧，出現(xiàn)右括號(hào)時(shí)就與棧頂?shù)淖罄ㄌ?hào)看是否相匹配。若相匹配就棧頂?shù)淖罄ㄌ?hào)出棧，不匹配就直接返回false。若所有左右括號(hào)都匹配才返回true。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-731422.html
具體實(shí)現(xiàn)代碼如下（C語(yǔ)言實(shí)現(xiàn)）：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-731422.html
//C語(yǔ)言實(shí)現(xiàn)需要自己將棧的各個(gè)功能實(shí)現(xiàn)
typedef char STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 棧頂
int _capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_top = 0;
ps->_capacity = 0;
}
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_capacity == ps->_top)
{
int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
ps->_a = tmp;
ps->_capacity = newCapacity;
}
ps->_a[ps->_top] = data;
ps->_top++;
}
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
ps->_top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top > 0);
return ps->_a[ps->_top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
int StackEmpty(Stack* ps)
{
return ps->_top;
}
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_top = 0;
}
bool isValid(char * s)
{
Stack st;
StackInit(&st);
char topVal;
while(*s)
{
//左括號(hào)入棧
if(*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
//右括號(hào)與棧頂左括號(hào)進(jìn)行匹配
else
{
//棧里已經(jīng)沒(méi)有左括號(hào)了，再輸入一個(gè)右括號(hào)，不匹配。
if(StackEmpty(&st) == 0)
{
StackDestroy(&st);
return false;
}
topVal = StackTop(&st);
//不匹配返回false。
if((topVal == '(' && *s != ')') || (topVal == '[' && *s != ']')
|| (topVal == '{' && *s != '}'))
{
StackDestroy(&st);
return false;
}
//匹配成功棧頂出棧。
StackPop(&st);
}
s++;
}
//最后棧里還剩有左括號(hào)返回false，不剩返回true。
int ret = StackEmpty(&st);
if(ret == 0)
return true;
else
return false;
}?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)之棧的實(shí)現(xiàn)（附源碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
